📚

Understanding Gback Normal Form Conversion

Apr 5, 2025

Lecture Notes: Gback Normal Form

Introduction to Gback Normal Form

  • Context-Free Grammar (CFG): A CFG is in Gback Normal Form if the productions are in the following forms:
    • A → b
    • A → b C1 C2 ... CN
    • Where A, C1 ... CN are non-terminals and b is a terminal.
  • Forms of Gback Normal Form:
    • A non-terminal gives a terminal symbol.
    • A non-terminal gives a terminal symbol followed by non-terminals.

Steps to Convert CFG to Gback Normal Form

  1. **Remove Unit and Null Productions: **

    • Check for unit productions or null productions.
    • Remove them using techniques discussed in previous lectures.
  2. Check for Chomsky Normal Form (CNF):

    • Verify if CFG is already in CNF.
    • Convert to CNF if not, using methods from previous lectures.
  3. **Rename Non-Terminal Symbols: **

    • Change names of non-terminal symbols to A1, A2, etc., in ascending order.
    • Example given:
      • S → A1, C → A2, a → A3, B → A4.
  4. **Ensure Productions are in Ascending Order: **

    • Form: AI → AJ X, where I < J.
    • Ensure order: I should always be less than J.

Example and Conversion Process

  • Example CFG:
    • S gives CA, BB
    • B gives b, SB
    • C gives b
    • A gives a
  • Steps followed on example:
    • No unit or null productions found.
    • Already in CNF, proceed to change non-terminals.
    • Replace S, C, A, B with A1, A2, A3, A4.

Resolving Issues in Conversion

  • Issue Identification:
    • Problems arise if I ≥ J in AI → AJ X.
    • Example: A4 → A1 A4, where I (4) > J (1).
  • Resolution Technique:
    • Replace problematic variables with correct values based on previous substitutions.
    • Example resolution:
      • A4 → B A2 A3 A4 is converted correctly.

Addressing Left Recursion

  • If I = J (left recursion), need to resolve.
  • Left Recursion Example: A4 gives A4 A4 A4.
  • Next Steps:
    • Lecture ends with a plan to remove left recursion in further lectures.

Conclusion

  • Summary: Steps 1 to 4 are crucial for converting CFG to Gback Normal Form.
  • Upcoming: Next lecture will cover removing left recursion to complete the conversion.