Σ={a,b}, L = {w : w is a palindrome, and #a(w) = #b(w)}. For example, abbaabba ∈ L; aba ∉ L because it has more a's than b's; ba ∉ L because it is not the same left-to right as right-to-left. Finish the proof, started below, which shows that L ∉ CFLs.

HW-2(2)

Computer Science

Theory of Computing (Csc 520 Course)

2. (12.5 points):

Σ={a,b}, L = {w : w is a palindrome, and #a(w) = #b(w)}. For example, abbaabba ∈ L; aba ∉ L because it has more a's than b's; ba ∉ L because it is not the same left-to right as right-to-left. Finish the proof, started below, which shows that L ∉ CFLs.

1. L⋂ = L ⋂ a*b*a*

2. If L ∈ CFLs then L⋂ ∈ CFLs because the CFLs are closed under intersection with an RL.

3. If L⋂ ∉ CFLs then L ∉ CFLs by applying the modus tollens logic rule to step 2.

4. Use the CF pumping theorem to show that L⋂ ∉ CFLs.

4.a Let w = aᴷb²ᴷaᴷ. Then w ∈ L and |w| ≥ k, so that w can be expressed as the

concatenation of the substrings uvxyz, and the CF pumping theorem guarantees

apply.