?={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.