context free grammar

can someone give me a link in the internet of resources that proves :

L = {a^nba^mba^(m+n) | n,m>=1}
kuntilanakAsked:
Who is Participating?
 
PaulKeatingConnect With a Mentor Commented:
I think you are looking for a proof that

"L = {a^nba^mba^(m+n) | n,m>=1} is (or: is not) context-free".

When you need a proof, it's helpful to know the answer up front so that you know what you want to prove. That answer is: You can't write a regular expression for this language. The plain-language rule is "finite automata cannot count". It is also not context-free. The plain-language rule is "context-free grammars can count 2 things but not 3."

But you don't just want the answer, you want a proof. Most online resources on this topic are not free. Here is one that is: How to Use The Pumping Theorem, available at

http://www.cs.utexas.edu/~ben/teaching/cs341_fa04/pumping.pdf

It doesn't cover the specific language you specify: for that you're going to have to do a bit of work. I suspect the language was chosen specifically to be slightly different from the standard textbook examples. In other words, you are unlikely to find a proof that you can simply crib.
0
 
kuntilanakAuthor Commented:
I've read that, but seems like I don't find any resources there that will help me to solve this
0
 
ozoCommented:
M ::= b | a M a
L ::= b M | a L a'
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.