## Are endmarkers necessary for Deterministic Pushdown Automata?

In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to accept as arguments triples $$(q, \sigma, \gamma)$$ with $$\gamma$$ that might be a right endmarker symbol. It is written: “The right endmarker delimits the input string and is a necessary addition. With NPDAs, we could guess where the end of the input string was, but with DPDAs we have no such luxury.” (p. 176). Can we show that this condition is necessary? Can we give an example of a language accepted by this kind of DPDA’s that is not accepted by any DPDA whose transition function has no argument with an endmarker?

Posted on Categories proxies

## Pushdown Automata for number of a less than 2 times number of b

Suppose we want to design a pushdown automata for $$L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$$, can anyone check whether my automata works?

we have 4 states $$\{q_0,q_1,q_2,q_3 \}$$, three stack symbols $$\{S,A,B \}$$, start state $$q_0$$, accept state $$q_3$$, we have rules as following: $$q_0$$ accepts nothing and push $$S$$ onto stack to $$q_1$$

$$q_1$$ reads $$a$$ and pops $$B$$, remain in $$q_1$$

$$q_1$$ reads $$a$$ and pushes $$A$$, remain in $$q_1$$

$$q_1$$ reads $$b$$ and pushes $$BB$$, remain in $$q_1$$

$$q_1$$ reads $$b$$ and pops$$AA$$, remain in $$q_1$$

$$q_1$$ reads $$b$$ and pops$$A$$ and pushes $$B$$, remain in $$q_1$$

$$q_1$$ reads nothing and pops $$B$$, go to $$q_2$$

$$q_2$$ reads nothing and pops $$B$$, remain in $$q_2$$

$$q_2$$ reads nothing and pops $$S$$, go to $$p_3$$

## Pushdown Automata – constructing a PDA to recognise a language with at least as many as as bs

I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question)

W = {w ∈ {a, b}^* | w contains at least as many as as bs} 

My thought process so far has been this:

 1. Start off in q0 (q0 being an accept state)  2. add a $to the start of the stack (so you can see when the stack is empty), then transition to q1 (not an accept state). 3. If you receive an a: - if there is an a at the top of the stack, push the a on. - if there is a b at the top of the stack, pop the b. - if there is nothing on the top of the stack, push the a on. 4. If you receive a b: - if there is an a at the top of the stack, pop the a. - if there is a b at the top of the stack, push the b on. - if there is nothing on the top of the stack push the b on. 5. Once there is no more input: - if there is a$   at the top of the stack, transition to q3 (q3 being an accept state) - this means there was an equal number of as and bs   - if there is an a at the top of the stack, transition to q3 (q3 being an accept state) - this means there was more as than bs   if there is a b at the top of the stack, it means there was more bs than as, and thus we stay in q2, which is not an accept state. 

(Sorry if this is hard to understand, I am not sure how to link those transition diagrams of the PDA’s I’ve seen in some posts, if someone can tell me how to create one and link it in the post, I can update the post to be more understandable if needed)

I have a few questions:

1. Is this approach correct?
2. Is the it correct to assume the machine is smart enough to know that if there isn’t a b at the top of the stack, and I receive an a, it will push that a onto the stack (something like (q1, a, ε) -> (q1, a) to cover both cases where there is an a on the top of the stack and also the case where the stack has nothing in it))
3. Do I need to push a $at the start from q0 to q1 in the transition diagram (I’ve seen this to be the case for all PDAs on my lecture slide – which makes me think is it necessary to include if all machines need to do this – why is it not just implied?) 4. I am ok to have 2 different scenarios to go to q2 right? Or would I be better doing something in q1, where if I have reached the end of my input queue, keep popping off as on the top of the stack until I reach the$ , then transition to q2?

Sorry if anything is unclear – I am not super familiar with PDAs and the way to describe things – please let me know if I need to clarify anything.

Posted on Categories proxies

## Pushdown Automata – can you have multiple transition functions options between 2 states?

I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states?

For example,

 - if you have a 1 and the stack is empty, push it on the stack, and transition to q1  - if you have a 0 and the stack is empty, push it on the stack, and transition to q1  - if you have a 1 and there is a 1 on the stack, push it on the stack, and transition to q1  - if you have a 1 and there is a 0 on the stack, pop the 0 off, and transition to q1  - if you have a 0 and there is a 0 or 1 on the stack, push it on the stack and stay in q0 

I was wondering if this is allowed, and it knows what to do given the scenario?

Sorry if this is obvious, I have been looking at some PDAs and haven’t seen any that have multiple options to transition between states and was wondering if it was allowed.

Posted on Categories proxies

## Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

Design a Pushdown Automata, accepting either by final state or by empty stack to accept the set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s

This is a homework question, but not graded.

I’m not looking for the answer, right now I’m just trying to understand the question. I don’t understand what sort of words would be accepted and what would be rejected. For example, I can’t understand whether the following word would be accepted:

011011 ; where 01 is prefix and 1011 is suffix
011011 ; where 011 is prefix and 011 is suffix
011011 ; where 0110 is prefix and 11 is suffix

I guess my question is this: Given a word, how do I know which part is the prefix? I don’t think I can proceed with the question unless this part is clear.

Please try to give an explanation without the actual PDA answer, I’d like to try it myself first.

Thanks!

Posted on Categories proxies

## A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM.

On the other hand a PDA with one stack is capable to recognise only context-free languages.

Hence there is a kind of a gap between the class of PDA with one stack and the class of PDA with two stacks which should be capable to recognise only context-sensitive languages.

I feel like it should be already an examined question, but I couldn’t find an answer: what restrictions should we apply to a PDA with two stacks in order to make it equivalent to a Linear-bounded automaton?

Posted on Categories proxies

## It is decidable whether a pushdown automaton will accept a word?

I’m asking myself if the problem of decide whether a push down automaton will accept a word is decidable.

I would say that you can simulate a push down automaton with a Turing Machine and, if it doesn’t loop forever, accept the word when the automaton accepts, or reject when it does. In this case, the problem of decide if a push down automaton accept a word would be semi-decidable. But I’m not sure if that is correct and also, I can’t find a way to prove if it is decidable or not.

Any ideas here?

Posted on Categories proxies

## Why do pushdown automata use a stack?

I’m taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?

## How to visualize non-deterministic pushdown automata?

My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize the automaton in action.

What mean in visualizing is, for example, this, a non-deterministic finite automaton that accepts a*+(a.b)*. You can actually try it here. In the lower left corner there is a input field for the word you wanna try and on it’s right side there is a button that starts the process. For each letter being consumed you have to click once inside the canvas, or you can select the “Leitura automática” button for automatic reading. BTW, the source code is here, even though I don’t expect anyone to understand it, it is not well written and the documentation is almost non-existent (and it’s also written in Portuguese).

I read in the internet about a deterministic PA, but this approach with the single stack is not helpful if I wanna build automata that can follow multiple paths at once(like my finite non-pushdown one, that tests all possible paths at once, instead of trying one and backtracking if it fails). So I don’t know if I’m in the right place, but my question is: how can I do something similar for a non-deterministic pushdown automata?

Posted on Categories proxies

## Pushdown automaton help [newbie]

I’m trying to understand how push-down automata work, for example in the case that the requirements are double the a’s that of b’s and that lambda ∈ L.

First of all, I understand that the language we refer to is the following: L = {ai bj | i, j> = 0 ^ i = 2j}* and my proposal is as follows

δ(q0, λ, λ) ={[q1, C]}

δ(q1, a, A) ={[q2, A]}

δ(q1, a, C) ={[q2, C]}

δ(q1, b, B) ={[q3, B]}

δ(q1, b, C) ={[q3, C]}

δ(q1, a, B) ={[q1, λ]}

δ(q1, b, A) ={[q1, λ]}

δ(q1, λ, C) ={[q5, λ]}

δ(q2, λ, λ) ={[q1, A]}

δ(q3, λ, λ) ={[q4, B]}

δ(q4, λ, λ) ={[q1, B]}

Could someone tell me if I’m right? Thank you.