inherent ambiguity

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • stdvu
    New Member
    • Oct 2008
    • 21

    inherent ambiguity

    how do one prove that the language is inherently ambigous? like for example in languages that use unions such as
    L = L1 U L2, where
    L1 = {a^m b^m c^n | m,n>0}
    L2 = {a^m b^n c^n | m,n>0}
  • JosAH
    Recognized Expert MVP
    • Mar 2007
    • 11453

    #2
    Originally posted by stdvu
    how do one prove that the language is inherently ambigous? like for example in languages that use unions such as
    L = L1 U L2, where
    L1 = {a^m b^m c^n | m,n>0}
    L2 = {a^m b^n c^n | m,n>0}
    If the intersection of L1 and L2 isn't empty while L1 != L2 the union of both
    languages L1 U L2 is ambiguous. Note that the problem L1 == L2? is an
    undecidable problem. See the Post Correspondence Problem for a fundamental
    proof.

    kind regards,

    Jos

    Comment

    Working...