Results 1 to 4 of 4

Math Help - Showing CFG is ambiguous

  1. #1
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Showing CFG is ambiguous

    To show it i need to find a string belonging to language and show that
    has 2 different parsin trees. Is there way to tell which string could possibly have 2 diff trees
    or do i have to generate like 20 strings belonging to language and test each string?
    I would much appreciate ideas how to do this.
    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,163
    Thanks
    761

    Re: Showing CFG is ambiguous

    Hey stribor40.

    It would be good if you provided the example string, but ultimately you should look at grammars that have optional tokens or one or another token. The reason why I say this is because you can create a grammar with and without the optional tokens and both can arrive at the same sentence.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2013
    From
    Toronto
    Posts
    28

    Re: Showing CFG is ambiguous

    ok say this example....

    S->AB|aaB
    A->a|Aa
    B->b

    I know that this grammar generates strings such as "ab,aab,aaab,etc". Now I have to find one string tha has 2 different left derivations.
    How would I do that without testing each of these strings?

    Thanks for reply chiro
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,163
    Thanks
    761

    Re: Showing CFG is ambiguous

    Can you explain what a left derivation is? I haven't looked at formal definitions in many years (but I still understand what is going on).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Ambiguous Case (SSA)
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: April 11th 2012, 11:02 AM
  2. Ambiguous Case Help
    Posted in the Trigonometry Forum
    Replies: 7
    Last Post: December 4th 2011, 10:30 AM
  3. ambiguous
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 13th 2009, 12:04 PM
  4. Quickie! Ambiguous Cases
    Posted in the Trigonometry Forum
    Replies: 9
    Last Post: August 27th 2008, 08:29 PM
  5. Ambiguous Cases
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: December 9th 2007, 03:23 PM

Search Tags


/mathhelpforum @mathhelpforum