Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q551: What is the problem of emptiness in context-free grammars (CFG)?
- A: Determining if CFG generates any word
- B: Checking if CFG generates a finite language
- C: Testing if a given string can be generated
- D: Finding the membership of a string
View Answer
A
Q552: Which algorithm determines if a CFG generates any word?
- A: Algorithm 1
- B: Algorithm 2
- C: Algorithm 3
- D: Algorithm 4
View Answer
A
Q553: What is the main purpose of Algorithm 2 in CFG?
- A: To find useless nonterminals
- B: To determine finiteness of CFG
- C: To check the membership of a string
- D: To determine CFG generates any word
View Answer
A
Q554: In Algorithm 1, what happens if the CFG contains the production S→Λ?
- A: CFG is empty
- B: CFG is non-empty
- C: CFG is finite
- D: CFG generates infinite language
View Answer
B
Q555: How can you determine if a nonterminal X is ever used in the derivation of a word in CFG?
- A: By finding productive nonterminals
- B: By checking self-embedded nonterminals
- C: By identifying useless nonterminals
- D: By eliminating unproductive nonterminals
View Answer
C
Q556: What does the CYK algorithm determine?
- A: Whether a string can be generated by CFG
- B: Whether CFG is empty
- C: Whether CFG is finite
- D: Whether CFG is productive
View Answer
A
Q557: In the CYK algorithm, what is the first step?
- A: Convert CFG to CNF
- B: List nonterminals for substrings
- C: List nonterminals generating single letter substrings
- D: Determine if CFG generates any word
View Answer
A
Q558: What does self-embedded mean in the context of CFG?
- A: A nonterminal can generate a string including itself
- B: A nonterminal is not used in any production
- C: A nonterminal is unproductive
- D: A CFG generates a finite language
View Answer
A
Q559: For which CFG production is the algorithm for checking finiteness used?
- A: S→AA
- B: S→a
- C: S→ABa
- D: S→Aba
View Answer
C
Q560: In top-down parsing, what is the starting point?
- A: Nonterminal S
- B: Terminal symbols
- C: Production rules
- D: Derivation tree
View Answer
A