What a grammar is

1. Arden: solution of R = Q + RP when ε ∉ L(P)?
   Stuck? Peek at 2.2.2 FA → regex: state elimination and Arden’s theorem

   • Prep: new start S (ε to old start), new accept E (ε from old accepting). Merge parallel arrows with +.
   • Eliminate k: R(p,q) ← R₄ + R₁R₂*R₃ (no loop ⇒ R₂* = ε).
   • Arden: R = Q + RP, ε ∉ P ⇒ R = QP*. Mirror: R = Q + PR ⇒ R = P*Q.
   • Incoming equations: q = Σ p·a (+ ε for start); answer = sum over accepting states.

   Read lesson 2.2.2

2. Is (a+b)* equal to a*(ba*)*?
   Stuck? Peek at 2.1.2 Writing regexes, identities and equivalence

   • ∅ + r = r; ∅r = ∅; εr = r; ∅* = ε* = ε; (r*)* = r*; r*r* = r*; ε + rr* = r*; (rs)*r = r(sr)*.
   • (r+s)* = (r*s*)* = (r*+s*)* = r*(sr*)* = (r*s)*r*.
   • ≠: (r+s)* vs r*+s* vs r*s*; (rs)* vs r*s*.
   • No “aa”: (b+ab)*(ε+a). At most one a: b*(ε+a)b*. Even #0: 1*(01*01*)*.
   • Equality: compare shortest strings; counterexample kills; identities or minimal DFAs prove.

   Read lesson 2.1.2

3. How many strings of length n are there over a 2-letter alphabet?
   Stuck? Peek at 0.3.2 Σᵏ, Σ*, Σ⁺ and languages

   • |Σᵏ| = |Σ|ᵏ; Σ⁰ = {ε}; Σ* = ⋃ Σᵏ (k ≥ 0); Σ⁺ = Σ* − {ε}.
   • #strings of length ≤ n over k symbols = (kⁿ⁺¹ − 1)/(k − 1); binary: 2ⁿ⁺¹ − 1.
   • Language = any subset of Σ*. ∅ (no strings) ≠ {ε} (one string). Exactly r of one symbol in length n (binary): C(n, r).
   • Shortlex order lists every string at a finite position.

   Read lesson 0.3.2

English sentences are built by rules like “a sentence is a noun phrase followed by a verb phrase”. Programming languages are defined the same way in their manuals: “an expression is a term, or an expression plus a term”. Machines check strings; regexes describe them; a grammar generates them by rewriting symbols step by step. Grammars become the main tool of Phase 3, so we meet them here first.

Rules: S → aS and S → b. Starting from S and applying rules until no S is left, which strings can you produce?

Prediction check

S ⇒ b; S ⇒ aS ⇒ ab; S ⇒ aS ⇒ aaS ⇒ aab; … The strings are b, ab, aab, … = a*b.

Formal definition

Shorthand: A → x | y means two productions A → x and A → y. A → ε means A can vanish.

Derivations

A derivation step uA v ⇒ uβv applies a rule A → β somewhere in a string. ⇒* means “zero or more steps”. A string of variables and terminals reachable from S is a sentential form; one with only terminals is a sentence.

Grammars can be stronger than finite automata

Consider S → aSb | ε. Derivations: S ⇒ ε; S ⇒ aSb ⇒ ab; S ⇒ aSb ⇒ aaSbb ⇒ aabb. L(G) = { aⁿbⁿ | n ≥ 0 } — a language we proved is not regular (1.3.3). So grammars in general can describe more than DFAs. Which grammars stay within the regular languages? That is the next lesson’s question.

Reading a grammar

Ask: what does each variable generate on its own? Build up from the variables with only terminal rules. Example: A → aA | ε generates a*; B → bB | b generates b⁺; S → AB generates a*b⁺.

Putting it together

• A grammar (V, T, P, S) generates strings by rewriting variables until only terminals remain.
• L(G) = all terminal strings derivable from S.
• General grammars can generate non-regular languages such as aⁿbⁿ.

G:  S → aSb | ε                derivation of aabb
                                 S
 S ⇒ aSb                         ├─ a
   ⇒ aaSbb                       ├─ S ─┬─ a
   ⇒ aabb   (S → ε)              │     ├─ S ── ε
                                 │     └─ b
                                 └─ b          (a tree of rule applications)

G2: S → aS | bS | a     L(G2) = strings over {a,b} ending in a = (a+b)*a

Now: which shapes of rules generate exactly the regular languages? Answer: rules that grow the string from one end only — right-linear or left-linear grammars.

1. MCQ

   In G = (V, T, P, S), the set T contains:

   1. variables
   2. terminals
   3. productions
   4. start symbols
2. MSQ

   G: S → aS | bS | ε. Which strings are in L(G)?

   1. ε
   2. ab
   3. bba
   4. none of length 2
3. MCQ

   L(S → aSbb | ε) is:

   1. { aⁿbⁿ }
   2. { aⁿb²ⁿ : n ≥ 0 }
   3. a*b*
   4. { a²ⁿbⁿ }
4. NAT

   G: S → aSa | bSb | a | b | ε. How many strings of length 4 are in L(G)?

   Write your answer before opening the key.

• grammar G = (V, T, P, S)
• variable (non-terminal), terminal
• production A → β
• start symbol
• derivation ⇒, ⇒*
• sentential form, sentence
• language of a grammar L(G)

1. Four parts of a grammar?
   Reveal answer

   Variables V, terminals T, productions P, start symbol S.
2. L(S → aSb | ε)?
   Reveal answer

   { aⁿbⁿ : n ≥ 0 }
3. Grammar for palindromes over {a,b}?
   Reveal answer

   S → aSa | bSb | a | b | ε