Undecidable problems for Recursively enumerable languages continued Fall 2004 COMP 335 1 L Take a recursively enumerable language Decision problems: L is empty? L is finite? L contains two different strings of the same length? All these problems are undecidable Fall 2004

COMP 335 2 Theorem: For a recursively enumerable languageL it is undecidable to determine whether L is finite Proof: We will reduce the halting problem to this problem Fall 2004 COMP 335 3 Let

M be the TM with L( M ) L Suppose we have a decider for the finite language problem: M Fall 2004 finite language problem decider YES L(M )

finite NO L(M ) not finite COMP 335 4 We will build a decider for the halting problem: YES M w Fall 2004

Halting problem decider NO COMP 335 M halts on w M doesnt halt on w 5 We want to reduce the halting problem to the finite language problem

Halting problem decider M w Fall 2004 YES finite language Mw problem NO decider COMP 335 NO YES 6

We need to convert one problem instance to the other problem instance Halting problem decider M w Fall 2004 YES NO convert finite language Mw input problem YES NO

? decider COMP 335 7 Construct machine Mw : On arbitrary input string s Initially, simulates M on inputw Menters a halt state, If accept s ( * inifinite language)

Otherwise, reject Fall 2004 s COMP 335 ( finite language) 8 M halts on w if and only if L( M w ) is infinite *

L( M w ) Fall 2004 COMP 335 9 halting problem decider M w Fall 2004 YES finite language construct M w problem Mw

decider NO COMP 335 NO YES 10 L Take a recursively enumerable language Decision problems: L is empty? L is finite? L contains two different strings of the same length? All these problems are undecidable Fall 2004 COMP 335

11 Theorem: or a recursively enumerable languageL t is undecidable to determine whether L contains two different strings of same length Proof: We will reduce the halting problem to this problem Fall 2004 COMP 335 12 Let M

be the TM with L( M ) L Suppose we have the decider for the two-strings problem: M Two-strings problem decider YES NO L(M ) contains

L(M ) Doesnt contain two equal length strings Fall 2004 COMP 335 13 We will build a decider for the halting problem: YES M w Fall 2004

Halting problem decider NO COMP 335 M halts on w M doesnt halt on w 14 We want to reduce the halting problem to

the empty language problem Halting problem decider M w Fall 2004 M w Two-strings problem decider COMP 335 YES YES NO NO

15 We need to convert one problem instance to the other problem instance Halting problem decider M w Fall 2004 convert M Two-strings w problem inputs decider ? COMP 335 YES

YES NO NO 16 Construct machine Mw : On arbitrary input string s Initially, simulate M on input When M enters a halt state,

accept if s a or s b (two equal length strings L( M w ) {a, b} Otherwise, reject Fall 2004 s COMP 335 ( L( M w ) w ) ) 17 M halts on

w if and only if M w accepts two equal length strings Mw Fall 2004 accepts a COMP 335 and b 18 Halting problem decider M

w Fall 2004 construct M w Two-strings problem Mw decider COMP 335 YES YES NO NO 19

Rices Theorem Fall 2004 COMP 335 20 Definition: Non-trivial properties of recursively enumerable languages: any property possessed by some (not all) recursively enumerable languages Fall 2004 COMP 335 21 Some non-trivial properties of

recursively enumerable languages: L is empty L is finite L contains two different strings of the same length Fall 2004 COMP 335 22 Rices Theorem: Any non-trivial property of a recursively enumerable language is undecidable Fall 2004 COMP 335 23

The Post Correspondence Problem Fall 2004 COMP 335 24 Some undecidable problems for context-free languages: Is L(G1 ) L(G2 ) ? G1,G2 are context-free grammars Is context-free grammar

Fall 2004 COMP 335 G ambiguous? 25 We need a tool to prove that the previous problems for context-free languages are undecidable: The Post Correspondence Problem Fall 2004 COMP 335

26 he Post Correspondence Problem Input: Two sequences of n strings A w1, w2 , , wn B v1, v2 , , vn Fall 2004 COMP 335 27 There is a Post Correspondence Solution if there is a sequence i, j , , k such that: PC-solution:

wi w j wk vi v j vk Indices may be repeated or omitted Fall 2004 COMP 335 28 Example: A: w1 100 w2 11 w3 111

B: v1 001 v2 111 v3 11 PC-solution: 2,1,3 w2 w1w3 v2v1v3 11100111 Fall 2004 COMP 335

29 Example: A: w1 00 w2 001 w3 1000 B: v1 0 v2

11 v3 011 There is no solution Because total length of strings from B s smaller than total length of strings from A Fall 2004 COMP 335 30 We will show: 1. The MPC problem is undecidable (by reducing the membership to MPC) 2. The PC problem is undecidable (by reducing MPC to PC)

Fall 2004 COMP 335 31 Theorem: The PC problem is undecidable Proof: We will reduce the MPC problem to the PC problem Fall 2004 COMP 335 32 Some undecidable problems for context-free languages: Is

L(G1 ) L(G2 ) ? G1,G2 are context-free grammars Is context-free grammar ambiguous? G We reduce the PC problem to these problems Fall 2004 COMP 335 33 Theorem: Let G1,G2 be context-free grammars. It is undecidable to determine if L(G1 ) L(G2 )

Proof:Rdeduce the PC problem to this problem Fall 2004 COMP 335 34 Suppose we have a decider for the empty-intersection problem Context-free grammars G1 G2 Fall 2004

L(G1 ) L(G2 ) ? Emptyinterection problem decider COMP 335 YES NO 35 Theorem: For a context-free grammar G , it is undecidable to determine if G is ambiguous

Proof: Fall 2004 Reduce the PC problem to this problem COMP 335 36