SUNY Geneseo Department of Mathematics

Ambiguity of CFGs is Undecidable

Wednesday, April 13

Math 304
Spring 2016
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc
- REU Talk
  - Megan Brunner
  - Measuring intercultural competence in middle school students
  - Thursday, April 14, 3:30, South 328
  - Extra credit for write-ups
Questions?
Ambiguity of CFGs is Undecidable
- From PCP instance P, construct CFG G
```
S → T    // = “top”
S → B    // = “bottom”
...
T → t_i T a_i 
...
B → b_i B a_i
```
- T derives string from tops of tiles, B from bottoms, the a_i are tile identifiers that ensure that both derivations of the same string use the same tiles
- String w has ambiguous derivation iff w is the top/bottom of a match in P
  - Part 1: w has ambiguous derivation
    - w must = t_i₁t_i₂...t_{i_n} a_{i_n}...a_i₂a_i₁ = b_i₁b_i₂...b_{i_n} a_{i_n}...a_i₂a_i₁
    - Ambiguity is S → T vs S → B
      - (Ambiguity within t’s or b’s leads to different a_{i_j} sequences)
    - P has match w/ tiles a_i₁ a_i₂ ... a_{i_n}
  - Part 2: P has a match
    - t_i₁t_i₂...t_{i_n} = b_i₁b_i₂...b_{i_n} = w
    - G derives...
      - S → T → t_i₁ T a_i₁ → t_i₁ t_i₂ T a_i₂ a_i₁ ... → t_i₁t_i₂...t_{i_n} a_{i_n}...a_i₁
        = w a_{i_n} ... a_i₁
      - S → B → b_i₁ B a_i₁ → ... → b_i₁b_i₂...b_{i_n} a_{i_n} ... a_i₁
        = w a_{i_n} ... a_i₁
    - 2 derivations, therefore G is ambiguous
- This construction reduces PCP to ambiguity in CFG
  - Deciding ambiguity would decide PCP
  - Which is undecidable
Next
- The Recursion Theorem
- Definition of “computable function” f(x)
  - There exists Turing machine that if started with ⟨x⟩ on tape halts with ⟨f(x)⟩ on tape
- Read section 6.1 through “Self-Reference”
  - Bottom of page 245 through top 2/3 of 249

Next Lecture