1. The process of removing symbols that are never reachable from the start symbol is called:

A . Eliminating ε-productions

B . Eliminating useless symbols

C . Chomsky normalization

D . Greibach conversion

Answer

2. A production rule of the form A → ε is called a(n):

A . Useless production

B . Unit production

C . ε-production

D . Terminal production

Answer

3. In Chomsky Normal Form (CNF), every production rule must be of the form:

A . A → BC or A → a

B . A → B or A → ε

C . A → aB

D . A → α (where |α| ≤ 2)

Answer

4. Which of the production rule can be accepted by Chomsky grammar?

A . A->BC

B . A->a

C . S->e

D . All of the mentioned

Answer

5. Which of the following grammars are in Chomsky Normal Form:

A . S->AB|BC|CD, A->0, B->1, C->2, D->3

B . S->AB, S->BCA|0|1|2|3

C . S->ABa, A->aab, B->Ac

D . All of the mentioned

Answer

6. Greibach Normal Form (GNF) requires all productions to be of the form:

A . A → aB₁B₂...Bₙ

B . A → BC

C . A → ε

D . A → a

Answer

7. Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.

A . top-down parser

B . bottom-up parser

C . multitape turing machine

D . none of the mentioned

Answer

8. Which step is not part of converting a CFG to CNF?

A . Eliminate ε-productions

B . Eliminate unit productions

C . Ensure all productions are binary or terminal

D . Introduce left recursion

Answer

9. The Pumping Lemma for CFLs states that for any CFL L, there exists a constant *p* such that:

A . All strings in L can be divided into uvwxy

B . |vwx| ≤ *p* and |vx| ≥ 1

C . uvⁿwxⁿy ∈ L for all *n* ≥ 0

D . All of the above

Answer

10. The Pumping Lemma is primarily used to:

A . Prove a language is context-free

B . Prove a language is not context-free

C . Convert CFGs to PDAs

D . Eliminate useless symbols

Answer

11. For the language *L = {aⁿbⁿcⁿ | n ≥ 0}*, the Pumping Lemma shows that:

A . L is regular

B . L is context-free

C . L is not context-free

D . L is decidable

Answer

12. In uvwxy partitioning, the condition |vx| ≥ 1 ensures that:

A . The string is non-empty

B . At least one symbol is pumped

C . The string is infinite

D . The grammar is in CNF

Answer

13. If a language fails the Pumping Lemma for CFLs, it is:

A . Regular

B . Context-free

C . Not context-free

D . Recursively enumerable

Answer

14. CFLs are closed under:

A . Union

B . Concatenation

C . Kleene star

D . All of the above

Answer

15. CFLs are not closed under:

A . Intersection

B . Complement

C . Both A and B

D . Homomorphism

Answer

16. The intersection of a CFL and a regular language is always:

A . Regular

B . Context-free

C . Context-sensitive

D . Undecidable

Answer

17. Which operation preserves CFLs?

A . Intersection with another CFL

B . Complementation

C . Substitution

D . None of the above

Answer

18. The emptiness problem for CFLs is:

A . Undecidable

B . Decidable

C . NP-complete

D . Only decidable for DCFLs

Answer

19. A Turing Machine (TM) differs from a PDA because it has:

A . An infinite tape

B . A stack

C . Finite states

D . ε-transitions

Answer

20. The formal definition of a TM includes all except:

A . A finite set of states

B . An input alphabet

C . A stack alphabet

D . A transition function

Answer

21. An Instantaneous Description (I of a TM includes:

A . Current state, tape symbols, and head position

B . Only the tape contents

C . The transition function

D . The set of final states

Answer

22. The language accepted by a TM is called:

A . Regular

B . Context-free

C . Recursively enumerable

D . All of the above

Answer

23.A turing machine with several tapes in known as:

A . Multi-tape turing machine

B . Poly-tape turing maching

C . Universal turing machine

D . All of the mentioned

Answer

---

Relevant Materials :

☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-1 - [ FLAT ]

☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-2 - [ FLAT ]

☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-3 - [ FLAT ]

☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-4 - [ FLAT ]

☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-5 - [ FLAT ]

---

Similar Materials :

☞ R - Programming MCQs - Unit-1 - [ R-Programming ]

☞ R - Programming MCQs - Unit-2 - [ R-Programming ]

☞ R - Programming MCQs - Unit-3 - [ R-Programming ]

☞ R - Programming MCQs - Unit-4 - [ R-Programming ]

☞ R - Programming MCQs - Unit-5 - [ R-Programming ]

☞ Artificial Intelligence (AI) MCQs - Unit-1 - [ Artificial Intelligence ]

☞ Artificial Intelligence (AI) MCQs - Unit-2 - [ Artificial Intelligence ]

☞ Artificial Intelligence (AI) MCQs - Unit-3 - [ Artificial Intelligence ]

☞ Artificial Intelligence (AI) MCQs - Unit-4 - [ Artificial Intelligence ]

☞ Artificial Intelligence (AI) MCQs - Unit-5 - [ Artificial Intelligence ]

☞ PPS MCQs - Unit-1 - [ PPS ]

☞ PPS MCQs - Unit-2 - [ PPS ]

☞ PPS MCQs - Unit-3 - [ PPS ]

☞ PPS MCQs - Unit-4 - [ PPS ]

☞ PPS MCQs - Unit-5 - [ PPS ]

☞ Object Oriented Programming through Java MCQs - Unit-1 - [ OOP_JAVA ]

☞ Object Oriented Programming through Java MCQs - Unit-2 - [ OOP_JAVA ]

☞ Object Oriented Programming through Java MCQs - Unit-3 - [ OOP_JAVA ]

☞ Object Oriented Programming through Java MCQs - Unit-4 - [ OOP_JAVA ]

☞ Object Oriented Programming through Java MCQs - Unit-5 - [ OOP_JAVA ]

☞ Design and Analysis of Algorithms MCQs - Unit-1 - [ DAA ]

☞ Design and Analysis of Algorithms MCQs - Unit-2 - [ DAA ]

☞ Design and Analysis of Algorithms MCQs - Unit-3 - [ DAA ]

☞ Design and Analysis of Algorithms MCQs - Unit-4 - [ DAA ]

☞ Design and Analysis of Algorithms MCQs - Unit-5 - [ DAA ]

☞ Software Engineering MCQs - Unit-1 - [ SE ]

☞ Software Engineering MCQs - Unit-2 - [ SE ]

☞ Software Engineering MCQs - Unit-3 - [ SE ]

☞ Software Engineering MCQs - Unit-4 - [ SE ]

☞ Software Engineering MCQs - Unit-5 - [ SE ]

☞ Data Mining MCQs - Unit-1 - [ DM ]

☞ Data Mining MCQs - Unit-2 - [ DM ]

☞ Data Mining MCQs - Unit-3 - [ DM ]

☞ Data Mining MCQs - Unit-4 - [ DM ]

☞ Data Mining MCQs - Unit-5 - [ DM ]

☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-1 - [ COA ]

☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-2 - [ COA ]

☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-3 - [ COA ]

☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-4 - [ COA ]

☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-5 - [ COA ]

☞ Data Structures Objective Type Question Bank-Unit-1 - [ DS ]

☞ Data Structures Objective Type Question Bank-Unit-2 - [ DS ]

☞ Data Structures Objective Type Question Bank-Unit-3 - [ DS ]

☞ Data Structures Objective Type Question Bank-Unit-4 - [ DS ]

☞ Data Structures Objective Type Question Bank-Unit-5 - [ DS ]

☞ Database Management System Objective Type Question Bank-Unit-1 - [ DBMS ]

☞ Database Management System Objective Type Question Bank-Unit-2 - [ DBMS ]

☞ Database Management System Objective Type Question Bank-Unit-3 - [ DBMS ]

☞ Database Management System Objective Type Question Bank-Unit-4 - [ DBMS ]

☞ Database Management System Objective Type Question Bank-Unit-5 - [ DBMS ]