Log In

Most viewed posts in Theory of Computation

Important Ones More Questions Problem Set 1 Problem Set 2
posted Aug 9, 2015 in Theory of Computation Arjun 7,975 views
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
posted Aug 30 in Theory of Computation Deepakk Poonia (Dee) 4,419 views
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
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
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 :
posted Nov 7, 2019 in Theory of Computation Shaik Masthan 1,292 views
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 933 views
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 903 views
Nice papers with examples:
posted Jan 22, 2016 in Theory of Computation bahirNaik 305 views
To see more, click for the full list of questions or popular tags.