Lecture Notes on Regular Grammar

Introduction to Grammar

• Grammar is a set of rules for proper conversation in human language.
• It is also applicable in computer languages, defined mathematically.
• Noam Chomsky proposed a mathematical model of grammar for writing computer languages.

Types of Grammars (Chomsky's Classification)

1. Type 0 Grammar

   • Unrestricted grammar
   • Accepted language: Recursively enumerable language
   • Automaton: Turing machine

2. Type 1 Grammar

   • Context-sensitive grammar
   • Accepted language: Context-sensitive language
   • Automaton: Linear bounded automaton

3. Type 2 Grammar

   • Context-free grammar
   • Accepted language: Context-free languages
   • Automaton: Pushdown automata

4. Type 3 Grammar

   • Regular grammar (Subject of this lecture)
   • Accepted language: Regular languages
   • Automaton: Finite state automaton

Formal Definition of Grammar

• A grammar G can be defined using four tuples: G = (V, T, S, P)
  • V: Set of variables or non-terminal symbols
  • T: Set of terminal symbols
  • S: Start symbol
  • P: Production rules for terminals and non-terminals

Production Rules

• Production rules have the form:
  • Alpha → Beta
  • Alpha = strings on V ∪ T
  • At least one symbol of Alpha belongs to V (non-terminal).

Example of a Grammar

• Given a grammar G:
  • V = {S, A, B}
  • T = {a, b}
  • S = S
  • P:
    • S → AB
    • A → a
    • B → b
• Example string formed:
  • Starting with S → AB → ab (by applying production rules)

Regular Grammar

• Regular grammar can be classified into two types:
  1. Right Linear Grammar
     • Production rules are of the form: A → XB or A → X
     • X = terminal symbol, B = non-terminal symbol (B is to the right of X).
  2. Left Linear Grammar
     • Production rules are of the form: A → BX or A → X
     • X = terminal symbol, B = non-terminal symbol (B is to the left of X).

Examples

• Right Linear Grammar Example:
  • Production rule: S → aB, S → b
• Left Linear Grammar Example:
  • Production rule: S → SB, S → b

Conclusion

• Understanding regular grammar and its types is essential in the study of formal languages and automata theory.
• Next lecture will delve deeper into regular grammar concepts and applications.

---

Thank you for watching!