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

  • Environmental Health Health Hazards in Public Schools

    Environmental Health Health Hazards in Public Schools

    The primary source for asbestos exposure is though heating systems and acoustic insulations. ... Outside Lewis Central High School Businesses Most Responsible for Toxics Outside Lewis Central High School Gerald W Kirn Junior High School Chemicals Most Responsible for the...
  • Uveitis - University of Jordan

    Uveitis - University of Jordan

    Other causes of granulomatous uveitis, such as Vogt-Koyanagi-Harada disease, sarcoidosis, tuberculosis, and syphilis should be considered. Treatment of sympathetic ophthalmia consists of systemic anti-inflammatory agents with high dose oral corticosteroid as the drug of choice. However, if the ...
  • NCEB Building Your Brand flyer - Institute of Internal Auditors

    NCEB Building Your Brand flyer - Institute of Internal Auditors

    Building Your Brand as an Emerging Leader Thursday, April 18, 2013 2:00 - 4:00 pm Chevron Building 2001 Diamond Boulevard Concord, California ... Arial Calibri Arial Black Default Design PhotoImpact Pro Image PowerPoint Presentation ...
  • Measurement of Severity from Claims Data

    Measurement of Severity from Claims Data

    Measurement of Severity from Claims Data. This is a lecture by professor Alemi about how to measure severity of illness from claims data within electronic health records. This presentation is based on a patent available for use in different settings...
  • MICROSOFT WORD 2007 - Algonquin College

    MICROSOFT WORD 2007 - Algonquin College

    MICROSOFT WORD 2007. INTERMEDIATE/ADVANCED. CREATE A NEW STYLE BASED ON A SELECTED TEXT. ... Ensure that you have correct spacing and punctuation around the Fill-in field. A CURRENT MAIL MERGE LETTER TO A PRINTER.
  • Institutional Challenges and Opportunities for Competitive ...

    Institutional Challenges and Opportunities for Competitive ...

    For those of you who haven't flown recently, that is known as a commuter airplane. If you are travelling from a major city like New York or Washington to say, Muskogee, OK, the final leg of your trip might be...
  • Student Quality and Reported Student Quality: Higher ...

    Student Quality and Reported Student Quality: Higher ...

    College's Acceptance Decision Table 3 Columns II and IV: Probit Regression College's Acceptance Decision Table 4 : Predicted rather than Actual SAT I Score Interpretation of Point Estimates College X An applicant who scores a 1,000 on the SAT I...
  • Department of Finance and Services

    Department of Finance and Services

    Australian Securities & Investment Commission (ASIC) is Australia's corporate, markets and financial services regulator. Capex Capital Expenditure (CAPEX) is the use of funds by a company to upgrade existing or acquire new physical assets such as property, buildings or equipment.