Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q531: A production of the form nonterminal → terminal is known as a _______ production.
- A: Live
- B: Dead
- C: Self Embedded
- D: Finite
View Answer
B
Q532: In a CFG in CNF, applying a live production how many times increases the number of nonterminals by one?
- A: Once
- B: Twice
- C: Thrice
- D: Four times
View Answer
A
Q533: If a CFG in CNF has p live and q dead productions, what is the maximum number of letters in a generated word without repeating any live production?
- A: 2p
- B: (p+1)
- C: 2q
- D: (p+q)
View Answer
B
Q534: For a CFG in CNF with p live and q dead productions, what happens if a word has more than 2p letters?
- A: It always has a nonterminal used twice
- B: No nonterminals used twice
- C: Nonterminals are used exactly once
- D: Nonterminals are used in pairs
View Answer
A
Q535: What does the Pumping Lemma for CFLs state about words of length more than 2p?
- A: They can be decomposed into five substrings with x not null and v, y not both null.
- B: They can be decomposed into three substrings where v and y are both non-empty.
- C: They can be decomposed into two substrings with x null.
- D: They cannot be decomposed at all
View Answer
A
Q536: In the Pumping Lemma for CFLs, what must be true for substrings v and y?
- A: They are both not null.
- B: They are both null.
- C: They are both single letters.
- D: One must be null and one must not be null
View Answer
A
Q537: Which language does the Pumping Lemma show to be non-CFL if it can't be decomposed into the required form?
- A: L={anbncn :n=1,2,3,…}
- B: L={anbn : n=1,2,3,…}
- C: L={a^n : n=1,2,3,…}
- D: L={a^n b^n : n=1,2,3,…}
View Answer
A
Q538: The Pumping Lemma for regular languages does not hold for non-regular languages because they do not contain both _______ and _______.
- A: xyz, xyyz
- B: uvxyz, uvvxyyz
- C: xy, xyy
- D: z, yz
View Answer
A
Q539: The CFG for the language EVENA is defined as _______.
- A: S → SS|aa, A → a
- B: S → a, A → b
- C: S → SS|b, A → a
- D: S → a, A → b
View Answer
A
Q540: Which of the following is a characteristic of the Pumping Lemma for CFLs compared to regular languages?
- A: It acts on algebraic structures such as grammar.
- B: It acts on machines.
- C: It only applies to finite languages.
- D: It is not applicable to infinite languages
View Answer
A