L2.3 · Regular grammars

Chapter recap

A grammar G = (V, T, P, S) generates L(G) = {w ∈ T* : S ⇒* w}. General grammars can generate non-regular languages (S → aSb | ε). Right-linear (A → wB | w) and left-linear (A → Bw | w) grammars generate exactly the regular languages; mixing the two sides does not guarantee regularity. DFA arrows become productions A → aB, accepting states get A → ε.

Merged rule card

From 2.3.1 What a grammar is

G = (V, T, P, S); A → x | y; sentential form; ⇒, ⇒*; L(G) = {w ∈ T* : S ⇒* w}.
S → aSb | ε gives aⁿbⁿ (not regular) — general grammars exceed DFAs.
Palindromes: S → aSa | bSb | a | b | ε.

From 2.3.2 Right-linear and left-linear grammars

Right-linear: A → wB | w. Left-linear: A → Bw | w. Regular grammar = one of the two (not mixed).
DFA → grammar: δ(A,a)=B ⇒ A → aB; A accepting ⇒ A → ε.
Grammar → NFA: A → aB is an arrow; A → a goes to a new accepting state.
Mixed linear can give aⁿbⁿ. Non-regular grammar does not imply non-regular language.

Practice questions

MCQ
Which grammar is right-linear?
1. S → Sa | b
2. S → aSb | ε
3. S → abS | a
4. S → AB, A → a, B → b
MSQ
Which languages are generated by S → aS | bA, A → bA | ε?
1. a*b⁺
2. strings with at least one b, all a’s before all b’s
3. a*b*
4. (a+b)*b
NAT
Minimum number of variables in a right-linear grammar for (ab)* using rules of the form A → aB, A → ε (one terminal per rule)?
Write your answer before opening the key.
MCQ
Left-linear S → Sa | Sb | a describes:
1. strings starting with a
2. strings ending with a
3. a*
4. (ab)*
MCQ
S → aSa | ε generates:
1. a*
2. (aa)*
3. a⁺
4. {ε}
MSQ
Which are true?
1. Every regular language has a right-linear grammar
2. Every regular language has a left-linear grammar
3. S → aSb | ε is right-linear
4. Right-linear grammars can be converted to NFAs
MCQ
A grammar has rules S → aA, A → Sb | b. It is:
1. regular
2. linear but not regular
3. left-linear
4. right-linear
NAT
Strings of length 4 generated by S → aS | bS | a?
Write your answer before opening the key.

Answer key

Reveal answers when you’re ready

C — Variables only at the right end.
- A: Left-linear.
- B: Variable in the middle.
- D: Two variables in a body.
AB — a’s, then a b, then more b’s.
- C: Includes ε and a’s only, which are not generated.
- D: Allows b before a.
2 — S → aB | ε, B → bS.
A — The derivation grows to the left from a final leftmost a: a(a+b)*.
- B: Growth is on the right, so the first symbol is fixed.
- C: b’s allowed.
- D: Unrelated.
B — Two a’s per step.
- A: Odd lengths missing.
- C: ε included, odd excluded.
- D: More strings.
ABD — Standard.
- C: Variable in the middle.
B — Mixed sides; generates aⁿbⁿ.
- A: Mixed rules are not a regular grammar.
- C: S → aA is right-linear.
- D: A → Sb is left-linear.
8 — Ends with a: 2³.