Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 6
Q81:
The language of strings containing double 'a' over Σ = {a, b} is expressed by:
A. a(a + b)*
B. (a + b)aa(a + b)
C. (a + b)*a
D. a(a + b)*a
Correct Answer:
B
Chapter: 6
Q82:
What does the regular expression (0+1)* (00 + 11) (0+1)* represent?
A. Strings of odd length
B. Strings with double 0's or double 1's
C. Strings starting with 0 or 1
D. Strings containing at least one 0
Correct Answer:
B
Chapter: 6
Q83:
The regular expression for strings containing triple 'a's or triple 'b's over Σ = {a, b} is:
A. (a+b)aaa(a+b)
B. (a+b)bbb(a+b)
C. a(a+b)
D. (a+b)(aaa + bbb)(a+b)
Correct Answer:
D
Chapter: 6
Q84:
Which of the following regular expressions represents the EVEN-EVEN language over Σ = {a, b}?
A. (aa+bb+(ab+ba)(aa+bb)(ab+ba))
B. (ab+ba)(aa+bb)*
C. aa+bb
D. (aa + bb)*
Correct Answer:
A
Chapter: 6
Q85:
Fill in the blank: The language of strings over Σ = {a, b} that starts with 'a' and ends with 'b' can be expressed as _____.
A. a(a + b)*b
B. (a + b)*b
C. a(a+b)+
D. a(b + a)*
Correct Answer:
A
Chapter: 6
Q86:
The finite automaton (FA) accepting all non-empty strings over Σ = {a, b} can be expressed by the regular expression:
A. (a + b)*
B. (a + b)+
C. (a)*b
D. (b)*a
Correct Answer:
B
Chapter: 6
Q87:
What is the difference between FA1 and FA3 if both accept the same language?
A. FA1 has fewer states than FA3
B. FA3 is disconnected
C. FA1 has no final state
D. FA3 has fewer transitions than FA1
Correct Answer:
B
Chapter: 6
Q88:
Which of the following FA accepts the language containing triple a's or triple b's over Σ = {a, b}?
A. FA1
B. FA2
C. FA3
D. FA4
Correct Answer:
C
Chapter: 6
Q89:
Fill in the blank: A disconnected FA is one where _____.
A. No path exists between states
B. All states are connected
C. It accepts only empty strings
D. It rejects all input strings
Correct Answer:
A
Chapter: 6
Q90:
The language L defined over Σ = {a, b} containing no string is represented by:
A. Empty set (Ø)
B. Null set (Λ)
C. (a + b)*
D. a(a + b)*
Correct Answer:
A
Chapter: 6
Q91:
What is the regular expression for the language of strings that contains at least one occurrence of 'aa' over Σ = {a, b}?
A. (a+b)aa(a+b)
B. aa(a+b)
C. (a + b)*a
D. a(a + b)*a
Correct Answer:
A
Chapter: 7
Q92:
What is the regular expression for the language L = {Λ, b, ab, bb}, defined over Σ = {a, b}?
A. Λ + b + ab + bb
B. ab + bb + aa
C. a + b
D. Λ + a + b
Correct Answer:
A
Chapter: 7
Q93:
In an FA, what are dead states also referred to as?
A. Final states
B. Start states
C. Davey John Lockers
D. Transition states
Correct Answer:
C
Chapter: 7
Q94:
Which structure can help build an FA for a language with fewer strings?
A. Tree structure
B. Graph structure
C. FA diagram
D. Finite transition table
Correct Answer:
A
Chapter: 7
Q95:
The regular expression for the language L = {aa, bab, aabb, bbba}, defined over Σ = {a, b}, is:
A. aa + bb + ab
B. aa + bab + aabb + bbba
C. ab + bba + aa
D. ab + bb
Correct Answer:
B
Chapter: 7
Q96:
The language L = {w belongs to {a,b}*: length(w) ≥ 2 and w neither ends in aa nor bb} is expressed by:
A. (a + b)* (ab + ba)
B. (a + b) + aa + bb
C. ab + ba + bb
D. (a+b) (bb+ab)
Correct Answer:
A
Chapter: 7
Q97:
What is the purpose of a transition graph (TG) in FA?
A. Shows input letters
B. Defines states
C. Shows state transitions
D. Displays null strings
Correct Answer:
C
Chapter: 7
Q98:
A transition graph (TG) consists of which of the following?
A. Finite number of states
B. Infinite states
C. Infinite number of input letters
D. Null strings only
Correct Answer:
A
Chapter: 7
Q99:
What is the regular expression for the language L = {w belongs to {a,b}*: w does not end in aa}?
A. a + b + Λ
B. Λ + a + b + (a+b)* (ab+ba+bb)
C. ab + ba + bb
D. (a + b)* aa
Correct Answer:
B
Chapter: 7
Q100:
Which of the following states does not have a final state in the FA corresponding to L = {Λ, b, ab, bb}?
A. State 1
B. State x
C. State 5
D. State 4
Correct Answer:
B