Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 43
Q541:
A nonterminal is considered self-embedded if it occurs as a _______ in its own derivation tree.
A. Parent
B. Node
C. Descendant
D. Child
Correct Answer:
C
Chapter: 43
Q542:
Theorem states that if a CFG is in CNF with p live productions, every word of length more than 2p can be decomposed as _______.
A. w = uvxyz
B. w = uvwxy
C. w = xyzw
D. w = uvwz
Correct Answer:
B
Chapter: 43
Q543:
In the example CFG provided, what is the CFG in CNF for the language EVENA?
A. S → SS|aa, A → a
B. S → a, A → b
C. S → SS|bb, A → a
D. S → a, A → b
Correct Answer:
A
Chapter: 43
Q544:
A CFG in CNF can generate a word with more than 2p letters if it is decomposed into _______.
A. uvxyz, where v and y are not both null.
B. xyz, where y is null.
C. uv, where x and z are both null.
D. w, where v is null.
Correct Answer:
A
Chapter: 43
Q545:
The theorem on self-embedded nonterminals deals with a nonterminal that appears as a _______ of itself.
A. Descendant
B. Parent
C. Sibling
D. Child
Correct Answer:
A
Chapter: 43
Q546:
In the CFG for the language L={anbncn :n=1,2,3,…}, the word a200b200c200 of length more than 2p shows that it _______.
A. Satisfies the pumping lemma
B. Does not satisfy the pumping lemma
C. Satisfies regular language pumping lemma
D. Can be decomposed into xyz
Correct Answer:
B
Chapter: 43
Q547:
The theory of Automata includes the study of which types of languages?
A. Context-Free Languages and Non-Context-Free Languages
B. Only Context-Free Languages
C. Only Regular Languages
D. Only Non-Context-Free Languages
Correct Answer:
A
Chapter: 43
Q548:
A CFG that has a production of the form nonterminal → string of two nonterminals is called a _______ production.
A. Live
B. Dead
C. Self Embedded
D. Terminal
Correct Answer:
A
Chapter: 43
Q549:
In the given CFG example, the derivation tree for the word bbabbb shows that the word can be decomposed into _______.
A. uvxyz, where u = a, v = Λ, x = b, y = ab, z = Λ
B. w = uvxyz
C. xyz
D. uvx
Correct Answer:
B
Chapter: 43
Q550:
The CFG in CNF that generates the language {anbmanbm :m,n=1,2,3,…} is checked using which version of the Pumping Lemma for CFLs?
A. Second version
B. First version
C. Regular language version
D. Non-context-free version
Correct Answer:
A
Chapter: 44
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
Correct Answer:
A
Chapter: 44
Q552:
Which algorithm determines if a CFG generates any word?
A. Algorithm 1
B. Algorithm 2
C. Algorithm 3
D. Algorithm 4
Correct Answer:
A
Chapter: 44
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
Correct Answer:
A
Chapter: 44
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
Correct Answer:
B
Chapter: 44
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
Correct Answer:
C
Chapter: 44
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
Correct Answer:
A
Chapter: 44
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
Correct Answer:
A
Chapter: 44
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
Correct Answer:
A
Chapter: 44
Q559:
For which CFG production is the algorithm for checking finiteness used?
A. S→AA
B. S→a
C. S→ABa
D. S→Aba
Correct Answer:
C
Chapter: 44
Q560:
In top-down parsing, what is the starting point?
A. Nonterminal S
B. Terminal symbols
C. Production rules
D. Derivation tree
Correct Answer:
A