Where you are in the story
Phase 2 ended at a wall: aⁿbⁿ, balanced brackets and palindromes are not regular. Phase 3 climbs over it with two tools — grammars that grow strings from both ends, and machines with a stack. Before that, lock in what regular languages can do, because GATE’s classification questions always start with “is it regular?”.
Previous phase in pictures
Four faces of one family
Regex shortest-strings check
| length | (a+b)* | a*b* | (ab)* |
|---|---|---|---|
| 0 | ε | ε | ε |
| 1 | a, b | a, b | — |
| 2 | aa ab ba bb | aa ab bb | ab |
Conversions
Closure: everything finite
The pumping slider
Carry these forward
Regex precedence?
Star, then concatenation, then union. (2.1.1)
Is (a+b)* = a* + b*?
No — ab separates them. (2.1.2)
Strict Thompson states for (a+b)*?
8. (2.2.1)
Arden’s theorem?
R = Q + RP with ε ∉ L(P) ⇒ R = QP*. (2.2.2)
Which grammars are regular?
Right-linear or left-linear, not mixed. (2.3.2)
Is a subset of a regular language regular?
Not necessarily. (2.4.1)
How do you test finiteness of a DFA’s language?
Trim useless states; infinite iff a cycle remains. (2.4.2)
Pumping lemma conditions?
|xy| ≤ p, |y| ≥ 1, xyⁱz ∈ L for all i ≥ 0. (2.4.3)
Is { w x wᴿ : w, x ∈ Σ⁺ } regular?
Yes. (2.4.4)
Unary regular languages?
Exactly those with eventually periodic length sets. (2.4.4)
Quick refresher
- MSQ
Which are regular?
- { aⁿbᵐ : n ≡ m (mod 2) }
- { aⁿbⁿ }
- { w : |w|ₐ − |w|_b ≡ 0 (mod 3) }
- { ww : w ∈ {a,b}* }
- NAT
Minimal DFA states for strings over {a,b} with exactly 2 b’s?
Write your answer before opening the key.
- MCQ
Arden: R = b + Ra gives
- ba*
- a*b
- (ba)*
- b*a
- MCQ
Which grammar generates a non-regular language?
- S → aS | b
- S → Sa | b
- S → aSb | ε
- S → abS | ε
What the next phase adds
Answer Vault
Reveal answers when you’re ready
- AC — Remainders only.
- B: Exact count comparison.
- D: Copy language over two letters.
- 4 — k + 2.
- A — R = QP* with Q = b, P = a.
- B: That solves R = b + aR.
- C: Wrong.
- D: Wrong.
- C — aⁿbⁿ.
- A: a*b.
- B: ba*.
- D: (ab)*.