[PDF] [PDF] Solution - CS5371 Theory of Computation

View - Download [PDF] Solution - CS5371 Theory of Computation

Previous PDF

Next PDF

CS5371 Theory of Computation

Homework 3 (Suggested Solution)

1. Ans.The languagef0n1n2njn¸1gis not context-free, so that it cannot be recognized by a 1-PDA. However, we can easily design a 2-PDA to recognize this language as follows (LetS1andS2be the two stacks in the 2-PDA): 1. For each 0 it reads, push a 0 inS1and push a 0 inS2 2.

For each 1 it reads, pop a 0 fromS1

3.

For each 2 it reads, pop a 0 fromS2

4. If at any step, we discover the input string is not in correct order (e.g., a 0 is read after 1 is read), we reject the input string 5. IfS1andS2become just empty at the end, we accept the input string Thus, we have found a language that can be recognized by some 2-PDA but not by any 1- PDA. On the other hand, if a language can be recognized by a 1-PDA, it must be recognized by some 2-PDA. Therefore, 2-PDAs are more powerful than 1-PDAs. 2. Ans.If a languageLis decidable, there exists a deciderDthat decidesL. Then, we can construct an enumeratorEthat enumerates the strings ofLin the desired ordering (shorter string ¯rst, then lexicographical order) as follows:

E= \On any input,

1. Ignore the input

2. Fork= 1;2;:::

i. ii.

IfDaccepts, print the string"

Conversely, if some enumeratorEenumerates the strings ofLin the desired ordering, then eitherLis a ¯nite set so that it is decidable, or ifLis an in¯nite set, we can construct a

TMDbased onEas follows:

D= \On inputw,

1. RunE

i.

For every stringsprinted byE, ifs=w, acceptw

ii.

Else ifs < win the desired ordering, continue

iii.

Else ifs > w, rejectw"

Since at most a ¯nite number of strings ofLare smaller thanwin the desired ordering, so after a ¯nite number of strings are printed byE, we can decide ifwis inLor not. So,

Druns in ¯nite steps and is thus a decider.

3. LetS=fhMi jMis a DFA that acceptswwhenever it accepts the reverse ofwg. (a) Ans.An example of a DFA inS: A DFA that accepts all strings. (b) Ans.To showSis decidable, we construct a deciderDforSas follows (LetCbe a

TM that decidesEQDFA):

1

D= \On inputhMi,

1. Construct an NFAM0such thatL(M0) =fwRjw2L(M)g

2. ConvertM0into an equivalent DFAM00

3. UseCto compareL(M00) andL(M)

4. IfL(M00) =L(M), accept. Else, reject.

In the above TM, Step 1 can be done by convertingMintoM0in ¯nite steps. The idea is to (i) reverse the directions of all transition arrows inM, (ii) create a new stateq0inM0, and connectsq0to each original ¯nal states ofMwith"-transitions, and (iii) make the original start state ofMa ¯nal state ofM0. It is easy to check thatL(M0) =fwRjw2L(M)g. Also, both Step 2 and Step 3 can be done in ¯nite steps, as we learnt from the lectures (See Notes 4 pages 13{15, and Notes 12 pages 16{17). So,Druns in ¯nite steps and is thus a decider. 4. Ans.LetPALDFA=fhMi jMis a DFA that accepts some palindromeg. To show PAL DFAis decidable, we construct a deciderDforPALDFAas follows (LetKbe a

TM that decidesECFG):

D= \On inputhMi,

1. Construct a PDAPsuch thatL(P) =fwjwis a palindromeg

2. Construct a PDAP0such thatL(P0) =L(P)\L(M)

3. ConvertP0into an equivalent CFGG

4. UseKto check ifL(G) is empty.

5. IfL(G) is empty, reject. Else, accept.

In the above TM, Step 1 can be done in ¯nite steps. Step 2 is based on Prob 2.18 and can be done in ¯nite steps. Step 3 is the conversion of PDA into an equivalent CFG, which can be done in ¯nite steps (See Notes 8, pages 28{34). Step 4 is done in ¯nite steps, because the deciderKcan check whether the language of a CFG is empty (For the existence ofK, see Notes 12, pages 20{21). In summary,Druns in ¯nite steps for any input, and is thus a decider. 5.

Ans.LetCbe the language

C CFG=fhG;ki jGis a CFG andL(G) contains exactlykstrings wherek¸0 ork=1g In this problem, we are given a deciderDthat decides if the language of a CFG is in¯nite. Then, we can show thatCis decidable, by ¯nding a corresponding deciderFas follows:

F= \On inputhG;ki,

1. UseDto check ifL(G) is an in¯nite set.

2. There are four cases:

i.

If yes, andk=1, accept.

ii.

If yes, butk6=1, reject.

iii.

If no, butk=1, reject.

iv.

If no, andk6=1, continue.

3. Compute the pumping lengthpfor the grammarG.

2

4. Setcountto be 0.

5. Forx= 1;2;:::;p

i.

For all stringswith length =x,

Check ifscan be generated byG; if so, incrementcountby 1.

6. Ifcount=k, accept. Else, reject.

In the above TMF, Steps 1{2 correctly answer the case whereL(G) is an in¯nite set, or k=1. So, after Step 2, we only deal with a grammarGwhose language is a ¯nite set, and our task is to check whether the language size is exactlyk. To do so, the loop in Step

5 counts all string that can be generated byG, whose length is at most the pumping length

p. Because we know thatL(G) is ¯nite, we are sure that no strings ofL(G) can be longer thanp. In other words, the valuecountcorrectly computes the exact number of strings in L(G). So, Step 6 can check correctly answer the case whenL(G) is ¯nite, andkis ¯nite. Finally, it is easy to check that each step runs in ¯nite number of steps. Thus,Fis a decider, so thatCis a decidable language. 3quotesdbs_dbs9.pdfusesText_15

[PDF] let us java pdf

[PDF] let x1 1 and xn+1=2 1/xn

[PDF] let x1=1 and xn 1=3xn^2

[PDF] let xn be a sequence such that there exists a 0 c 1 such that

[PDF] letra cancion bandolero paris latino

[PDF] letter and sound assessment form

[PDF] letter coding examples

[PDF] letter coding tricks

[PDF] letter granting permission to use copyrighted music

[PDF] letter identification assessment free

[PDF] letter identification assessment pdf

[PDF] letter of acceptance of appointment as director

[PDF] letter of appointment of additional director in private company

[PDF] letter of consent for child to travel with grandparents

[PDF] letter of consent to travel with one parent