Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 31
Q401:
Which grammar defines the language expressed by (a+b)aa(a+b)?
A. S → SS
B. S → XaaX
C. S → a
D. S → a+b
Correct Answer:
B
Chapter: 31
Q402:
In CFG, what is the role of terminal symbols?
A. Must be replaced
B. Can’t be replaced
C. Can be either replaced or deleted
D. Only generate non-terminals
Correct Answer:
B
Chapter: 31
Q403:
What type of language is expressed by S → aS, S → bS, S → Λ?
A. Regular Language
B. Context-Free Language
C. Infinite Language
D. Finite Language
Correct Answer:
B
Chapter: 31
Q404:
Which type of string is generated by the grammar Σ = {a, b} and productions X → aX, X → bX, X → Λ?
A. Finite strings of a’s and b’s
B. Infinite strings of a’s
C. Only one string
D. Empty strings
Correct Answer:
A
Chapter: 31
Q405:
Context-Free Grammars (CFGs) primarily deal with which of the following?
A. Syntax
B. Semantics
C. Machine Learning
D. Assembly Language
Correct Answer:
A
Chapter: 31
Q406:
Fill in the blank: A Context-Free Language is generated by a ____.
A. DFA
B. CFG
C. PDA
D. Turing Machine
Correct Answer:
B
Chapter: 31
Q407:
Fill in the blank: The symbols in CFG that must be replaced by other things are called ____.
A. Nonterminals
B. Terminals
C. Productions
D. Syntax
Correct Answer:
A
Chapter: 31
Q408:
Fill in the blank: In CFG, the rule S → Λ means that S can be ____.
A. replaced by a
B. deleted from the string
C. used as a terminal
D. used as a nonterminal
Correct Answer:
B
Chapter: 31
Q409:
Fill in the blank: The rule S → aS generates the language expressed by ____.
A. a*
B. b*
C. a+b
D. (a+b)*
Correct Answer:
A
Chapter: 32
Q410:
What does the CFG with productions S → SS, S → XS, S → Λ, X → aa, X → bb, Y → ab, Y → ba generate?
A. EVEN language
B. EQUAL language
C. PALINDROME
D. EVEN EVEN language
Correct Answer:
D
Chapter: 32
Q411:
In the grammar for EVEN EVEN language, which nonterminal generates the string "aa"?
A. S
B. X
C. Y
D. Λ
Correct Answer:
B
Chapter: 32
Q412:
Which production defines the language where the number of 'a's equals the number of 'b's?
A. S → SS
B. S → aB
C. S → YXY
D. S → aSb
Correct Answer:
B
Chapter: 32
Q413:
What is generated by the production S → aB in the EQUAL language?
A. A string with unequal number of 'a's and 'b's
B. A string with equal number of 'a's and 'b's
C. A palindrome
D. An empty string
Correct Answer:
B
Chapter: 32
Q414:
Which CFG production generates strings of type baab?
A. S → aXb
B. S → AA
C. S → aSa
D. S → bSb
Correct Answer:
B
Chapter: 32
Q415:
The language generated by the CFG S → aB, S → bA is called the ________ language.
A. EVEN
B. PALINDROME
C. EQUAL
D. CLOSED
Correct Answer:
C
Chapter: 32
Q416:
The CFG S → YXY, X → bbb generates the language expressed by ________.
A. (a+b)bbb(a+b)
B. (a+b)+
C. babab*
D. {anbn}
Correct Answer:
A
Chapter: 32
Q417:
In CFG, terminals are designated by ________ letters.
A. Small
B. Capital
C. Greek
D. Italic
Correct Answer:
A
Chapter: 33
Q418:
In Polish notation, how is the arithmetic expression 3+4*5 written?
A. *3+4 5
B. 3+*4 5
C. +3*4 5
D. *+3 4 5
Correct Answer:
C
Chapter: 33
Q419:
Which operator notation starts with the operator followed by operands?
A. Prefix notation
B. Infix notation
C. Postfix notation
D. Suffix notation
Correct Answer:
A
Chapter: 33
Q420:
The expression *+*+1 2+3 4 5 6 in infix form is equivalent to?
A. (((1+2)*(3+4))+5)*6
B. +1 2(3+4) 5 6
C. (1+2)(3+(45))
D. *(((1+2)+(3+4)) 5 6
Correct Answer:
A