Sunday, January 30, 2005

Context Free Grammar

In the context of context free grammar i thought of one thing which may help someone in making a grammar/testing ones own while developing. There are terminal and non terminals in a grammar. we start with a starting non-terminal(S) then apply any of grammatical rules any number of times to it to finally create a string of alphabets with terminals only. eg. S->aAb S->ab will give all those non empty string which have a's followed by equal number of b's.

Now the thing is we can look the other non-Terminals here (A in this case) as representative of the property of the string that we want to produce (equal a's followed by equal b') So what all can we do to maintain this property. add a's and b's before and after the string

Now one can propose the grammar S->A and A->Ab A->aA but it fails in one fact mentioned above (any of the grammar rules any number of times) so if i apply S->Ab 3 times and S->aA 4 times then the numbers dont match. So the rules can be applied in any order and any number of times.

We can imagine so because in context free grammars except for null transistion (A->e e is null string) all other possible rules can only increase the length of unprepared string. And it is a qood visualization technique also it looks like loop invariance i learned in formal program developement course...

No comments: