CENG491 Homework 4.31

1. (20pts) Let a k-PDA be a pushdown automaton that has k stacks.

Thus a 0-PDA is an NFA and a 1-PDA is a conventional PDA. You already know that

1-PDAs are more powerful (recognize a larger class of languages) than 0-PDAs.

a. Show that 2-PDAs are more powerful

than 1-PDAs.

2-PDAs have

2 tapes (stacks) and 1-PDAs have only one. 2-PDAs are more powerful than 1-PDAs

because they recognize a larger class of languages. For giving an example; language L= {w |w ? anbncn} cannot be recognized by 1-PDA because it is not a

context-free language (CFL). Proof is:

Suppose this language is context-free; then it has a context-free

grammar. Let p be the

constant associated with this grammar by the Pumping Lemma. Consider the

string apbpcp, which is in L and has length greater than p. By the Pumping Lemma this must be

representable as uvxyz, such that

all uvixyiz are

also in L. Let’s say i=2. This

is impossible, since:

– either v or y cannot contain a mixture of letters

from {a,b,c}; otherwise they would

be in the wrong order for uv2xy2z

– if v or y contain

just ‘a’s, ‘b’s or ‘c’s, then uv2xy2z cannot

maintain the balance between the 3 letters

But

we can design an algorithm for 2-PDA to recognize this language:

Read input a*b*c*

1. Initially PDA is in state qaccept. If an ‘a’ is read,

then push it in stack 1 and go to q1. Else if read a

‘b’ or ‘c’, go to qreject because string cannot

start with a ‘b’ or ‘c’.

2. If it is in state q1 and more ‘a’s

are coming, push it into the stack 1. If a ‘b’ is read, go to state q2 and pop one ‘a’ from stack 1 and push a ‘b’ on stack

2. If a ‘c’ is read after ‘a’s, then go to qreject and stay.

3. If it is in state q2 and more ‘b’s are coming, pop one ‘a’ and push

‘b’ in stack 2. If a ‘c’ is read, then go to state q3 and pop one ‘b’ from

stack 2. If no a is remaining on stack with ‘b’ still in hand, go to qreject. Reject if ‘a’ is

read again.

4. If it is in state q3 and more ‘c’s are coming, pop one ‘b’

from stack 2. Reject if ‘a’ or ‘b’ is read.

5. Accept if both of the stacks are empty, otherwise reject.

2-PDA can

recognize this language in spite of the fact that 1-PDA cannot. Hence, we can

say that 2-PDAs are more powerful than 1-PDAs.

b. Show that 3-PDAs are not more

powerful than 2-PDAs.

2-PDA can simulate

a Turing machine. To show that a 2-stack PDA can simulate a Turing machine, we

let the two stacks simulate the left and right halves of the tape. Let’s use

the top symbol of the right-hand stack to represent the symbol at our current

position on the tape. To move left on the tape, we pop a symbol from the left

stack and push a symbol on the right stack, and to move right on the tape we

pop from the right and push on the left. The stack alphabet is simply the tape

alphabet.

We know

that multi-tape Turing machines, Turing machines which have infinite length

tape that its head can go right or left infinitely, and Turing machines which have

“stay” instruction are equivalent to single-tape Turing machine from our

lectures. We mentioned about complexity is higher with single-tape TM and it take

more time to compute compared to multi-tape TMs but they are actually equivalent.

All variants of Turing machine are equivalent of original Turing machine.

2. (20pts) Show that the collection of decidable languages is

closed under the operation of

a.

concatenation

Let A, B be decidable languages.

The concatenation of languages A and B is the language AB = {xy|x ?

A and y ? B}. Since A and B are decidable languages, it follows

that there exist Turing machines MA and MB that decide

the languages A and B respectively. In order to prove that AB is decidable, we

can construct a Turing machine that decides AB. This machine, MAB

can use the machines MA and MB to decide if a string is

in AB or not. We construct a multi-tape TM MAB that decides A·B:

MAB =

“On input w:

1. Copy w onto the second tape

and reset all heads to the front of the tapes.

2. Run MA on w (first

tape).

3. If MA accepts, run

MB on the rest of w (from where the second head is pointing at).

4. If MB accepts,

accept.

5. Otherwise reject.”

MAB

accepts if MA then MB accept the input w. MAB

is a decider because both MA and MB are deciders, so it

will use a finite number of steps to accept or reject any w, there can’t be any

loop. It is certain than MAB won’t run forever.

b.

complementation

For

any decidable language L, let M be the TM that decides it. We construct a TM ML’

that decides the complement of L (L’):

ML = “On input w:

1.

Run M on w. If it accepts, reject.

2.

Otherwise accept.”

ML’ accepts if M rejects

the input w. ML’ is a decider because M is a decider, so it will use

a finite number of steps to accept or reject any w. There can’t be any loop.

3.

(20pts) Let INFINITEPDA = {

infinite language}. Show that INFINITEPDA is decidable.

We

know that PDA is another version of DFA or NFA with additional memory called

stack with infinite length. Also, we know that PDAs are used for recognizing

context-free languages (CFG). In our lectures, we learnt that ADFA,

ANFA, EDFA, EQDFA, ACFG, and ECFG

are all decidable. Only EQCFG is undecidable. We can design a Turing

machine TMINF-PDA to decide INFINITEPDA.

TMINF-PDA = “On input

where M is a PDA:

1. Convert M to a CFGA and

compute A’s pumping length p.

2. Construct a regular

expression B that contains all strings of length p or more.

3. Construct a CFGC such

that L(C) = L(A) ? L(B).

4. Test L(C) = ?, using ECFG decider D.

5. If D accepts, reject; if D

rejects, accept.”

Intersection of a

CFL and regular language is a CFL. So, C is a CFL. We test C for emptiness by ECFG

decider D. If C is empty we won’t accept it; therefore, it means its

empty when D accepts it. This is why we reject when D accepts it and we accept

when D rejects it.

4.

(20pts) TS (Traveling Salesman) PROBLEM: Given n cities, and distances d (i, j)

between them, what is the minimum distance of a path that visits each city

once?

HAMPATH (Hamiltonian Path)

PROBLEM: Given a graph G, is there a path that goes through each node exactly

once?

a. Reformulate

the TS problem as a Yes/No problem. Call it TS2.

TS2 (Traveling Salesman) PROBLEM: Given n cities, and

distances d (i, j) between them, and a positive number k, is there a path that

visits each city once and has length ? k?

b. Given

that the HAMPATH problem is NP-complete, show that TS2 is NP-complete.

We have to show that HAMPATH ?P

TS2

Suppose we can

solve any TS2 problem. Given a HAMPATH problem, transform it into TS2 as

follows:

• If there is a

connection between vertex i and vertex j, set d(i, j) = 1.

• If there is no

connection between vertex i and vertex j, set d(i, j) = 10.

• Set k = n

(number of vertices)

If TS2 finds a

path of length ? n (actually, we have length = n) it is the one we are looking

for. Clearly, this reduction is of polynomial type.