Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 2
Q21:
What is the first step in defining the language of INTEGER?
A. 0 is in INTEGER
B. 1 is in INTEGER
C. Any number is in INTEGER
D. 2 is in INTEGER
Correct Answer:
B
Chapter: 2
Q22:
In the recursive definition of EVEN, which number is initially in EVEN?
A. 1
B. 2
D. -2
Correct Answer:
B
Chapter: 2
Q23:
What is the base case for defining the factorial language?
A. 1!=0
B. n!=n*(n+1)!
C. 0!=1
D. 1!=n*(n-1)!
Correct Answer:
C
Chapter: 2
Q24:
What is the recursive step for defining the palindrome language?
A. s(x) is palindrome
B. s(Rev(s)) is palindrome
C. s(x)Rev(s) is palindrome
D. s(x)s is palindrome
Correct Answer:
C
Chapter: 2
Q25:
Which string is part of the language {a^n b^n} for n=1,2,3,… ?
A. ab
B. ba
C. aabb
D. bb
Correct Answer:
A
Chapter: 2
Q26:
How is the language of strings ending in 'a' defined?
A. By starting with b
B. By starting with a
C. By concatenating strings with a
D. By appending s(x) to a
Correct Answer:
D
Chapter: 2
Q27:
What is the defining characteristic of strings in the language containing "aa" or "bb"?
A. They contain no 'a' or 'b'
B. They contain at least two a's
C. They contain exactly one 'a'
D. They contain exactly one 'b'
Correct Answer:
B
Chapter: 3
Q28:
What does the regular expression a* represent?
A. The null string
B. All strings of "a"
C. All strings of "a", including the null string
D. Strings with exactly one "a"
Correct Answer:
C
Chapter: 3
Q29:
Which regular expression represents the language of strings having exactly one 'a'?
A. a(a+b)*
B. bab
C. (a+b)a(a+b)
D. (a+b)(a+b)
Correct Answer:
B
Chapter: 3
Q30:
What is the regular expression for a language of strings with even length?
A. (a+b)(a+b)
B. ((a+b)(a+b))*
C. a+b*
D. a*
Correct Answer:
B
Chapter: 3
Q31:
The language of strings having at least one 'a' and one 'b' can be expressed by which of the following regular expressions?
A. (a+b)*a(a+b)b(a+b)
B. aba*
C. aabb
D. (a+b)a(a+b)
Correct Answer:
A
Chapter: 3
Q32:
How is a language with strings starting with 'aa' and ending with 'bb' expressed in regular expressions?
A. aa(a+b)*bb
B. abab*
C. (a+b)aa(a+b)*
D. a(a+b)*b
Correct Answer:
A
Chapter: 3
Q33:
What does the regular expression (a+b)* represent?
A. Only strings with 'a' and 'b'
B. Strings of 'a' and 'b'
C. All possible strings of 'a' and 'b', including the null string
D. Strings with at least two 'a's
Correct Answer:
C
Chapter: 3
Q34:
What is the base step in the recursive definition of Regular Expression?
A. Every letter in Σ is an RE
B. Λ is not an RE
C. All words in Σ are not REs
D. Every string of finite length is an RE
Correct Answer:
A
Chapter: 3
Q35:
Which regular expression generates all strings starting with 'a' and ending in 'b'?
A. a(a+b)*b
B. (a+b)*a
C. aab
D. b*(a+b)*
Correct Answer:
A
Chapter: 3
Q36:
What is the recursive step for creating a regular expression from two expressions r1 and r2?
A. r1 + r2 is not a regular expression
B. r1 r2 is a regular expression
C. r1* is not a regular expression
D. (r1)(r2) is not a regular expression
Correct Answer:
B
Chapter: 3
Q37:
Which of the following represents the language of strings with odd length in regular expressions?
A. ((a+b)(a+b))*
B. (a+b)((a+b)(a+b))*
C. a(a+b)*b
D. b*(a+b)*a
Correct Answer:
B
Chapter: 3
Q38:
Fill in the blank: The regular expression ______ represents the language with at least one 'a'.
A. bab
B. (a+b)a(a+b)
C. (a+b)(a+b)*
D. aabb
Correct Answer:
B
Chapter: 3
Q39:
Fill in the blank: The recursive definition of regular expressions allows the use of _______.
A. r1 r2
B. r1 + r2
C. r1*
D. All of the above
Correct Answer:
D
Chapter: 3
Q40:
Fill in the blank: The regular expression ______ defines a language where strings start with 'aa' and end with 'bb'.
A. aa(a+b)*bb
B. (a+b)*
C. bbb
D. aba
Correct Answer:
A