Solved

context free grammar

Posted on 2008-10-09
3
400 Views
Last Modified: 2008-10-24
can someone give me a link in the internet of resources that proves :

L = {a^nba^mba^(m+n) | n,m>=1}
0
Comment
Question by:kuntilanak
3 Comments
 
LVL 5

Accepted Solution

by:
PaulKeating earned 500 total points
ID: 22693276
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
 

Author Comment

by:kuntilanak
ID: 22736536
I've read that, but seems like I don't find any resources there that will help me to solve this
0
 
LVL 84

Expert Comment

by:ozo
ID: 22737043
M ::= b | a M a
L ::= b M | a L a'
0

Featured Post

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Regex Help 2 38
regex. How to include lines between 10 93
regex to allow alphanumeric characters and \ 2 60
regex to restrict strings ending with something 2 11
I have been reconstructing a PHP-based application that has grown into a full blown interface system over the last ten years by a developer that has now gone into business for himself building websites. I am not incredibly fond of writing PHP code o…
Whatever be the reason, if you are working on web development side,  you will need day-today validation codes like email validation, date validation , IP address validation, phone validation on any of the edit page or say at the time of registration…
Learn how to match and substitute tagged data using PHP regular expressions. Demonstrated on Windows 7, but also applies to other operating systems. Demonstrated technique applies to PHP (all versions) and Firefox, but very similar techniques will w…
Explain concepts important to validation of email addresses with regular expressions. Applies to most languages/tools that uses regular expressions. Consider email address RFCs: Look at HTML5 form input element (with type=email) regex pattern: T…

713 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question