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
Do You use yacc ,lex ? Can You give me recomendations ?
Best web editing software
Big guide to FREE programs!
And they wonder why we lable liberals...
Do we have Free Will or is there only Determinism?
Free Speech
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
Free Hosting-Availability
Hey guys, want a free sig?
Submit to tons of search engines for free
Free games
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.