CENG491 are more powerful than 1-PDAs. 2-PDAs have 2

 

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.

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

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 = {| M is a PDA and L(M) is an
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.