Lecture Notes: Regular Grammar and Its Types

What is Grammar?

• Grammar Representation: Grammar is represented by a four-tuple: (G = (V, T, P, S))
  • V (Variables): Also called non-terminals, represented by uppercase letters.
  • T (Terminals): Terminal symbols, represented by lowercase letters, digits, and symbols (e.g., +, -, ?, ε).
  • P (Production Rules): Each rule is of the form (\alpha \rightarrow \beta) where (\alpha) is the left-hand side and (\beta) is the right-hand side.
  • S (Start Symbol): Always a non-terminal; the left-hand side of the first production.

Types of Regular Grammar

Regular grammars are classified into two main types:

1. Left Linear Regular Grammar

• Form: (A \rightarrow B \alpha)
• Characteristics:
  • The leftmost symbol on the right-hand side is a non-terminal.
  • (A) and (B) are non-terminals, while (\alpha) is a terminal symbol (can be lowercase, digit, or symbol like ε).

2. Right Linear Regular Grammar

• Form: (A \rightarrow \alpha B)
• Characteristics:
  • The rightmost symbol on the right-hand side is a non-terminal.
  • (A) and (B) are non-terminals, while (\alpha) is a terminal symbol.

Key Differences Between Left Linear and Right Linear Grammar

• Left Linear: The leftmost symbol on the right-hand side is a non-terminal.
• Right Linear: The rightmost symbol on the right-hand side is a non-terminal.

Upcoming Topics

• How to construct left linear and right linear grammars.
• Conversion between right linear and left linear grammars.