Talk:Pushdown automaton

From Wikipedia, the free encyclopedia

I thought a pushdown automton was called a pushdown automaton because of the last in - first out stack system, i.e. the pushdown store. When a new entry is put onto the stack, it "pushes the previous entries down". On the explanation in the article, there's no reason for the pushdown automaton to be particularly deserving of the name, since it needn't be implemented using a punch card system and any other abstract machine that could be implemented using a punch card system would also be a pushdown automaton, by the same logic. 71.197.85.71 03:12, 2 January 2007 (UTC)

I added an example to the page to make it easier to understand how pushdown automation works. Please verify that it's correct. An illustration of the corresponding state diagram would be nice but I don't have time to make one.

"Pushdown automata exist in deterministic and non-deterministic varieties, and the two are not equipotent."

A comment to the information in the page:

Non-deterministic pushdown automata are more potent than deterministic pushdown automata. Some deterministic pushdown automata cannot accept context-free languages accepted by non-deterministic pushdown automata.

[edit] Pushdown automaton as a 7-Tuple?

Isn't a pushdown automaton usually defined as a 6-tuple, instead of a 7-tuple? 82.82.120.201 18:53, 20 Feb 2004 (UTC)

Kozen's "Automata and Computability" defines it in terms of a 7-tuple. However, as he later points out, if we're interested in acceptance by empty stack rather than acceptance by final state then the final state is irrelevant. So it could be dropped leaving a 6-tuple. Is that how you've seen it? I can't say which is more common. Josh Cherry 01:38, 21 Feb 2004 (UTC)

Actually the Wikipedia entry was the first time, that I saw the 7-tuple. I will surf the internet a to find out, which is the more common definition. Usually I saw definitions like 82.83.0.53 10:51, 21 Feb 2004 (UTC)

Added a comment on the possible use of 6-tuples instead. I cite John Reif (Duke University), and point out that if an additional start state and first transition are added, they are equivalent. I felt it against Wikipedia's style to include the citation the article, but I'm probably wrong about that, so please change it if I am. --Mike-de-S

I had added...

Three ways of starting and recognizing are:

• Start with the stack holding Ω, and then say it's done when then stack is empty.
• Start with an empty stack, and have the first state immediately push a symbol (like Ω) onto the stack, and say it's done when the stack is empty.
• Start with an empty stack, and say it's done when a special accept symbol is placed on the stack.

...but canceled, when I realized how incredibly petty the whole conversation is. There are many ways to signal the end of the stack FSM, and many ways to start it.

LionKimbro

[edit] Transition function

I am just a first year student, so I do not dare to correct the original text. But I wonder: Shouldn't the transition function read:

• σ is a finite transition relation (Q × ( Σ & {ε}) × Φ) ( Q × Φ^* )

( instead of ×)

I think that the idea is that it is not necessarily a function since the automaton need not be deterministic. In general it is a relation. However, I think that you're right that something is wrong. I suspect that it should say the the relation is some subset of (Q × ( Σ & {ε}) × Φ) × ( Q × Φ^* ). But I'm no expert either. By the way, please sign your posts. Josh Cherry 00:13, 12 Oct 2004 (UTC)

[edit] NPDA-DPDA equivalence

I seem to recall that NPDA and DPDA are equivalent, as any NFA of n states can be written as a DFA of 2ⁿ states (since there are only 2^n possible state combinations an NFA can be in). Thus I don't think that a DPDA is "strictly weaker" than an NPDA, though I could be misremembering (it's not like I've had to use this since getting my master's degree or anything). Or does the nondeterminism also apply to the stack? 207.171.180.101 23:06, 6 September 2006 (UTC)

No, NFAs (nondeterministic finite automata) and DFAs (deterministic finite automata) are equivalent. These are finite automata, but we are talking about pushdown automata. NPDAs are strictly more powerful than DPDAs. --Spoon! 02:57, 14 December 2006 (UTC)

For example, the language of even-length palindromes ww^R (where w is a string and w^R means the reverse of w) is context-free, but cannot be recognized by any DPDA. --Spoon! 01:01, 9 January 2007 (UTC)