Does PDA accept everything?is undecidable? 
P.S. I need the answer ASAP Thanks

---

Request for Question Clarification by mvguy-ga on 29 Oct 2002 08:41 PST

If you would like an answer ASAP, could you please explain more
precisely what it is you want to know?  Thanks.

---

Clarification of Question by joannehuang-ga on 29 Oct 2002 08:48 PST

Just need to justify the claim the question Does a PDA accept
everything?
is undecidable?
What I know is In Automata:The language of all PDAs that accept
everything.
We would have to try every string before declaring that a PDA accepts
everything, but since membership in a CFG (equivalent to a PDA) is
decidable, we determine that a PDA does not accept anything once it
rejects anything.

The question "Does a given PDA accept all strings?" is very much
decidable.

Let our PDA be called P, and consider a PDA P' that accepts only those
strings not accepted by P. The problem is now reduced to deciding
whether P' is empty; if it is, then P accepts all strings, otherwise
not.

Since the language accepted by P' is context-free, there is a grammar
G' such that L(G') = L(P'). The question of whether a grammar can
generate at least one string is decidable -- for example, by
converting to Chomsky normal form -- so we can decide whether L(G') =
L(P') = {}. Hence, our original question is also decidable.

Regards,

leapinglizard

---

Clarification of Answer by leapinglizard-ga on 29 Oct 2002 20:25 PST

My previous answer is incorrect; consider it an object lesson in
meretricious argumentation. The trouble is that context-free languages
are not closed under complement; thus, it isn't always possible to
construct P' from a given P, since there may be no such P'.

Let me get back to you with a correct answer.

---

Clarification of Answer by leapinglizard-ga on 29 Oct 2002 21:17 PST

The question "Does a given PDA accept all strings?" is indeed
undecidable, and user jburnim-ga has given a correct proof in his
comment below. As he points out, the difficulty is in showing that the
set of computation histories for all strings rejected by a Turing
machine M constitutes a context-free language. I thought I would try
to think of a simpler proof, but I've failed.

I did, however, locate a PDF document used in a Computational Theory
course that addresses precisely your question.

Yih-Kuen Tsay, National University of Taiwan
lecture notes on reducibility: original PDF document
http://www.im.ntu.edu.tw/~tsay/courses/theory/ch5slides.pdf


Yih-Kuen Tsay, National University of Taiwan
lecture notes on reducibility: rendered as text
://www.google.ca/search?q=cache:4fhl-09o1McC:www.im.ntu.edu.tw/~tsay/courses/theory/ch5slides.pdf+CFG+all+strings+undecidable&hl=en&ie=UTF-8

The PDF download is rather slow -- I have it crawling along at
0.2KB/s, with no end in sight -- so you may prefer the text rendering.
The latter is not very pretty, and a number of Greek symbols are
missing, but it's readable if you're familiar with the context. You'll
find your problem on page 18.

Here, they call the problem ALL_CFG, and the treatment is identical to
that in jburnim's comment. They assume as a foregone conclusion that
the set of non-accepting computation histories of any Turing machine M
is a context-free language. You'd do best to cite this as a known
result, preferably with reference to a theorem covered in your class
textbook or in a lecture, if applicable.

I apologize for jumping the gun, and hope that your question has
nonetheless been answered to your satisfaction.

Regards,

leapinglizard

---

Clarification of Answer by leapinglizard-ga on 29 Oct 2002 21:20 PST

Oh, and I used the following query to find this document.

Keywords used:
CFG all strings undecidable

Regards,
leapinglizard

It is not decidable whether a PDA accepts all possible strings.

This can be proved by a reduction from the halting problem. 
Essentially, you let V be the set of finite valid executions of a
turing machine M given input x.  You can prove that ~V, the complement
of V, is a context-free language (CFL).  If you could answer the
question "Does the CFL ~V contain all possible strings?", you could
answer "Does V contain no strings?" or "Does M have no valid finite
executions given x?"  Asking whether or not M has any valid finite
executions for a given input x is equivalent to asking whether or not
M halts on input x -- this is the Halting Problem and is not
computable.

The proof that the complement of all finite valid executions of a
turing machine M on input x is a context-free language is a little
complicated.  I would guess that most textbooks on automata and
computability theory would have this proof.  Kozen's "Automata and
Computability" does anyway, which is the source of this answer.

My previous comment actually explains why it is not decidable whether
or not a context-free language contains all possible strings.  I
should have mentioned that because context-free languages are
generated by context-free grammars, which are equivalent to push-down
automatan (PDAs) (as you mentioned in your post), this is also a proof
that it is undecidable whether or not a PDA accepts all strings.

to:jburnim-ga 
thanks for your comment