You should prove that if w in L(G1) then it on doubleswap(L) by the grammar

that you define.

Algo CFL are closes by homomorfism (sorry for my english) so h(a)=bb and

h(b)=aa than the h(L) is still CFL

"Jack Smith" <st*******@yahoo.com> wrote in message

news:20**************************@posting.google.c om...

Hello, I have the following problem. I have an idea of how to prove

it, but any other help is appreciated.

Let doubleswap(L) be the language obtained from L by replacing each a

by bb and each b by aa in all strings in L. Prove that if L is

context free, then so is doubleswap(L). Note L is a subset or equal

to {a,b,c}*.

Now here is how I would prove it:

We know since L is context-free, there exists a grammer G for L. Now

any grammer G can be converted to a grammer G' in Chomsky Normal Form.

So we only have productions of the form A ->BC and D -> k where

A,B,C,D are an element of the Non-Terminals and k is an element of the

terminals. So it is easy to create a new grammer G1 for doubleswap(L)

by usings the exact same productions as G', but replacing each

production of the form P1-> a by P1-> bb and P2->b by P2->aa. But I

think I need to show more. I think I may still have to show L(G1) =

doubleswap(L), since I just showed how you could construct a grammer

that should give us doubleswap(L). How would I show this? Any Help

appreciated.

Thanks