1
The process of removing symbols that are never reachable from the start symbol is called:
Correct Answer
Eliminating useless symbols
☑ MCQ PRACTICE
Formal Languages and Automata Theory Unit 4
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Formal Languages and Automata Theory - Unit-4
2
A production rule of the form A → ε is called a(n):
Correct Answer
ε-production
3
In Chomsky Normal Form (CNF), every production rule must be of the form:
Correct Answer
A → BC or A → a
4
Which of the production rule can be accepted by Chomsky grammar?
Correct Answer
All of the mentioned
5
Which of the following grammars are in Chomsky Normal Form:
Correct Answer
S->AB|BC|CD, A->0, B->1, C->2, D->3
6
Greibach Normal Form (GNF) requires all productions to be of the form:
Correct Answer
A → aB₁B₂...Bₙ
7
Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.
Correct Answer
top-down parser
8
Which step is not part of converting a CFG to CNF?
Correct Answer
Introduce left recursion
9
The Pumping Lemma for CFLs states that for any CFL L, there exists a constant p such that:
Correct Answer
All of the above
10
The Pumping Lemma is primarily used to:
Correct Answer
Prove a language is not context-free
11
For the language L = {aⁿbⁿcⁿ | n ≥ 0}, the Pumping Lemma shows that:
Correct Answer
L is not context-free
12
In uvwxy partitioning, the condition |vx| ≥ 1 ensures that:
Correct Answer
At least one symbol is pumped
13
If a language fails the Pumping Lemma for CFLs, it is:
Correct Answer
Not context-free
14
CFLs are closed under:
Correct Answer
All of the above
15
CFLs are not closed under:
Correct Answer
Both A and B
16
The intersection of a CFL and a regular language is always:
Correct Answer
Context-free
17
Which operation preserves CFLs?
Correct Answer
Substitution
18
The emptiness problem for CFLs is:
Correct Answer
Decidable
19
A Turing Machine (TM) differs from a PDA because it has:
Correct Answer
An infinite tape
20
The formal definition of a TM includes all except:
Correct Answer
A stack alphabet
21
An Instantaneous Description (ID) of a TM includes:
Correct Answer
Current state, tape symbols, and head position
22
The language accepted by a TM is called:
Correct Answer
Recursively enumerable
23
A turing machine with several tapes in known as:
Correct Answer
Multi-tape turing machine