Pumping Lemma, Table Filling, DFA Minimization, Parse Trees, Ambiguous Grammars & Context-Free Grammars
Classified in Electronics
Written on in English with a size of 1,022.87 KB
Pumping Lemma and Non-Regular Languages
9) Define Pumping Lemma. Prove that the language L = { ai bj | i > j } is not a regular language:
Let L be a regular language. There exists a constant k such that for every string ω in L, where the length of string ω i.e |ω| ≥ k, we can break ω into 3 strings i.e ω = xyz following conditions:
- (i) |xy| ≤ k
- (ii) y ≠ ε i.e |y| > 0
- (iii) for each q ≥ 0, xyqz ∈ L
Let L be a regular language. w = a(k+1) bk is a long string (given k > 0). |w| = 2k + 1, w = xyz should satisfy:
- (i) |xy| ≤ k
- (ii) y ≠ 0
- (iii) for each q ≥ 0, xyq z ∈ L
Let k = 3, w = a4 b3, which is aaaaabbb.
- (i) |xy| ≤ k, 3 ≤ 3
- (ii) y ≠ 0, y = a
Minimization of DFA's
11) Minimization of DFA’s A=(Q, Σ, δ, q0, F):