| Grammar | Can LHS have multiple symbols? | Can LHS include terminals? | Distinct Constraint |
|---|---|---|---|
| Regular (RG) | No - must be exactly one non-terminal | No | RHS is strictly limited to Terminals or Terminal + Variable. Shapes: A → a or A → aB (Right-Linear). Note: You cannot mix Right-Linear (aB) and Left-Linear (Ba) rules in the same grammar. |
| Context-Free (CFG) | No - must be exactly one non-terminal | No | RHS can be a mix of any number of variables and terminals. |
| Context-Sensitive (CSG) | Yes | Yes | LHS Length ≤ RHS Length |
fraxhost
/ grammar_rule_of_thumb.md
Created
December 9, 2025 16:03
The table shows rule of thumb to identify grammars.
fraxhost
/ grammar_comparison.md
Last active
December 9, 2025 16:02
The table compares regular, context-free and context-sensitive grammar.
| Feature | Regular Grammar (RG) | Context-Free Grammar (CFG) | Context-Sensitive Grammar (CSG) |
|---|---|---|---|
| Rule form | A → aB or A → a or A → ε (right-linear or left-linear only) | A → α | α A β → α γ β |
| Depends on surrounding symbols? | No | No | Yes |
| Power | Least powerful | More powerful | Even more powerful |
| Can generate aⁿbⁿ? | No | Yes | Yes |
| Can generate aⁿbⁿcⁿ? | No | No | Yes |
| Used for | Lexical analysis, tokenization, and simple patterns | Programming languages, compilers | Natural language, advanced constraints |
| Parsing complexity | Very efficient - O(n) | Efficient - O(n³) worst case, often linear | Harder (exponential worst case) |
| Equivalent Machines | Finite Automata (DFA/NFA) | Pushdown Automata (PDA) | Linear Bounded Automata (LBA) |