Right-linear and left-linear grammars

1. What is a sentential form?
   Stuck? Peek at 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 | ε.

   Read lesson 2.3.1

2. Strict Thompson states for a*?
   Stuck? Peek at 2.2.1 Regex → ε-NFA (Thompson construction)

   • Invariant: one start (no in-moves), one accept (no out-moves).
   • ∅, ε, a: 2 states. r+s: +2 states, 4 ε. rs: ε from accept(r) to start(s). r*: +2 states, 4 ε (enter, skip, loop back, exit).
   • States ≤ 2 × (symbols + operators). Regex → ε-NFA → DFA proves regex ⇒ regular.

   Read lesson 2.2.1

3. Minimal DFA states for strings ending in a over {a,b}?
   Stuck? Peek at 1.1.3 DFA design patterns

   Language (|w| = k pattern)	Minimal states
   starts with w	k + 2
   contains w / ends with w	k + 1
   |x| ≡ r mod n	n
   |x| = k, |x| ≤ k	k + 2
   |x| ≥ k	k + 1
   #a mod m and/or #b mod n	m·n (typical)
   binary value ≡ 0 mod k, k odd	k
   binary ÷ 2ʲ	j + 1
   k-th symbol from start fixed	k + 2

   Divisibility update: r ← (base·r + digit) mod k.

   Read lesson 1.1.3

A DFA’s arrow “from A on a go to B” reads like a rule: “a string from A is a, followed by a string from B”. Write every arrow as a production and the DFA becomes a grammar. The grammars you get have a very rigid shape — a variable only ever appears at the right end. That shape is exactly what keeps grammars inside the regular languages.

DFA: A (start) ─a→ B, B ─b→ A, B is accepting. Write it as grammar rules, one per arrow, plus one rule for “B can stop here”.

Prediction check

A → aB, B → bA, B → ε. Language: a(ba)* — check: A ⇒ aB ⇒ a; A ⇒ aB ⇒ abA ⇒ abaB ⇒ aba ✓.

Right-linear and left-linear

FA → right-linear grammar

1. One variable per state; start symbol = start state.
2. For each δ(A, a) = B: add A → aB.
3. For each accepting A: add A → ε.

A derivation then mirrors the run: each step reads one symbol and moves to the next state.

Right-linear grammar → NFA

1. One state per variable plus one accepting state f.
2. A → aB: arrow A ─a→ B. A → a: arrow A ─a→ f. A → B: ε-arrow. A → ε: make A accepting.
3. Longer strings A → abcB: insert intermediate states for each symbol.

So right-linear grammars generate exactly the regular languages.

Left-linear grammars

A left-linear grammar for L corresponds to a right-linear grammar for Lᴿ (flip every right side). Since regular languages are closed under reversal (2.4.1), left-linear grammars also generate exactly the regular languages.

Direct conversion: for A → Ba, the string from A is a string from B followed by a — read the grammar “backwards from S”: S is the accepting state, terminal-only rules start the machine.

Mixing breaks it

Putting it together

• Right-linear (A → wB | w) and left-linear (A → Bw | w) grammars generate exactly the regular languages.
• DFA arrows become productions; accepting states get A → ε.
• Mixing left and right rules can escape regularity (aⁿbⁿ).

DFA for "ends with ab"                      right-linear grammar
 q0 —a→ q1, q0 —b→ q0                       Q0 → aQ1 | bQ0
 q1 —a→ q1, q1 —b→ q2                       Q1 → aQ1 | bQ2
 q2 —a→ q1, q2 —b→ q0   (q2 accepting)      Q2 → aQ1 | bQ0 | ε

derivation of "bab" mirrors the run q0 →b q0 →a q1 →b q2:
 Q0 ⇒ bQ0 ⇒ baQ1 ⇒ babQ2 ⇒ bab

rejected "aba": Q0 ⇒ aQ1 ⇒ abQ2 ⇒ abaQ1 — Q1 has no ε-rule, cannot finish

Regular languages now have five faces: DFA, NFA, ε-NFA, regex, regular grammar. Next chapter studies the family itself: which operations keep a language regular, what questions about it can be answered by an algorithm, and how to prove a language is NOT regular.

1. MCQ

   Which production is NOT allowed in a right-linear grammar?

   1. A → abB
   2. A → a
   3. A → Ba
   4. A → ε
2. MSQ

   Which statements are true?

   1. Right-linear grammars generate exactly the regular languages
   2. Left-linear grammars generate exactly the regular languages
   3. Every grammar with at most one variable per right side generates a regular language
   4. A left-linear grammar for L gives a right-linear one for Lᴿ
3. NAT

   Converting a 5-state DFA with 2 accepting states over {0,1} to a right-linear grammar (one rule per arrow, plus ε-rules) gives how many productions?

   Write your answer before opening the key.

4. MCQ

   L(S → aA, A → Sb | b) is:

   1. a*b*
   2. { aⁿbⁿ : n ≥ 1 }
   3. (ab)*
   4. a⁺b⁺

• right-linear grammar
• left-linear grammar
• regular grammar
• linear grammar (at most one variable)
• DFA ↔ grammar conversion

1. Right-linear production shapes?
   Reveal answer

   A → wB or A → w (w terminals).
2. Does mixing left- and right-linear rules keep regularity?
   Reveal answer

   Not guaranteed: S → aA, A → Sb | b gives aⁿbⁿ.
3. DFA arrow δ(A,a)=B as a production?
   Reveal answer

   A → aB
4. How do accepting states appear in the grammar?
   Reveal answer

   As A → ε rules.