Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Formal Languages

Chomsky Hierarchy

Formal languages are classified by the generative grammars that produce them:

TypeGrammarAutomatonLanguage ClassExample
3RegularDFA/NFARegulara*b*
2Context-FreePushdown AutomatonContext-Free{aⁿbⁿ}
1Context-SensitiveLinear-Bounded AutomatonContext-Sensitive{aⁿbⁿcⁿ}
0UnrestrictedTuring MachineRecursively EnumerableA_TM
 
Type 0 (Recursively Enumerable)
  ⊃ Type 1 (Context-Sensitive)
    ⊃ Type 2 (Context-Free)
      ⊃ Type 3 (Regular)

Regular Languages

Defined by regular expressions or recognized by DFAs/NFAs. Key closure properties: union, intersection, complementation, concatenation, Kleene star.

Pumping Lemma for Regular Languages: If L is regular, ∃p (pumping length) such that any string s ∈ L with |s| ≥ p can be split s = xyz where |xy| ≤ p, |y| > 0, and xyⁱz ∈ L for all i ≥ 0.

Using the pumping lemma to prove non-regularity (proof by contradiction):

  1. Assume L is regular. Let p be the pumping length.
  2. Choose a string s ∈ L with |s| ≥ p.
  3. Show that for any valid split xyz, some xyⁱz ∉ L.
  4. Contradiction → L is not regular.
def is_regular_by_dfa(string, transitions, start, accept):
    """Check membership in a regular language via DFA simulation."""
    state = start
    for ch in string:
        state = transitions.get((state, ch))
        if state is None:
            return False
    return state in accept

Context-Free Languages

Generated by context-free grammars (CFGs) or recognized by pushdown automata (PDAs). The stack gives them the power to match balanced delimiters.

CYK Algorithm (O(n³|G|)) parses any CFG in Chomsky Normal Form:

For string w = a₁a₂...aₙ:
  R[i][i] = { A | A → aᵢ is a rule }        (length 1 substrings)
  R[i][j] = { A | A → BC, B ∈ R[i][k], C ∈ R[k+1][j] }  (longer substrings)
  w ∈ L(G) iff S ∈ R[1][n]

Pumping Lemma for CFLs: If L is context-free, ∃p such that s = uvxyz with |vy| > 0, |vxy| ≤ p, and uvⁱxyⁱz ∈ L for all i ≥ 0.

Context-Sensitive Languages

Generated by context-sensitive grammars where production rules α → β satisfy |α| ≤ |β| (except possibly S → ε). Recognized by linear-bounded automata (TMs with tape bounded by input length). Example: {aⁿbⁿcⁿ | n ≥ 0}.

Interview Questions

Q: How do you prove a language is not regular? A: Use the pumping lemma. Assume it’s regular, pick a string longer than the pumping length, and show that pumping any valid division breaks membership. For {aⁿbⁿ}, pick aᵖbᵖ — pumping y (which must be all a’s) breaks the equal-count property.

Q: Why can’t a DFA recognize {aⁿbⁿ}? A: A DFA has finite memory (fixed states). To count n a’s and verify exactly n b’s, it would need unbounded memory — n can be arbitrarily large. A PDA solves this with its stack.

Q: What is the difference between the pumping lemmas for regular and context-free languages? A: The regular pumping lemma splits strings into 3 parts (xyz) and guarantees the middle part can be pumped. The CFL pumping lemma splits into 5 parts (uvxyz) and guarantees the two middle parts pump together (same exponent). The CFL version is more flexible, reflecting the greater power of CFGs.

References