Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 42
Q521:
What is the net effect of a path segment Net(READx, READy, w) → RowiNet(READy, S1, m1) … Net(Sn1, Sn, mn)?
A. The path segment pushes characters to the STACK only
B. The path segment pops exactly one letter from the STACK
C. The path segment pops and pushes multiple letters
D. The path segment changes the initial state of the PDA
Correct Answer:
B
Chapter: 42
Q522:
In the context of CFG productions for Row language, which of the following is true?
A. Productions can be defined only using nonterminals
B. Productions may include both nonterminals and terminals
C. Productions are only defined by terminals
D. Productions are not allowed in CFGs
Correct Answer:
C
Chapter: 42
Q523:
Which of the following rules helps in creating all possible productions for CFG of the row language?
A. Rule1: Net(START, ACCEPT, $) → S
B. Rule2: Net(X, Y, Z) → Rowi
C. Rule3: Net(READx, Sn, w) → RowiNet(READy, S1, m1) … Net(Sn1, Sn, mn)
D. All of the above
Correct Answer:
D
Chapter: 42
Q524:
What type of consistency must a sequence of rows have to be considered valid in the Row language?
A. Joint and STACK consistency
B. Alphabet and Syntax consistency
C. Semantic and Context consistency
D. None of the above
Correct Answer:
A
Chapter: 42
Q525:
Fill in the blank: The shortest word in the whole row language for the given PDA is ____.
A. Row1Row2Row3Row4Row5Row7
B. Row1Row2Row3Row4Row5
C. Row1Row2Row3Row4Row7
D. Row1Row2Row3Row7
Correct Answer:
A
Chapter: 42
Q526:
Which of the following correctly represents the effect of the production Net(READ1, READ2, $) → Row2Net(READ1, READ1, a)?
A. It adds characters to the STACK
B. It pops characters from the STACK
C. It performs no STACK operations
D. It transitions from READ1 to READ2 without changing the STACK
Correct Answer:
C
Chapter: 42
Q527:
In the CFG for the row language of the PDA accepting {a2nbn : n=1, 2, 3, …}, which row is represented by the production Net(READ1, READ2, a) → Row3Net(READ1, READ1, a)Net(READ1, READ2, a)?
A. Row3
B. Row2
C. Row4
D. Row5
Correct Answer:
A
Chapter: 42
Q528:
Fill in the blank: The nonterminal Net(READ1, ACCEPT, $) in the CFG corresponds to production ____.
A. Row7
B. Row6
C. Row5
D. Row4
Correct Answer:
A
Chapter: 43
Q529:
What are languages that are not Context-Free called?
A. NonCFL
B. ContextFree
C. DeadProduction
D. LiveProduction
Correct Answer:
A
Chapter: 43
Q530:
What type of production increases the number of nonterminals by one?
A. Dead Production
B. Self Embedded Production
C. Live Production
D. Terminal Production
Correct Answer:
C
Chapter: 43
Q531:
A production of the form nonterminal → terminal is known as a _______ production.
A. Live
B. Dead
C. Self Embedded
D. Finite
Correct Answer:
B
Chapter: 43
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
Correct Answer:
A
Chapter: 43
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)
Correct Answer:
B
Chapter: 43
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
Correct Answer:
A
Chapter: 43
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
Correct Answer:
A
Chapter: 43
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
Correct Answer:
A
Chapter: 43
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,…}
Correct Answer:
A
Chapter: 43
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
Correct Answer:
A
Chapter: 43
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
Correct Answer:
A
Chapter: 43
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
Correct Answer:
A