Time Left - 20:00 mins
GATE CS : Theory of Computation Champion Quiz 5
Attempt now to get your rank among 488 students!
Question 1
Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite.
II. Whether a given context–free language is regular
III. Whether two push–down automata accept the same language
IV. Whether a given grammar is context–free
I. Whether the intersection of two regular languages is infinite.
II. Whether a given context–free language is regular
III. Whether two push–down automata accept the same language
IV. Whether a given grammar is context–free
Question 2
Which of the following problems is undecidable?
Question 3
Which of the following problem is not decidable
Question 4
Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite.
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
I. Whether the intersection of two regular languages is infinite.
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
Question 5
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is a context-free language, then, is L’ also context-free?
3) If L is a regular language, then, is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?
1) Does a given program ever produce an output?
2) If L is a context-free language, then, is L’ also context-free?
3) If L is a regular language, then, is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?
Question 6
Which of the following statements is false?
Question 7
Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable but not recursive language.
Which one of the following statements is false?
Question 8
Consider the following statements about the context free grammar
G ={S → SS, S → ab, S → ba, S → ∈}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
G ={S → SS, S → ab, S → ba, S → ∈}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
Question 9
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
Question 10
Let
and 
Which of these languages are NOT context free?
and Which of these languages are NOT context free?- 488 attempts
- 4 upvotes
- 30 comments
Jul 5GATE & PSU CS
