Theory of Automata and Formal Languages Unit 3 – Regular and Non-Regular Grammars: AKTU previous year questions
31 AKTU questions from Unit 3 (Regular and Non-Regular Grammars) asked in 2018–2025, tagged by marks, year and topic. In short: about 27 marks of every paper come from this unit; the most asked topic is Context Free Grammar (17 times); 12 questions came back in a later year. The latest ones are listed below; on the page you can filter them by 2-mark or long questions, topic and repeats.
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)
- Convert the following CFG into Chomsky Normal Form (CNF): S → aSB | ε, B → b (7 marks, 2025, Normal Forms of CFG)
- Prove using derivation trees whether the grammar: S → aSb | ε is ambiguous or not. Explain ambiguity. (7 marks, 2025, Context Free Grammar)
- Simplify the following CFG: S → AbaC, A → BC, B → b | ε, C → D | ε, D → d (7 marks, 2025, Simplification of CFG)
- Compute the Language generated by the given CFG G = ({S}, {a, b}, P, S} where P is defined by: {S → SS, S → ab, S → ba, S → ε} (2 marks, 2024, Context Free Grammar)
- Let G be the grammar S → 0B | 1A, A → 0 | 0S | 1AA, B → 1 | 1S | 0BB. Determine the leftmost derivation for the string 00110101 (2 marks, 2024, Context Free Grammar)
- Write an equivalent left linear grammar from the given right linear grammar. S → 0A | 1B, A → 0C | 1A | 0, B → 1B | 1A | 1, C → 0 | 0A (7 marks, 2024, Regular Grammars)
- 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)
- Design a CFG for the following language: (i) L= {0m 1n | m ≠ n & m, n >= 1} (ii) L= {ap bq cr | p + q = r & p, q >= 1} (7 marks, 2024, Context Free Grammar)
Most asked Unit 3 topics
- Context Free Grammar – asked 17 times
- Normal Forms of CFG – asked 5 times
- Chomsky Hierarchy – asked 3 times
Unit 3 question pattern
- 2-mark questions: 14 asked in 2018–2025
- 7-mark questions: 12 asked in 2018–2025
- 10-mark questions: 5 asked in 2018–2025
- About 27 marks from Unit 3 in every paper
- 12 questions were asked again in a later year
Unit 3 questions year by year
- 2025: 7 Unit 3 questions asked (34 marks across that year's papers)
- 2024: 5 Unit 3 questions asked (25 marks across that year's papers)
- 2023: 5 Unit 3 questions asked (26 marks across that year's papers)
- 2022: 6 Unit 3 questions asked (36 marks across that year's papers)
- 2019: 3 Unit 3 questions asked (16 marks across that year's papers)
- 2018: 5 Unit 3 questions asked (25 marks across that year's papers)