search
Log In

Recent posts in Theory of Computation

1
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 in Theory of Computation Deepakk Poonia (Dee) 11,369 views
2
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,449 views
3
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 1,787 views
4
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,496 views
5
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,000 views
6
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,865 views
7
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 324 views
8
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,165 views
To see more, click for the full list of questions or popular tags.
...