Log In

Recent posts in Theory of Computation

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) 11,369 views
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,449 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 1,787 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
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
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
Nice papers with examples:
posted Jan 22, 2016 in Theory of Computation bahirNaik 324 views
Important Ones More Questions 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.