Q. = ∈{ } w has at least as many occurrences of (110)’s as (011)’s}. Let L {w 0,1 * 2 = ∈{ } w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?
✅ Correct Answer: (B)
L2 is regular but not L1
Theory of Computation MCQs | Page - 1
Dear candidates you will find MCQ questions of Theory of Computation here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.
Q. If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
✅ Correct Answer: (C)
6
Q. If G is a connected planar graph of v vertices e edges and r regions then
✅ Correct Answer: (A)
v-e+r=2
Q. A Hamiltonian cycle in a Hamiltonian graph of order 24 has
✅ Correct Answer: (B)
24 edges
Q. The following grammar
G = (N, T, P, S)
N = {S, A, B}
T = {a, b, c}
P : S → aSa
S → aAa
A → bB
B → bB
B → c is
✅ Correct Answer: (B)
is type 2 but not type 3
Q. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = {a, b, c}
P : S → aAB
AB → CD
CD → CE
C → aC
C → b
bE → bc is
✅ Correct Answer: (C)
is type 1 but not type 2
Q. The following grammar
G = (N, T, P, S)
N = {S, A, B, C}
T = {a, b, c}
P : S → aS
A → bB
B → cC
C → a is
✅ Correct Answer: (A)
is type 3
Q. P, Q, R are three languages. If P & R are regular and if PQ=R, then
✅ Correct Answer: (C)
Q need not be regular
Q. Which of the following is true with respect to Kleene’s theorem?
1 A regular language is accepted by a finite automaton.
2 Every language is accepted by a finite automaton or a turingmachine.
✅ Correct Answer: (C)
Both 1 and 2 are true statements
Jump to