Time Left - 15:00 mins
GATE Prev Year : Theory of Computation Test-4
Attempt now to get your rank among 532 students!
Question 1
The language accepted by a Pushdown Automaton in which the stack is limited to10 items is best described as
Question 2
Let L denotes the language generated by the grammar S →0S0/00.Which of the following is true?
Question 3
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
Question 4
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 5
Consider the following decision problems:
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?
(P1) Does a given finite state machine accept a given string
(P2) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?
Question 6
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
- 532 attempts
- 3 upvotes
- 22 comments
Apr 2GATE & PSU CS
