Theory of Automata and Formal Languages Unit 3 – Regular and Non-Regular Grammars: important questions for AKTU
Unit 3 (Regular and Non-Regular Grammars) questions that AKTU repeats most often. This unit carries about 27 marks per paper. Start with the repeated questions, then the most asked topics.
Most repeated Unit 3 questions
- Convert the following CFG into Chomsky Normal Form (CNF): S → aSB | ε, B → b (7 marks, 2025, Normal Forms of CFG) – also asked in 2018, 2019, 2023, 2024
- Prove using derivation trees whether the grammar: S → aSb | ε is ambiguous or not. Explain ambiguity. (7 marks, 2025, Context Free Grammar) – also asked in 2018, 2022, 2023
- Reduce the given grammar G = ({S, A, B}, {a, b}, P, S) to Chomsky Normal form. Where P is defined by: S → bA | aB, A → bAA | aS | a, B → aBB | bS | b (7 marks, 2024, Normal Forms of CFG) – also asked in 2018, 2019, 2023
Most important Unit 3 topic
- Context Free Grammar (Unit 3: Regular and Non-Regular Grammars) – asked 17 times in 2018, 2019, 2022, 2023, 2024, 2025
Most asked Unit 3 topics
- Context Free Grammar – asked 17 times
- Normal Forms of CFG – asked 5 times
- Chomsky Hierarchy – asked 3 times
More Unit 3 previous year questions
- What is the ambiguity in Context-Free Grammars (CFGs)? (2 marks, 2025, Context Free Grammar)
- Construct a CFG for the language L = {aⁿbⁿ | n ≥ 0}. (2 marks, 2025, Context Free Grammar)
- Find whether the following grammar is ambiguous or not: S → S*S | S+S | a (2 marks, 2025, Context Free Grammar)
- Convert the following regular grammar to a Finite Automaton: S → aA | bB, A → aS | a, B → bS | b (7 marks, 2025, FA and Regular Grammar Conversion)
- Simplify the following CFG: S → AbaC, A → BC, B → b | ε, C → D | ε, D → d (7 marks, 2025, Simplification of CFG)
Unit 3 syllabus topics
- Context Free Grammar
- Regular Grammars
- FA and Regular Grammar Conversion
- Simplification of CFG
- Normal Forms of CFG
- Chomsky Hierarchy