Hello everyone,
I have to check if the following language is context free:
L2={a^n * b^m * c^n * d^(n+m) :m>=0 n>=0 }
Please help, I am totally stuck and I have to hand it over on Monday.
views:
403answers:
3
+1
A:
For disproving that it is context free: http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages
For proving that it is context free - come up with a context-free grammar that generates the language.
Try both of the above until one succeeds.
Rafał Dowgird
2010-05-08 19:32:11
I used the pumping theory i order to prove tha the language in not context free but i could n't prove it so after some googling i saw that the language is context free so thougth to create a pussh down automatic which accept the language but i wa n't able to do that
altius
2010-05-08 19:49:03
Google-my-homework. Sigh.
Warren P
2010-05-10 19:06:05
A:
It's not context-free. a^n b^m c^n d^m is the first example of a non- context-free language, this one is very similar.
You can disprove it with the pumping lemma like Rafal wrote.
Itsik
2010-05-08 20:04:03
thanks alot i have prove in a previous example that a^n b^m c^n d^m is not context free but if i use any other language with a close property can i just say that the result of a close property is non context free because the one language(a^n b^m c^n d^m) is n't?
altius
2010-05-08 20:12:34
Yes, you are right. thats what happens when you do this late at night :). I'll fix the closure to something that works
Itsik
2010-05-09 15:41:47
I saw your post edited but again i can not understand which language L2 is?
altius
2010-05-09 16:32:51
I'm having trouble finding the correct homomorphism. It's more complicated than I first assumsed. I'm almost positive this is non context-free.. where did you see that it isnt ?
Itsik
2010-05-09 16:40:38
In this PDF http://www.cs.duke.edu/courses/cps140/spring03/lects/sectnpdaS.pdf
altius
2010-05-09 17:46:15
They wrote { a^n b^m+n c^n }, this is totally different, and context-free. The easiest way for you to do it is just use the pumping lemma, I couldnt find an easy with closure properties.You show that for each substring of L2, the lemma doesnt work. For example, we'll assume that L2 is context-free, then exists an integer n that fulfills the lemma. Then show that each substring doesnt fulfill (all a's, a's and b's, abc's, and abcd }. At each stage the lemma will fall for a different reason.
Itsik
2010-05-09 21:05:17
+1
A:
So you can prove that this isn't context free with a pretty standard pumping lemma by cases argument. (I don't do the whole model the pumping lemma as games, because that's just for people who don't understand quantifiers).
Take any m, now construct the string:
a^m b^m c^m d^2m
It should be pretty obvious that this string is in the language and is the case where n=m. Now what happens if we pump any part of the string, well clearly if we pump any part consisting of only one letter, then it will no longer be a member of the language. If we pump any of the overlaps then it will also no longer be a member of the language, because we won't be able to change the corresponding n or m component so that it corresponds to it. As an example if we pump the ab overlap then c won't have the same cardinality as a, so it won't be in the language.
Obviously you might need a little bit more rigor, but that's all that it takes.
Jacob Schlather
2010-05-09 17:14:45