TAFL Unit 3 Handwritten Notes AKTU (BCS402)

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Unit 3 · Handwritten Notes

AKTU Theory of Automata and Formal Languages (BCS402) Unit 3 handwritten notes for B.Tech Semester 4 – Regular and Non-Regular Grammars. Topics: Context…

A preview is available. Sign in or check access options in the reader for the complete resource.

Unit 3: Regular and Non-Regular Grammars – AKTU syllabus topics

  • Context Free Grammar: Derivations and Derivation Trees, Ambiguity in CFG
  • Regular Grammars: Right Linear Grammar, Left Linear Grammar
  • FA and Regular Grammar Conversion: FA into CFG Conversion, Regular Grammar into FA
  • Simplification of CFG
  • Normal Forms of CFG: Chomsky Normal Form, Greibach Normal Form
  • Chomsky Hierarchy

Most asked AKTU PYQ questions from Unit 3

  1. Q5a. Convert the following CFG into Chomsky Normal Form (CNF): S → aSB | ε, B → b (7 marks, 2024-25)
  2. Q5b. Prove using derivation trees whether the grammar: S → aSb | ε is ambiguous or not. Explain ambiguity. (7 marks, 2024-25)
  3. Q5a. 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, 2023-24)
  4. Q1d. What is the ambiguity in Context-Free Grammars (CFGs)? (2 marks, 2024-25)
  5. Q1f. Find whether the following grammar is ambiguous or not: S → S*S | S+S | a (2 marks, 2024-25)
  6. Q1f. Explain Chomsky Hierarchy. (2 marks, 2022-23)
  7. Q2c. Consider the grammar with following production rules: S→ABD | AC, A→aA | bAa | a, B→bbA | aB | AB, C→aCa | aD, D→aD | bC. Convert the above grammar into Chomsky Normal Form. (10 marks, 2022-23)
  8. Q5a. A context free grammar G is given by the following productions: E→E+E|E-E|E*E|E^E|N, N→0|1|2|3|4|5|6|7|8|9. Determine whether the grammar G is ambiguous or not. If ambiguous then construct an unambiguous grammar equivalent to G. (10 marks, 2022-23)
  9. Q2c. Give the Complete description about the Chomsky Hierarchy. (10 marks, 2021-22)
  10. Q6a. Simplify the following CFG: S → AbaC, A → BC, B → b | ε, C → D | ε, D → d (7 marks, 2024-25)

AKTU paper codes: BCS402, KCS402, RCS403

Other Theory of Automata and Formal Languages units

Theory of Automata and Formal Languages previous year papers

Browse all notes · Semester 4 notes