Application of PCP

 

   THM: (Unsolvability of CFG (Context-Free Grammar) Ambiguity problem)

   Given an arbitrary CFG, it is unsolvable to decide whether or not it is ambiguous.

 

  Proof:

 

  We can reduce an arbitrary PCP system to an equivalent CFG such that PCP is solvable if and

only if the CFG is ambiguous.

 

  Let an arbitrary PCP system have two sets of corresponding substring pairs,

                    w₁ ,  w₂ ,  w₃  , …,  w_n   .   

                    x₁ ,   x₂ ,   x₃  , …,   x_n

 

  Now, consider  the following n symbols not in the alphabet:

a₁ ,  a₂ ,   a₃  , …,  a_n   

 

   We construct a CFG from above pair of lists of substrings as follows:

                    S ->    SA | SB

                    SA -> w_i    SA   a_i  , for i =1,2, …, n

                    SA -> w_i    a_i          , for i =1,2, …, n

                    SB -> x_i    SB   a_i    , for i =1,2, …, n

                    SB -> x_i    a_i           , for i =1,2, …, n

         

          For this above, G,

          L(G) =  { x_i1 x_i2 … x_ik   a_ik   … a_i2  a _i1, w_j1 w_j2 …w_mj  a_mj   … a_j2  a _j1  }

                         

    The first kind of strings are to be derived from the non-terminal SB and

    the second of strings from the non-terminal SA .

          A string of the first kind and a string of the second kind can be the same when the two

          non-terminals SA and SB do derive the same string, which makes the grammar

          ambiguous. And the grammar is ambiguous exactly when the given PCP system has

          a solution.                          

 

          EX:

          PCP System:

            ab    abb

            aa   baa

            bb    b

           

            bbaa is a solution

 

          Corresponding CFG:

                    S -> SA

                    S -> SB                 // These two production rules can be written:

          S -> SA | SB

                    SA -> ab SA c1 | aa SA c2 | bb SA c3 | ab c1 | aa c2 | bb c3

                    SB -> abb SB c1 | baa SB c2 | b SB c3 | abb c1 | baa c2 | b c3

          A string made up of this solution in part can be derived in two different derivation

          sequences making the grammar ambiguous as follows:

 

                    S -> SA -> bb SA c3 -> bb aa c2 c3

                    S -> SB -> b SB c3   -> b baa c2 c3