Time Left - 15:00 mins
GATE 2018 Exam: Quiz Theory of Computation.
Attempt now to get your rank among 1190 students!
Question 1
Consider the language L given by the regular expression (a+b)*b(a+b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automation (DFA) accepting L is ______.
Question 2
Consider the following statements:
1) We can’t decide if a given context-free grammar is ambiguous.
2) We can’t decide if a given language generated by context-free grammar is finite.
Which of the above statements holds true?
1) We can’t decide if a given context-free grammar is ambiguous.
2) We can’t decide if a given language generated by context-free grammar is finite.
Which of the above statements holds true?
Question 3
Consider a language A and a Turing machine B, such that A(B) = A halts for all strings in the universe. This language is said to be?
Question 4
Consider the following statements:
1) A turing machine is more powerful than finite state machine because it has no finite state
2) A finite state machine can be assumed to be a turing machine of finite tape length without rewinding capability and unidirectional tape movement.
Which one of the above statements holds true?
1) A turing machine is more powerful than finite state machine because it has no finite state
2) A finite state machine can be assumed to be a turing machine of finite tape length without rewinding capability and unidirectional tape movement.
Which one of the above statements holds true?
Question 5
Turing-recognizable languages represent?
Question 6
Consider the following language
Which among the following strings do not belong in
?
Which among the following strings do not belong in
? Question 7
Which among the following options have built in regexps support?
Question 8
Which of the following helps in conversion of deterministic finite automata into a regular expression?
Question 9
Consider the following statements:
1) Every subset of a regular set is regular
2) Infinite union of two non regular set is regular
3) Every finite subset of non regular is regular
Which one of the above holds true?
1) Every subset of a regular set is regular
2) Infinite union of two non regular set is regular
3) Every finite subset of non regular is regular
Which one of the above holds true?
Question 10
Which among the following option pairs have different expressive power?
- 1190 attempts
- 2 upvotes
- 13 comments
Sep 15GATE & PSU CS
