FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


Context free grammar





akshar
why a context free grammer can not represent a^nb^nc^n while it can represent a^nb^n

a^n means a taken ntimes.
AftershockVibe
Heh, I'm fairly sure you use this forum to do your homework for you Razz

The reason is due to the definition of a CFG (Context Free Grammar). In a CFG you are only allowed one Non-terminal symbol on the left hand side and only one non-terminal symbol on the right with more than one terminal.

All of the statements must be of the form;

S -> t1Nt2
Where the N or t2 are optional.

There is no possible way using these rules to construct a grammar which can guarentee equal numbers of three symbols because the non-terminal (N) required to generate the recursion for the n instances of the letters would have to be on different lines (as only one is allowed per line) meaning that guaranteeing equal numbers of these non-terminals isn't possible.

You can construct a grammar for a^nb^n:
S -> aSb | [Empty String]
akshar
Yeah it's true tht i use this forum to do my homework not because I am lazy to find the things out on myself but I want to know what the possible experts has to say about this.

But in this case it is not my homework but some extra stuff i am learning. Learning automata as an extra stuff without having a teacher is a tough thing and i am very thankful for your help.
Liu
Use the pumping lemma, you can see that it wont work, thus it is not a CFG.
Related topics
Free Hosting-Availability
Hey guys, want a free sig?
Free games
Submit to tons of search engines for free
Big guide to FREE programs!
And they wonder why we lable liberals...
Do we have Free Will or is there only Determinism?
Free Speech
Do You use yacc ,lex ? Can You give me recomendations ?
Best web editing software
Firesouls domain - fun games and free stuff
Prevention, detection, and cure: 12 free security programs
Download Free - IObit Advanced SystemCare Pro 3.6.1
Questions about English words
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.