38

Two bits to this answer; Firstly, the class of languages recognised by Turing Machines is not context sensitive, it's recursively enumerable (context sensitive is the class of languages you get from linear bound automata). The second part, assuming we adjust the question, is that yes, a two-stack PDA is as powerful as a TM. It's mildly simpler to assume ...


36

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


30

If a language $L$ is deterministic, it is accepted by some deterministic push-down automaton, which in turn means there is some LR(1) grammar describing the language, and as every LR(1) grammar is unambiguous, this means that $L$ cannot be inherently ambiguous. Knuth proved this in his paper in which he introduced LR(1) (On the Translation of Languages from ...


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


20

There is no algorithm that given a context-free grammar, decide if a DPDA recognizes the same language and computes it if it exists. Because if such an algorithm existed, we would be able to decide the undecidable problem of the universality of a context-free grammar i.e. whether a given context-free grammar $G$ on $Σ$ recognizes the whole language $Σ^*$. ...


17

You can't go to the bottom of the stack without "forgetting" the rest of the stack. With a Turing machine you can easily go back and forth on the tape. This simple task cannot be done with a pushdown transducer (roughly the same thing as the pushdown automata, but that can write things at each step), but can easily be done with a tape: Read a string $w$ ...


15

No, this is context-free. To accept $a^nb^nc^n$, you need to make sure that three numbers are equal. To accept $a^*b^*c^* \setminus a^nb^nc^n$, you just need to make sure that you're in one of the following three cases: The number of $a$s is different from the number of $b$s; or The number of $a$s is different from the number of $c$s; or The number of $b$s ...


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


13

If you only consider that 'Turing machines can always be made to behave like a stack' you can only conclude that they are at least as powerful as pushdown automata. But in general, yes it is true, Turing machines are more powerful than PDAs. The easiest example would be to show that Turing machines can describe Context Sensitive Languages.


13

Your PDA would also accept strings of the form $a^nb^ic^j$ where $i+j=2n$ and $i,j>0$. For example the string "aaabbbbbc" is accepted. There is no way to tell that there are exactly $n$ $a$'s still remaining on the stack once you've finished reading the $b$'s.


12

Turing machines are indeed more powerful than regular PDAs. However in special case of a PDA with two stacks (TPDA or 2-PDA) the TPDA is equally powerful than a turing automata. The basic idea is that you can simulate the TM's tape using two stacks: in the left stack everything is stored which is left from the head on the Turing-tape, while the symbol ...


12

Here is my approach: I'll show that if you can decide your problem, then you can decide Post's correspondence problem (PCP), which is known to be not decidable. Remember, PCP is a decision problem that asks if in a set of $2$-tuples $P=\{(x_1,y_1),\ldots,(x_n,y_n)\}$ you can build a sequence (incl. repetition) such that the concatenated $x_i$s and the ...


10

Pick the languages: $L_1 = \{a^ib^jc^k | i \neq j \}$ and $L_2 = \{a^ib^jc^k | j \neq k\}$; both are DCFL and $L_3 = 0L_1 \cup L_2$ is DCFL, too. $L_0 = 0^*$ is DCFL (regular) But $L_{conc} = L_0 \cdot L_3 = 0^* L_3$ is not DCFL. Proof: Suppose that $L_{conc}$ (which is the concatenation of two DCFLs) is DCFL. If we intersect $L_{conc}$ with the regular ...


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


10

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


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


9

The halting problem for DPDAs is not only decidable; it is computable in polynomial time. Given a PDA $P$ and an input $x$, you can efficiently test whether $x$ is accepted by $P$. This can be done in time polynomial in the length of $x$ and the size of $P$. In particular, this is a terminating computation, so that means that the acceptance problem (given ...


8

Doesn't that language simply recognize any string in $\{0,1\}^*$ that has at least three $1$s in it? If so, you just need a regular finite deterministic automaton with that can count up to three in order to recognize it. This is because I'm not on the mood to do a direct translation of that grammar, if that is what you really wanted to check :P


8

You are correct. It is easy to show that the syntax of regular expressions is not regular using standard techniques. One possibility is to use a homomorphism (which $\mathrm{REG}$ is closed against) to get rid of all symbols but the parentheses, which leaves you with the Dyck language which is well-known to be non-regular. If in doubt, use the Pumping lemma ...


8

Here is a hint. You need your machine to initially accept part of a word from $L$, consuming the tape as it goes. Then, without consuming anything, you need to find some word from $R$ that will push the machine into a final state. The chosen word from $R$ plays the role of the input word for the second half of the computation. Clearly, non-determinism will ...


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

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


7

A two-way PDA can accept the canonical context-sensitive language $\{0^{n}1^{n}2^{n} | n \geq 1\}$. Such an automaton could work by checking whether the largest prefix of the form $0^{i}1^{j}$ had $i = j$, using the stack, after which it could empty the stack, and check whether the largest suffix of the form $1^{j}2^{k}$ had $j=k$, again using the stack. So $...


7

The following pushdown automaton should do the trick. I publish this only because the existing answer can be improved upon. (Note, I am using $e$ to denote $\epsilon$- (or $\lambda$-) transitions. The idea is that the left-hand part counts the number of $a$'s (modulo 2). Each time it has seen two $a$'s, it pushes $3$ $b$'s onto the stack. ...


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

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

Unfortunately the problem is not computable. It is undecidable even to tell if two arbitrary PDAs are equivalent; minimizing a PDA is even harder.


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