Formal grammars are the foundation of computational theory, helping us understand and define the structure of languages. To classify a grammar, it’s crucial to know whether it is regular, linear, or context-free. This guide will walk you through the rules and provide examples for easy understanding.
1. Regular Grammar
Regular grammars are the simplest type of grammar in the Chomsky hierarchy. They define regular languages, which can be recognized by finite automata.
Rules to Identify Regular Grammar
- Each production must have at most one non-terminal on the right-hand side.
- The non-terminal (if present) must appear either at the start or the end of the production.
- Productions are of the form:
- ϵ (empty string) productions are allowed.
Example of Regular Grammar
S→aA
A→bB
B→c
This grammar generates strings like abcabcabc, ababab, etc., and is right-linear.
Non-Examples
- S→aSb Violates the rule because SSS appears in the middle.
- S→SS Violates the rule because there are two non-terminals.
2. Linear Grammar
Linear grammars are slightly more expressive than regular grammars. They allow one non-terminal anywhere in the production.
Rules to Identify Linear Grammar
- Each production must have at most one non-terminal on the right-hand side.
- Productions are of the form:
- x,y,w are strings of terminals.
Example of Linear Grammar
S→aSb
S→ab
This grammar generates strings like a^n b^n (e.g., ab, aabb etc.).
Non-Examples
- S→SS Violates the rule because there are two non-terminals.
- S→aSbT Violates the rule because there are multiple non-terminals.
3. Context-Free Grammar (CFG)
Context-free grammars are more powerful than regular and linear grammars. They define context-free languages, which can be recognized by pushdown automata.
Rules to Identify Context-Free Grammar
- Each production must have exactly one non-terminal on the left-hand side.
- The right-hand side can have any combination of terminals and non-terminals.
- Productions are of the form:
- ϵ (empty string) productions are allowed.
Example of Context-Free Grammar
S→aSb
S→SS
S→ϵ
This grammar generates strings like aabb, aaabbb, etc.
Non-Examples
AB→aB Violates the rule because the left-hand side has more than one non-terminal.
Comparison of Regular, Linear, and Context-Free Grammars
| Property | Regular Grammar | Linear Grammar | Context-Free Grammar |
|---|---|---|---|
| Non-Terminals Allowed | At most one, at the start or end | At most one, anywhere | Any number |
| Right-Hand Side Form |
A → xB A → Bx A → x |
A → xBy A → w |
A → α (any combination of terminals and non-terminals) |
| Example |
S → aA A → b |
S → aSb S → ab |
S → aSb S → SS S → ϵ |
| Recognized By | Finite Automata | Limited use | Pushdown Automata |