1 Crore+ students have signed up on EduRev. Have you? Download the App 
The number of states required to automate the last question i.e. {a,b}*{aba}{a,b}* using finite automata:
Which of the following problems are decidable?
Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given contextfree language is regular
III. Whether two pushdown automata accept the same language
IV. Whether a given grammar is contextfree
Which of the following problems is undecidable?
Which of the following statements is/are FALSE?
1. For every nondeterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive.
Which of the following statements is not necessarily true?
Which of the following is true for the language
If L and L' are recursively enumerable, then L is
152 docs216 tests

Test: Turing Machines & Undecidability 2 Test  20 ques 
Test: Pumping Lemma Test  10 ques 
152 docs216 tests

Test: Turing Machines & Undecidability 2 Test  20 ques 
Test: Pumping Lemma Test  10 ques 