[PDF] Homework 8 Solutions Consider the emptiness problem for

View - Download Homework 8 Solutions

Previous PDF

Next PDF

CS 341: Foundations of Computer Science II

Prof. Marvin Nakayama

Homework 8 Solutions

1. Consider the decision problem of testing whether a DFA and a regular expression are

equivalent. Express this problem as a language and show that it is decidable.

Answer:Define the language as

C={?M,R? |Mis a DFA andRis a regular expression withL(M) =L(R)}. Recall that the proof of Theorem 4.5 defines a Turing machineFthat decides the languageEQDFA={?A,B? |AandBare DFAs andL(A) =L(B)}. Then the following Turing machineTdecidesC: T="On input?M,R?, whereMis a DFA andRis a regular expression:

1.ConvertRinto a DFADRusing the algorithm in the

proof of Kleene"s Theorem.

2.Run TM deciderFfrom Theorem 4.5 on input?M,DR?.

3.IfFaccepts,accept. IfFrejects,reject."

2. Consider the decision problem of testing whether a CFG generates the empty string.

Express this problem as a language and show that it is decidable.

Answer:The language of the decision problem is

Aε

CFG={?G? |Gis a CFG that generatesε}.

If a CFGG= (V,Σ,R,S)includes the ruleS→ε, then clearlyGcan generate ε. ButGcould still generateεeven if it doesn"t include the ruleS→ε. For example, ifGhas rulesS→XY,X→aY|ε, andY→baX|ε, then the derivation S?XY?εY?εε=εshows thatε?L(G), even thoughGdoesn"t include the ruleS→ε. So it"s not sufficient to simply check ifGincludes the ruleS→εto determine ifε?L(G). But if we have a CFGG?= (V?,Σ,R?,S?)that is in Chomsky normal form, thenG? generatesεif and only ifS?→εis a rule inG?. Thus, we first convert the CFGG into an equivalent CFGG?= (V?,Σ,R?,S?)in Chomsky normal form. IfS?→εis a rule inG?, then clearlyG?generatesε, soGalso generatesεsinceL(G) =L(G?). SinceG?is in Chomsky normal form, the only possibleε-rule inG?isS?→ε, so the only way we can haveε?L(G?)is ifG?includes the ruleS?→εinR. Hence, if 1 G?does not include the ruleS?→ε, thenε??L(G?). Thus, a Turing machine that decidesAεCFGis as follows:

M="On input?G?, whereGis a CFG:

1.ConvertGinto an equivalent CFGG?= (V?,Σ,R?,S?)

in Chomsky normal form.

2.IfG?includes the ruleS?→ε,accept. Otherwise,reject."

3. LetΣ ={0,1}, and consider the decision problem of testing whether a regular

expression with alphabetΣgenerates at least one stringwthat has111as a substring. Express this problem as a language and show that it is decidable.

Answer:The language of the decision problem is

A={ ?R? |Ris a regular expression describing a language overΣcontaining at least one stringwthat has111as a substring (i.e.,w=x111yfor somexandy)}. Define the languageC={w?Σ?|whas111as a substring}. Note thatCis a regular language with regular expression(0?1)?111(0?1)?and is recognized by the following DFADC: 1234
0 1 0 1 0 1 0,1 Now consider any regular expressionRwith alphabetΣ. IfL(R)∩C?=∅, thenR generates a string having111as a substring, so?R? ?A. Also, ifL(R)∩C=∅, thenRdoes not generate any string having111as a substring, so?R? ??A. By Kleene"s Theorem, sinceL(R)is described by regular expressionR,L(R)must be a regular language. SinceCandL(R)are regular languages,C∩L(R)is regular since the class of regular languages is closed under intersection, as was shown in an earlier homework. Thus,C∩L(R)has some DFADC∩L(R). Theorem 4.4 shows thatEDFA= {?B? |Bis a DFA withL(B) =∅}is decidable, so there is a Turing machineHthat decidesEDFA. We apply TMHto?DC∩L(R)?to determine ifC∩L(R) =∅. Putting this all together gives us the following Turing machineTto decideA:

T="On input?R?, whereRis a regular expression:

1.ConvertRinto a DFADRusing the algorithm in the

proof of Kleene"s Theorem.

2.Construct a DFADC∩L(R)for languageC∩L(R)

from the DFAsDCandDR.

3.Run TMHthat decidesEDFAon input?DC∩L(R)?.

4.IfHaccepts,reject. IfHrejects,accept."

2

4. Consider the emptiness problem for Turing machines:

E

TM={?M? |Mis a Turing machine withL(M) =∅}.

Show thatETMis co-Turing-recognizable. (A languageLis co-Turing-recognizable if its complement Lis Turing-recognizable.) Note that the complement ofETMis

ETM={?M? |Mis a Turing machine withL(M)?=∅}.

(Actually, ETMalso contains all?M?such that?M?is not a valid Turing-machine encoding, but we will ignore this technicality.) Answer:We need to show there is a Turing machine that recognizes

ETM, the com-

plement ofETM. Lets1,s2,s3,...be a list of all strings inΣ?. For a given Turing machineM, we want to determine if any of the stringss1,s2,s3,...is accepted by M. IfMaccepts at least one stringsi, thenL(M)?=∅, so?M? ?

ETM; ifM

accepts none of the strings, thenL(M) =∅, so?M? ??

ETM. However, we cannot

just runMsequentially on the stringss1,s2,s3,.... For example, supposeMaccepts s

2but loops ons1. SinceMacceptss2, we have that?M? ?

ETM. But if we runM

sequentially ons1,s2,s3,..., we never get past the first string. The following Turing machine avoids this problem and recognizes ETM:

R="On input?M?, whereMis a Turing machine:

1.Repeat the following fori= 1,2,3,....

2.RunMforisteps on each inputs1,s2,...,si.

3.If any computation accepts,accept.

3quotesdbs_dbs21.pdfusesText_27

[PDF] is expedia good for car rentals

[PDF] is fog a colloid

[PDF] is form 8332 necessary

[PDF] is france constitution written or unwritten

[PDF] is full fat milk homogeneous or heterogeneous

[PDF] is glucose a crystalloid

[PDF] is green a primary color

[PDF] is hamburg a rich city

[PDF] is hand sanitizer dangerous goods

[PDF] is handset leasing profitable for telecom companies

[PDF] is high alkalinity in drinking water bad

[PDF] is interest income taxable in singapore

[PDF] is iphone packaging recyclable

[PDF] is iron a pure substance

[PDF] is iron filings a mixture