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.

**Remove Unit and Null Productions: **
- Check for unit productions or null productions.
- Remove them using techniques discussed in previous lectures.
Check for Chomsky Normal Form (CNF):
- Verify if CFG is already in CNF.
- Convert to CNF if not, using methods from previous lectures.
**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.
**Ensure Productions are in Ascending Order: **
- Form: AI → AJ X, where I < J.
- Ensure order: I should always be less than J.

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.

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.

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.

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.