Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 9
Q121:
Which regular expression represents the language containing triple 'a' or triple 'b'?
A. (a+b)(aa + bb)(a+b)
B. (a+b)(aaa + bbb)(a+b)
C. (a+b)(ab+ba)(a+b)*
D. (a+b)+aa+bb+(a+b)*
Correct Answer:
B
Chapter: 9
Q122:
What does the regular expression a(a + b)*b + b(a + b)*a represent?
A. Strings beginning and ending in different letters
B. Strings containing double 'a'
C. Strings starting with 'b'
D. Strings with an even number of 'a's
Correct Answer:
A
Chapter: 9
Q123:
The regular expression a(a + b)*a + b(a + b)*b represents which language?
A. Strings starting with 'b'
B. Strings with odd-length
C. Strings of length two or more, beginning and ending in the same letter
D. Strings containing triple 'a'
Correct Answer:
C
Chapter: 9
Q124:
The EVENEVEN language can be expressed by which of the following regular expressions?
A. (aa+bb+(ab+ba)(aa+bb)(ab+ba))
B. (aa+ab)*
C. (a+b)(aa+bb)(a+b)
D. (ab)(aa+bb)*
Correct Answer:
A
Chapter: 9
Q125:
In the EVENEVEN language, what condition is met?
A. Strings containing exactly two 'a's
B. Strings with an even number of 'a's and 'b's
C. Strings that end in 'bb'
D. Strings starting with 'a'
Correct Answer:
B
Chapter: 9
Q126:
What does the expression (aa)b(b+(aa(aa)b)) bb represent?
A. Strings containing only 'a'
B. Strings where 'a' occurs in even clumps and ends in three or more 'b's
C. Strings beginning with 'b'
D. Strings starting and ending with different letters
Correct Answer:
B
Chapter: 9
Q127:
How many successful paths are traced by the string abbbabbbabba in the given TG example?
A. 1
B. 2
C. 3
D. 4
Correct Answer:
C
Chapter: 9
Q128:
What is a Generalized Transition Graph (GTG) made up of?
A. Finite number of states
B. Infinite input set
C. Regular expressions on transitions
D. Both A and C
Correct Answer:
D
Chapter: 9
Q129:
In a GTG, what is the label of a transition edge typically associated with?
A. A state
B. An input letter
C. A regular expression
D. A final state
Correct Answer:
C
Chapter: 9
Q130:
What is true about the string abbbabbbabba in the given TG example?
A. It is rejected by the TG
B. It is accepted by the TG
C. It traces only one path
D. It does not contain 'a'
Correct Answer:
B
Chapter: 9
Q131:
Which of the following regular expressions represents strings starting and ending with different letters?
A. a(a+b)*a + b(a+b)*b
B. a(a+b)*b + b(a+b)*a
C. (a+b)*(aaa + bbb)
D. (a+b)(aa + bb)(a+b)
Correct Answer:
B
Chapter: 10
Q132:
Which regular expression represents the language containing double 'a' or double 'b'?
A. (a+b)* (aaa + bbb) (a+b)*
B. (a+b)* (aa + bb) (a+b)*
C. (a+b)(ab+ba)(a+b)*
D. (ab) (aa + bb) (ab)
Correct Answer:
B
Chapter: 10
Q133:
What does the regular expression a(a+b)*b + b(a+b)*a represent?
A. Strings containing triple 'a'
B. Strings with double 'b'
C. Strings beginning and ending in different letters
D. Strings starting with 'a' and ending with 'a'
Correct Answer:
C
Chapter: 10
Q134:
The regular expression (a+b)* (aaa + bbb) (a+b)* represents which language?
A. Strings containing triple 'a' or triple 'b'
B. Strings beginning and ending with same letter
C. Strings with only one 'a'
D. Strings with alternating 'a' and 'b'
Correct Answer:
A
Chapter: 10
Q135:
Which property of TGs and GTGs creates nondeterminism?
A. Existence of multiple start states
B. Lack of final state
C. Existence of multiple paths for a string
D. Presence of a regular expression
Correct Answer:
C
Chapter: 10
Q136:
What is true about Kleene’s Theorem Part I?
A. A TG can accept a language expressed by an RE
B. An FA can accept a language expressed by an RE
C. If a language can be accepted by an FA, it can also be accepted by a TG
D. If a language can be accepted by a TG, it can also be accepted by an FA
Correct Answer:
C
Chapter: 10
Q137:
Which part of Kleene’s Theorem states that a language accepted by a TG can be expressed by a regular expression?
A. Part I
B. Part II
C. Part III
D. Part IV
Correct Answer:
B
Chapter: 10
Q138:
According to Kleene’s Theorem Part III, if a language can be expressed by a regular expression, what else is true?
A. It can be accepted by an FA
B. It can be accepted by a TG
C. It can be expressed by another RE
D. It cannot be accepted by an FA
Correct Answer:
A
Chapter: 10
Q139:
In nondeterministic TGs, what differentiates them from finite automata (FAs)?
A. Absence of a final state
B. Multiple transition graphs
C. Existence of multiple paths
D. Only one path exists
Correct Answer:
C
Chapter: 10
Q140:
What is the starting state of a generalized transition graph (GTG)?
A. Initial state
B. Final state
C. Regular expression
D. Transition edge
Correct Answer:
A