People who code: we want your input. Take the Survey

# Tag Info

## Hot answers tagged pushdown-automata

37

There are several possible layers to your question. Why must PDAs have a stack? -- By definition! That's just how it is. But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition. Why is it interesting? -- See reinierpost's ...

27

OmG and Raphael have already answered your question: pushdown automata use a stack because they're defined that way if they didn't use a stack, what you'd get is a different type of automaton, with different properties At this point you may ask: why does my professor present the pushdown automaton, not some other kind of automaton? What makes the pushdown ...

15

If you change the stack to the queue or multiple stacks, the power of computation will be increased! (as you know, we can model a queue with two stacks). If we use a queue, it can be powerful as a Turing machine. However, the computation power of a push-down automaton is not that much! You can know more about that here.

14

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet. Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-valid" computations of a TM can be coded as strings of a CFG. This is Lemma 8.7 of Introduction to Automata Theory by Hopcroft and Ullman. The authors refer for ...

11

You needn't determine the end of "first part". Note $L$ is exactly the set of strings satisfying the following three constraints: Its length is even. It only contains $a$ and $b$. The first $b$ appears in its latter half. Constraints 1 and 2 are easy to check. To check constraint 3, the DPDA can push a symbol to its stack each time it reads a character ...

10

A machine using two pushdowns accepts the recursively enumerable languages. So there is a lot to choose from. Look for your favourite non-context-free language, and build a two-stack machine for it! (added. see also the answer obtained via our sistersite math) The languages $L_1 = \{ a^nb^nc^n \mid n\ge 1 \}$ and $L_2 = \{ a^nb^ma^nb^m \mid m,n\ge 1 \}$ are ...

10

I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter. Searching the web does also give a negative answer, with counter example, on stackoverflow by a member of CS (notation adapted): $(a+b+c)^*WcW^R$, where $W \in (a+b)^+$; this is non-...

9

David S. Wise provides in his paper A strong pumping lemma for context-free languages a strong pumping lemma which is equivalent to being context-free. He also provides an additional equivalent condition (property 3 on page 362) which he claims could be viewed as an analog of the Myhill-Nerode theorem. As an application of the latter, he shows that $\{ a^nba^... 8 Quite simply, the mechanism is magic. The idea of non-determinism is that it simply knows which way it should take in order to accept the word, and it goes that way. If there are multiple ways, it goes one of them. Non-determinism can't be implemented as such in real hardware. We simulate it using techniques such as backtracking. But it's primarily a ... 8 The langauge is regular, so answers 1–4 are all correct. The (deterministic) automaton has seven states,$0, \dots, 6$corresponding to the remainder when the number is divided by 7. The initial state is$0$, which is also the only accepting state. We adopt the convention that the empty string represents zero (as does the string "$0$", ... 8 Unfortunately the problem is not computable. It is undecidable even to tell if two arbitrary PDAs are equivalent; minimizing a PDA is even harder. 8 Non-determinism is the same concept in all contexts – the machine is allowed several options to proceed at any given point. However, the semantics are a bit different since DFAs/NFAs and PDAs always define total functions, while Turing machines (deterministic or non-deterministic) in general define partial functions. A partial function is one defined only ... 8 The main (and only) difference between DPDA and NPDA is that DPDAs are deterministic, whereas NPDAs are non-deterministic. With some abuse of notation, we can say that NPDAs are a generalization of DPDAs: every DPDA can be simulated by an NPDA, but the converse doesn't hold (there are context-free languages which cannot be accepted by a DPDA). The main ... 8 The language$\{a^nb^nc^k \mid n,k \ge 1\} \cup \{a^nb^kc^n \mid n,k \ge 1\}$I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can push the$a$'s, but we do not know when to pop (compare with$b$'s or with$c$'s?) The language$L = \{ a^nb^nc^k \mid n,k \ge 1\} \cup \{d\;a^nb^kc^n \mid n,...

8

DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily deterministic CFL.

7

Note [2019-07-30] The proof is wrong ... the question is more complicated than it sounds. After a failed attempt here it is another idea. If we intersect $L$ with the regular language $L_{reg} = 0^*10^*10^*10^*$ we get a CF language. Perhaps we can have more luck if we use $L_{reg}' = 0^*10^*10^*10^*10^*$ (a string with exactly 4 1s). Let $L_1 = L \cap ... 7 You write So, I already know that$L = \{ww \mid w \in (0,1)*\}$is not context free. Since CFL are not closed under complement its complement$L'$is a CFL Indeed$L'$is context-free, but your argumentation is ...eeuh... nonsense. Shure, CFL are not closed under complement, meaning there exist context-free languages of which the complement is not ... 7 Just like any automaton, a PDA is nondeterministic if (and only if) the transition relation is not a function, that is there are configurations that have multiple possible succeeding configurations. If this is the case for reachable configurations, this means that a non-deterministic automaton has inputs for which there are multiple computations. Here, the ... 7 I answered basically the same question (put more generally) here. The argument in short: if you could do this, you could decide universality, and a couple of other undecidable properties of PDA/CFG. Hence, by reduction, there can be no such minimizer. 7 That's not how non-determinism works, though perhaps it's how you'd simulate it in real life. Here are several ways of thinking about non-determinism. The genie. Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if ... 7 The difference between DPDA and NPDA is that in NPDA there may be more than one possible transition from a single state given input symbol and stack symbol, while in a DPDA there is only one transition. So, computation of a NPDA looks like a tree, i.e., different branches for different computation paths. Computation halts when you reach a "leaf". You can ... 7 Let me start with a grammar for the language of words of the form$x\#x^R$: $$S \to aSa \mid bSb \mid \#$$ This is our starting point. Now there are two interpretations of the term subsequence. Under the first interpretation, a subsequence is obtained by removing any number of symbols. This just means that we can omit the second side of each production of ... 6 The result is proved in Ginsburg and Greibach, Deterministic context free languages, Inform. Control 9(6), 620–648, 1966, Theorem 4.1 on page 24 (643). However, the proof looks somewhat different. 6 There is a very nice characterization of context-free languages (credited to Wechler) in the paper by Berstel and Boasson, Towards an algebraic theory of context-free languages. Let me introduce a few definitions in order to state this result (Theorem 3.1 in the paper). The polynomial closure$Pol(\mathcal{L})$of a class$\mathcal{L}$of languages of$A^*$... 6 Yes, this is an example of an informal explanation that is not quite true. A PDA is deterministic if (at any moment) it can make at most one legal computational step. This is a local property, a condition on a single step, and not on a computation. The statement "If only one computation exists for all accepted strings" is a global property, a statement on ... 6 The more common term is the "product construction". The product of a PDA and a DFA is a PDA whose state space is the Cartesian product of the states of the two automata (just like in two DFAs), the transition function is similar to the product construction in DFAs, only the PDA component can act on the stack. 6 The intersection of two context-free languages can be non-context-free. The classical example is $$\{ a^n b^n c^m : n,m \geq 0 \} \cap \{ a^m b^n c^n : n,m \geq 0 \} = \{ a^n b^n c^n : n \geq 0 \}.$$ So in general you cannot simulate the intersection of two NPDAs with an NPDA. 6 I think this is possible for the subclass of CFLs that are permutation-invariant with a binary alphabet. These correspond to type$\langle 1,1\rangle$quantifier languages comparing the cardinalities of two sets. [1] characterizes such languages accepted by DPDA by the equivalent semilinear sets, and states at the end that quantifier languages accepted by ... 6 If$L_1,L_2$are two disjoint context-free languages which are not inherently ambiguous, then$L_1 \cup L_2$is also a context-free language which is not inherently ambiguous. The reason is simple: starting with context-free grammars for$L_1,L_2$with start symbols$S_1,S_2$(respectively) and otherwise disjoint non-terminals, you can construct an ... 6 There is a standard construction to do this, discussed in all formal languages/automata courses. It results in gigantic grammars, often with lots of useless productions and nonterminals. Added, as requested by Nehorai: Take a PDA$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \varnothing)$that accepts$L = \mathcal{N}(M)\$ by empty stack (if you have a PDA ...

Only top voted, non community-wiki answers of a minimum length are eligible