LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Programming like question (context-free grammar) (https://www.linuxquestions.org/questions/programming-9/programming-like-question-context-free-grammar-155587/)

true_atlantis 03-09-2004 06:02 PM
Programming like question (context-free grammar)
 
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


All times are GMT -5. The time now is 06:34 PM.