By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
438,034 Members | 822 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 438,034 IT Pros & Developers. It's quick & easy.

Please Help on CFLs

P: n/a
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
Jul 17 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
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

Jul 17 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.