Talk:Pushdown automaton

Untitled

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 (source).

"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.

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 ${\mathcal {A}}=\left(Q,\Sigma ,\Gamma ,\delta ,q_{0},\#\right)$ 82.83.0.53 10:51, 21 Feb 2004 (UTC)

If you decide to include a formal definition, it should be a "complete" definition, not something based on hit count from Google. PDA is defined as 7-tuple ${\mathcal {A}}=\left(Q,\Sigma ,\Gamma ,\delta ,q_{0},\#,F\right)$, where $F$ denotes the set of final states and cannot be omitted from the definition of PDA. PDAs form a set hierarchy with the most encompassing set being nondeterministic PDAs, then the more restrictive deterministic PDA with final state acceptance and the most restrictive set, deterministic PDAs with empty stack acceptance (This is not a comprehensive list, it only serves to illustrate the point). All of them are 7-tuple, but for example, for DPDA with empty stack acceptance, it holds that $F$ is an empty set - you cannot just ommit it, you need to define it precisely. That's what formal definition is for - one look and you know what kind of PDA it is.oOo

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 $\Omega$, 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 $\Omega$) 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

Both the formal definition and the computation definition should be consistent. In one there is a 7-tuple and the other is only a 6-tuple!!! 189.136.79.171 (talk) 14:58, 8 February 2008 (UTC)

Thomas A. Sudkamp's "Languages and Machines" defines it as a 6-tuple.96.32.143.226 (talk) 04:31, 22 October 2008 (UTC)

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 × ( Σ & {ε}) × Φ) $\rightarrow$ ( Q × Φ^* )

($\rightarrow$ 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)

Quite right. The transitions can be specified as a finite relation (of five tuples) as Josh Cherry states. The preserve the idea of moving from a situation (state, input letter to be read, topmost stack symbol) to another situation (new state, new stack sequence) one sometimes defines a transition function as on the wiki-page. This must introduce the powerset at the righthand side of the arrow, as the automaton may have several choices on the same initial situation. Though mathematically the formulations are close, personally I prefer the relation, since it avoids the powerset. Jochgem 16:40, 30 October 2007 (UTC)

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)

Question added to article by anon

An anon user asked this question in an edit, so I thought I'd answer.

SO I GOT HERE FROM THE PAGE ON COMPUTABILITY THEORY. THEY SHOWED A PROBLEM WHERE AN FSM WOULD FAIL. THE PROBLEM WAS TO SHOW THAT A STRING HAD THE SAME NUMBER OF A'S AS B'S. THEY PROVED HOW A FSM COULD ALIAS A SET OF A'S THAT WERE SUFFICIENTLY FAR ENOUGH APART TO LOOK THE SAME. THUS WHEN COMPARED TO THE NUMBER OF B'S WE GOT A FALSE ACCEPTANCE OF THIS STRING, I.E., WE THOUGHT THAT THE COUNT OF A'S WAS EQUAL TO THE COUNT OF B'S BUT WERE WRONG. CAN YOU SHOW HOW A PUSHDOWN AUTOMATON COULD CORRECTLY SOLVE THIS PROBLEM. I THINK THAT WOULD HELP ME QUICKLY UNDERSTAND THE USEFULNESS AND POWER OF A PUSHDOWN AUTOMATA. THANKS.

Informally: The pushdown automaton pushes each A onto the stack as it reads it in. Then, whem it comes to the string of Bs, it removes the top element of the stack for every B it reads in. If the stack is empty when the end of the input is reached, the automaton succeeds. Cadr 07:28, 4 May 2007 (UTC)

What if B's come before A's? Nxavar (talk) 09:44, 11 September 2012 (UTC)

Missing a formal definition of computation for PDA

I have a background in pure mathematics and for computer science, I am just a beginer. I sometimes feel terrible in reading stuffs (articles, textbooks...) about computer science because of the lack of rigorous mathematical treatment. I don't think you can have a meaningful debate on the merits of a definition (6-tuples or 7-tuples) without formally defining the computation processs under each PDA definition. Having said that, I'd like to point out some inconsistencies between the formal definition and the illustrative example in this Article.

First, by formal definition, the image of $\delta$ is a subset of $Q\times \Phi ^{*}$ where $\Phi ^{*}$ is the set of all strings from $\Phi$ and $\Phi$ is a finite set of the stack alphabet. In the illustrative example, $\delta (q_{0},a,\epsilon )=\{(q_{1},$$A$$)\}$, which impies that $(q_{1},$$A$$)$ is an element of $Q\times \Phi ^{*}$ which in turn implies that $A$ is an element of $\Phi ^{*}$. How is it possible that $A$ is an element of $\Phi ^{*}$?

Secondly, formal definition requires that PDA be 7-tuple whereas the illustrative example consider it a 6-tuple.

Thirdly, there is no explanation of how the machine can get from a situation where the symbol at the top of the stack was $A$ to a situation where the symbol at the top of the stack was A. Keep in mind that every move and hence every change is driven by the transition function and therefore must be explained by the transition function.

In short, we need a formal definition of computation for the formal definition of PDA which we choose and then we need to demonstrate that this pair of definitions works on all situations.

--CBKAtTopsails 19:57, 25 June 2007 (UTC) --CBKAtTopsails 18:01, 27 June 2007 (UTC)

A formal definition of computation seems now part of the wiki-page, based on the notion of computation path. I do not know where this idea comes from, but I feel this is a very bad choice for a definition. For PDA computations the isolated state sequence rarely is of value in technical arguments, instead one combines states and stack contents. In fact when the PDA has only a single state (a normal form for PDA) then a computation path consists of a repetition of that state which is hardly informative. The usual approach is as follows. Define a 'instantaneous description' (or global state) as a triplet (state, input-not-read, stack). Then define a single step (or move) of the PDA as a relation between instantaneous descriptions. Finally define computation as a sequence of steps.

Oh, the definition of determinism is more complex than the suggestion on the wiki-page. It involves both state, input letter and topmost stack symbol. The latter is not present in the underlying finite state automaton. In particular, a PDA may be deterministic, while the underlying FSA is nondeterministic. Jochgem 16:32, 30 October 2007 (UTC)

Diagrams!

Let's make some diagrams, for the love of god! My diagram-making ability is limited to MS Paint, so might anybody be willing to generate something? Otherwise, I'll stick in something temporary. SamuelRiv 03:41, 6 November 2007 (UTC)

The Idea Of Computation Path

The idea of computation path is basically the concept of computation branch in any non-deterministic machine as used in some textbooks. For example, take a look at Michael Sipser's "Introduction to the Theory of Computation".

I believe the reason we need formal definition is we want to establish theorems using rigorous mathematical arguments. Any arguments that cannot tie back to the basic definitions would not be considered rigorous in the mathematical communty. I am not sure about the "usual approach" you mentioned here and what practical purposes it can serve. Let's say, if we accept this "usual approach" to define PDA, can we widely use this definition to establish many important theorems in theoretical computer science? How are you going to prove the following well known theorem in theoretical computer science:

"A language is context-free iff some PDA recognizes it."

Keep in mind that every argument you make in your proof must tie back to your basic definition.

--CBKAtTopsails 17:27, 9 November 2007 (UTC)

Some Additional Comments

"Oh, the definition of determinism is more complex than the suggestion on the wiki-page. It involves both state, input letter and topmost stack symbol. The latter is not present in the underlying finite state automaton."

Response: I do not believe you are reading this page very carefully. The sequence s₁, s₂.....s_n tells you the stack contents. The sequences a₁,a₂...a_n and b₁,b₂....b_n tell you what is being read from the stack ,what is being removed and what is being pushed in. The sequence w₁,w₂....w_nrepresents the input symbols.

"In particular, a PDA may be deterministic, while the underlying FSA is nondeterministic."

Response: I believe a deterministic PDA is just a special case of a non-deterministic PDA in which there is only one branch of computation. One can specify the transition function to obtain a deterministic PDA. If you don't see it that way, maybe you should put up a formal definition for deterministic PDA.

"In fact when the PDA has only a single state (a normal form for PDA) then a computation path consists of a repetition of that state which is hardly informative."

Response: I don't understand the logic in this statement. PDA is not a single state. It is a 6-tuple containing a component called the transition function. When a string is input to the PDA, the transition function generates the computation paths. If you don't think this situation has any meaning, don't create it. You are the one to define the transition function.

--CBKAtTopsails 17:03, 10 November 2007 (UTC)

Dear CBKAtTopsails. Sorry for the confusion I caused. I do very much agree with your opinion that a formal definition for the semantics of a PDA is needed before doing proofs. My problem is that the computation path itself includes only states; it is a state sequence. With this definition every PDA that happens to have only a single state will be deterministic (which is not true). Computation paths should include the stack contents too, and preferably also the input. In this way they record the full (global) state of the automaton, not only the internal (local, finite) state. Jochgem 22:23, 10 November 2007 (UTC)

I think I can understand some of your points here. Presumably, I can go back to rewrite the computation path replacing each q_i with a 4-tuple (q_i, w_i, a_i, s_i) but this will make things look very cumbersome and not add any substance to the definition.

"With this definition every PDA that happens to have only a single state will be deterministic (which is not true)."

Response: I do not see how this definition would force any PDA with a single state into a deterministic one. In fact, if you look at condition (i) of Computation Definition 1, you will notice that this condition allows multiple values of b_i+1 for any given set of q_i, w_i+1 and a_i+1 even when q_i=q_i+1. In this case, you have a non-deterministic PDA.

--CBKAtTopsails 08:11, 11 November 2007 (UTC)

2-PDA

Just learned about the 2-stack pushdown automata in class, yet there's nothing here and there's no page for it...just throwing that out there. ThomasOwens (talk) 23:52, 28 January 2009 (UTC)

Thomas: they are mentioned on this page as equivalent to Turing machines. Jochgem (talk) 09:50, 25 April 2009 (UTC)

On PDA's and context-free languages

In the section PDA and Context-free Languages it says "Where the grammar rewrites a nonterminal, the PDA takes the topmost nonterminal from its stack and replaces it by the right-hand part of a grammatical rule (expand)." But, in fact a nonterminal is associated with a grammar production which may consist of multiple rules (e.g. S -> a b c | d e f is really one production with two rules S -> a b c and S -> d e f). I think we should make it clear that the nonterminal may have more than one "right-hand side" and more than one edge may be added for a particular nonterminal. Furthermore, deciding to transition along an edge in this case will be nondeterministic (thus this method only corresponds to NPDA's). Rehno Lindeque (talk) 16:42, 3 June 2011 (UTC)

GPDA

The section on Generalized PDA is unimportant detail that should be dropped. Since PDA and GPDA are equivalent, and all users of PDAs use the PDA form and not the GPDA form, no general readers of this article need to review this. This appears to be a classroom or textbook exercise in proving equivalences. DBSand (talk) 17:39, 16 June 2012 (UTC)

I think it does have encyclopedic significance as an aspect of PDA theory. It shows that extending a PDA to a GPDA does not increase its language recognition power. Nxavar (talk) 09:36, 11 September 2012 (UTC)

Merge with deterministic pushdown automata article

The commonalities and differences of deterministic and nondeterministic PDAs would be clearer if these two topics were covered in a single article rather than separate, competing articles. DBSand (talk) 17:56, 16 June 2012 (UTC)

Pushdown Transducers

Why is there absolutely no mention of PDTs, other than the page being redirected from the 'Pushdown Transducer' page? We covered this in my Theory of Computation class recently, and it seems like there's no mention of the word Transducer at all on this page, nor is there anything about dealing with outputs other than 'accept' and 'fail'. Ryokenohki (talk) 01:07, 3 May 2013 (UTC)

Gamma-star

I don‘t see why the second Γ in the formal definition‘s explanation of the transition table has an asterisk after it, but the second Q doesn’t…

This comment has been written by User:Theanswertolifetheuniverseandeverything (I don‘t have my password manager with me right now, you can ask later to verify) 185.238.218.42 (talk) 07:30, 16 December 2021 (UTC)

This should become clear from the paragraph immediately after the formal definition ("An element ... input untouched."): a transition takes the automaton into one new state (a member of Q), but is allowed to push a string of many symbols from Γ onto the stack. - Jochen Burghardt (talk) 12:39, 16 December 2021 (UTC)