Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 429
  • Last Modified:

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}
0
kuntilanak
Asked:
kuntilanak
1 Solution
 
PaulKeatingCommented:
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

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Tackle projects and never again get stuck behind a technical roadblock.
Join Now