Lecture Notes on Grammar

Overview of Grammar

• Grammar is a four-tuple: (Vn, Vt, S, P)
  • Vn: Set of non-terminal symbols (usually capital letters)
  • Vt: Set of terminal symbols (usually lowercase letters or digits 0 to n)
  • S: Starting symbol of grammar (usually a non-terminal symbol)
  • P: Set of production rules, each in the form α → β

Types of Grammar

1. Type 0 Grammar (Unrestricted Grammar)

   • Both α and β can be any combination of terminal and non-terminal symbols.
   • Example: S → AAB, A → B

2. Type 1 Grammar (Context Sensitive Grammar)

   • α and β can be any combination of terminals and non-terminals.
   • Additional condition: Length of α <= Length of β.
   • Example: S → AAB, AA → B

3. Type 2 Grammar (Context-Free Grammar)

   • α must be a non-terminal symbol.
   • β can be any combination of terminal and non-terminal symbols.
   • Example: S → AAB, A → AA | B

4. Type 3 Grammar (Regular Grammar)

   • α must be a non-terminal symbol.
   • β can either be a terminal followed by a non-terminal or just a terminal.
   • Example: A → aB | a

Hierarchical Relationships

• All regular languages are context-free, but not all context-free languages are regular.
• All context-free grammars are context-sensitive, but not all context-sensitive grammars are context-free.

Example of Context-Free Grammar: A^nB^n

• Grammar: S → ASB | ε
• To generate strings like AAB, AABB, etc., where the number of A's equals the number of B's.

Example of Context-Free Grammar: Palindromes

• Grammar: S → AS | BS | ε | A | B
• Accepts strings like A, B, AA, ABBA.

Derivations

• Always specify which production rule is used in the derivation process.
• Example: For string AAB, the derivation could be shown as:
  • S → ASA → AAB

Practicing Grammar Problems

• Write strings for the given language.
• Construct production rules from the strings.
• State the four tuples (Vn, Vt, S, P) for the grammar.
• Solve one or more derivations for specific strings.

Important Remarks

• Make sure to specify production rules during derivations.
• Practice with both even-length and odd-length palindromes.
• Understand the relationship between grammar types and their corresponding languages.