Recent posts in Theory of Computation

1

Divisibility language and Minimum Number of States in a DFA accepting a binary number divisible by 'n'

First let me define what is Divisibility language . We have two very similar looking type of languages. I call one type Length divisibility language and other I call Divisibility language "Length divisibility machines/languages" are different from " ... -main.pdf https://cs.stackexchange.com/questions/85850/minimum-number-of-states-in-dfa-accepting-binary-number-with-decimal-equivalent

posted Aug 30, 2020 in Theory of Computation Deepakk Poonia (Dee) 11,441 views

2

Minimal Deterministic Finite Automata

Let the i/p alphabet = {0,1} for the following questions : $\color{red}{Q) \mathbf{About\; String \;Lengths : }}$ $\color{green}{i) \text{ Length of the strings exactly = n : }}\color{blue}{\text{ n+2}}$ ... $\color{DarkOrange}{\text{Answer = (n+1)*(m+1) + 1}}$ Supported Documents : https://drive.google.com/open?id=1haPRlS78p7RA7ugMhaK9Li6370ZjaEcx

posted Nov 7, 2019 in Theory of Computation Shaik Masthan 1,639 views

3

Minimum Number of States in a DFA accepting a binary number divisible by 'n'

Lets first prove the number of states in the minimal DFA for accepting binary strings divisible by a given number say $12$ We need $3$ states for checking if a binary number is divisible by $3$ - each state corresponding to remainders $0,1,2.$ Here, remainder $0$ will be the ... by $\text{LCM}(m,n).$ To find the minimal number of states in the DFA accepting binary strings divisible by $m$ or $n:$

posted Sep 20, 2019 in Theory of Computation Arjun 2,206 views

4

Decidability Slides

These slides will be explaining decidability and Rice’s theorem. You can ask if anything is not clear. Part 2 is added now... Decidability Slides Updated

posted Jan 16, 2019 in Theory of Computation Arjun
edited Jan 27, 2019 by Arjun 3,586 views

5

Theory of Computation - GO Classroom

Day Date Contents Slides Assignments 1 Sep 27 Regular Language- alphabets, language(set of strings), language class or language family All languages -uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, there is an uncountable ... only- finite movement or configuration, all problems of undecidability is due to reverse movement of R/W head of tape.

posted Oct 6, 2018 in Theory of Computation Manoja Rajalakshmi A 1,049 views

6

DECIDABILITY

PLEASE CHECK MY UNDERSTANDING:- 1. Halting Problem:- a) A turing machine halts after running for exactly k steps on any input This is DECIDABLE, as the number of steps are finite and we can test it by giving a string whose length is 'k' as input. b) A ... DECIDABLE(same as above). c) A turing machine replaces the characters on the tape atmost n times on any input SEMI-DECIDABLE(same as above).

posted Sep 14, 2018 in Theory of Computation Balaji Jegan
edited Nov 23, 2018 by Balaji Jegan 1,987 views

7

Rice Theorem

Nice papers with examples: http://drona.csa.iisc.ernet.in/~deepakd/atc-2011/tm-reductions-rice.pdf http://people.cs.aau.dk/~srba/courses/CC-08/rice-uk.pdf

posted Jan 22, 2016 in Theory of Computation bahirNaik 332 views

8

Important Questions in Theory of Computation

Important Ones https://gateoverflow.in/questions/theory-of-computation?sort=featured More Questions http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/assign6/pb9.html Problem Set 1 Problem Set 2

posted Aug 9, 2015 in Theory of Computation Arjun 8,312 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Subjects

Network Sites

Recent posts in Theory of Computation

Log In

Register

Recent Posts

Subjects

Recent Blog Comments

Network Sites

Recent posts in Theory of Computation