Time Left - 15:00 mins
GATE-CS Quiz on Theory of Computation
Attempt now to get your rank among 1183 students!
Question 1
S → aSa | bSb | a | b
The language generated by the above grammar over the alphabet {a, b} is the set of
The language generated by the above grammar over the alphabet {a, b} is the set of
Question 2
Which one of the following languages over the alphabet { 0, 1} is described by the regular expression:
(0 + 1) * 0 (0 + 1) * 0 (0 + 1)* ?
(0 + 1) * 0 (0 + 1) * 0 (0 + 1)* ?
Question 3
The above DFA accepts the set of all strings over {0, 1} that
Question 4
Consider the following languages.
L1={0p 1q 0r | p, q, r > 0}
L2={0p 1q 0r | p, q, r > 0, p ≠ r }
Which one of the following statements is FALSE?
L1={0p 1q 0r | p, q, r > 0}
L2={0p 1q 0r | p, q, r > 0, p ≠ r }
Which one of the following statements is FALSE?
Question 5
Which of the following is/are undecidable?
1) G is a CFG. Is L(G) = Φ?
2) G is a CFG. Is L(G) = Σ*?
3) M is a Turing machine. Is L(M) regular?
4) A is a DFA and N is an NFA. Is L(A) = L(N)?
1) G is a CFG. Is L(G) = Φ?
2) G is a CFG. Is L(G) = Σ*?
3) M is a Turing machine. Is L(M) regular?
4) A is a DFA and N is an NFA. Is L(A) = L(N)?
Question 6
The language, {ambncm+n|m,n ≥1} is
- 1183 attempts
- 5 upvotes
- 70 comments
May 21GATE & PSU CS
