Languages and Finite Automata - WPI

Languages and Finite Automata - WPI

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

Recently Viewed Presentations

  • School of Social and Community Medicine - www.bristol.ac.uk

    School of Social and Community Medicine - www.bristol.ac.uk

    (Bristol Clinical Commissioning Group) Rachel Anthwal (South West Commissioning Support Unit) The problem. ... Interaction, linkage & exchange. Literature consistently suggests that personal contact b/t researchers & policymakers most effective.
  • Energy Future @ Carleton By Richard Strong, Director

    Energy Future @ Carleton By Richard Strong, Director

    Energy Future @ Carleton By Richard Strong, Director of Facilities Minnesota Fuel Mix for Electricity Carleton Energy Use 1987-2003 Carleton Energy Use 1987-2003 Carleton Energy Use 1987-2003 Cost for Energy 1900-2002 Cost per CCF of Natural Gas Total Annual Cost...
  • Integrating Physical Health with Recovery and Wellness Tools ...

    Integrating Physical Health with Recovery and Wellness Tools ...

    Learning Objectives. Recognize the key elements of a framework for integrating the physical health dimension of wellness and recovery. Identify core strategies used to engage individuals in active self-care
  • Kamanassie Case Study - CSIR

    Kamanassie Case Study - CSIR

    Environment 1 of 7 tasks Task leader - Mike Luger (NS) Core team as for WRC Ecological and Environmental Impacts of Large-scale Groundwater Development in the Table Mountain Group (TMG) Aquifer System WRC project K5/1327 WRC - TMG Introduction Objectives...
  • Understanding and Getting More From The NFPA Process

    Understanding and Getting More From The NFPA Process

    I - The standards making system II - Effectively working within the process to get what you want III - Where are we in the current cycle Part I - NFPA's Codes and Standards Making System The five steps 1)...
  • Factor V Leiden Detection and Genotyping

    Factor V Leiden Detection and Genotyping

    Factor V Leiden Detection and Genotyping August 6, 2008 Marylin Bicak Objective 1. To provide an overview of the Factor V Leiden assay 2. To explain the pathophysiology and epidemiology of the Factor V Leiden mutation.
  • Passo a Passo

    Passo a Passo

    Researcher Links. O British Council, o Conselho Nacional das Fundações Estaduais de Amparo à Pesquisa (Confap) e a Fundação de Amparo à Pesquisa do Estado de São Paulo (Fapesp) lançaram, em 27 de abril de 2015, uma nova chamada do...
  • The Development of Life Purpose in Pepperdine University

    The Development of Life Purpose in Pepperdine University

    Times New Roman Arial Wingdings Arial Black Symbol Arial Narrow Tahoma Pixel Microsoft Graph Chart Microsoft Office Excel Chart The Development of Life Purpose in Pepperdine University Undergraduates Research Hypotheses Research Methodologies Survey Instruments Faith and Spirituality Ego-Identity Status Life...