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.
a^n means a taken ntimes.
Context free grammar
Heh, I'm fairly sure you use this forum to do your homework for you 
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]
Last edited by AftershockVibe on Thu Apr 27, 2006 12:57 am; edited 1 time in total
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]
Last edited by AftershockVibe on Thu Apr 27, 2006 12:57 am; edited 1 time in total
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.
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.
Use the pumping lemma, you can see that it wont work, thus it is not a CFG.
 |