Programming like question (context-free grammar)

true_atlantis · 03-09-2004, 06:02 PM

lets say i have a Context-free grammar tree like this

Code:

      S
     /  \
   A      B
 / \     /  \
a   A   A    B
    |    |    |
    a    a    b

how many different derivations are there that generate the final string?

there has to be a way to do this without deriving every single one...

eshwar_ind · 03-09-2004, 10:55 PM

I Think it depends on the string you are going to generate. As far as i have know there is no particular formula or method to find the number of different derivations for a string.
If any please let me know.

true_atlantis · 03-10-2004, 01:24 AM

that is what i was trying to specify with the "Context-free grammar", the final string will be the fronteir of the tree or "aaab" and what i was askin is how many was there are to derive that string... here would be an example of one way

S=>AB=>aAB=>aaB=>aaAB=>aaaB=>aaab

does that make sence?

sNicker · 03-10-2004, 04:54 AM

You are asking how many different trees can build the same terminal string in an ambiguous grammar.. The answer is: "depends". Are these the only grammatical rules?

1)S=>AB
2)A=>a
3)A=>aA
4)B=>b
5)B=>AB

In this case I can see only a couple of trees... The one you drew and

S =1> AB =2> aB =5> aAB =3> aaAB =2> aaaB =4> aaab

But maybe I'm missing something..

From what I remember you can't compute all the trees for every string for a generic grammar. You can build a solution for a given grammar and a given string, but you have to work on every single occurrence (in other words, no generic algorithm can compute all the different trees for a string in an ambiguous grammar...). Maybe my memory falls somewhere, you should try an internet search or ask a professor of formal languages...

true_atlantis · 03-10-2004, 11:04 AM

see this problem is from a book, and it givs you the tree and asks how many ways you can derive the string... i started doing a bunch of them... here is what i started to do...

S=>AB=>aAB=>aaB=>aaAB=>aaaB=>aaab
S=>AB=>aAB=>aaB=>aaAB=>aaAb=>aaab
S=>AB=>aAB=>aAAB=>aAAb=>aAab=>aaab
S=>AB=>aAB=>aAAB=>aAAb=>aaAb=>aaab
S=>AB=>aAB=>aAAB=>aAaB=>aAab=>aaab
S=>AB=>aAB=>aAAB=>aAaB=>aaaB=>aaab
S=>AB=>aAB=>aAAB=>aaAB=>aaaB=>aaab
S=>AB=>aAB=>aAAB=>aaAB=>aaAb=>aaab
S=>AB=>AAB=>aAAB=> 6X
S=>AB=>AAB=>AaB=>Aab=>aAab=>aaab
S=>AB=>AAB=>aAB=>aAAB 6X
S=>AB=>AAB=>AaB=>aAaB=>aAab=>aaab
S=>AB=>AAB=>AaB=>aAaB=>aaaB=>aaab
S=>AB=>AAB=>aaB=>aaAB=>aaaB=>aaab
S=>AB=>AAB=>aaB=>aaAB=>aaAb=>aaab