Peter Linz Exercise 5.1

Question

Is the following language context-free?

L= { uvwv^R : u,v,w∈ {a,b}⁺ |u| = |w| =2 }

If yes, provide set of productions for the same.

Answer 1

I think it is

S$\rightarrow$ abA|baA|bbA|aaA

A $\rightarrow$ aAa|bAb|aXa|bXb

X $\rightarrow$ab| ba|aa|bb

Answer 2

S->AB

A->aa|ab|ba|bb

B->aBa|bBb|A

Comments

nice approach  :)

Answer 3

the question itself says that it is REGULAR (BOUNDED) i.e u,v are bounded with lenght '2' ,BUT  they are not infinate in lenght

and more over to  figure out this is CFL or  not, simlpy look at the  V W V^R ,

if V V^R  is present then it would be an NCFL,BUT its in the form of V W V^R  where W is of 2 lenght string which separates