1Draw a nondeterministic PDA transition diagram that accepts

1)Draw a non-deterministic PDA (transition diagram) that accepts the following language by final state acceptance.  

L = { w₁cw₂cw₃ | w₁ = w₂^R or w₁ = w₃^R }

2.Show that context-free languages are closed under concatenation. That is, if L1 and L2 are both context free, then L1L2 = {xw | x L1 and w L2} is also context free.

Solution

2)

Proof

1. Let L1 and L2 be generated by the CFG, G1 = (V1, T1, P1, S1) and G2 = (V2, T2, P2, S2),

2. subscript each nonterminal of G1 with a 1, and each nonterminal of G2 with a 2 (so that V1 V2 = ).

3. Define the CFG, G, that generates L1L2 as follows: G = (V1 V2 {S}, T1 T2, P1 P2 {S S1S2}, S).

4. Each word generated thus is a word in L1 followed by a word in L2.Hence L1L2 is also CFG.

==========================================================================

Comment about work