The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text “Introduction to Automata Theory, Languages, and Computation” (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements about a pushdown automata (PDA) which accepts by empty stack, as:

1. $ n$ , the total length of the input, is surely an upper bound on the number of states and stack symbols.

2. One rule could place almost n symbols on the stack.

The following statements were made while the authors were about to make some notes about the decision properties of CFLs(Context Free Languages)

Now here are some points by which I am possibly able to contradict the claim rather than proving it correct.

  1. Suppose $ n$ , is the total length of the input, but as per the design of the PDA it might so happen that to accept the input string all the states of the PDA is not involved, so by this we can’t say that $ n$ is an upper bound on the number of states the PDA has.

  2. Though the PDA accepts by empty stack, it might so happen that a transition function adds more than $ n$ elements on the top of the stack, but at the end on consuming the $ n$ input symbols we can stay on the particular state and use epsilon transitions to just remain in the same state and pop the elements from the stack till it becomes empty. So how can we say that $ n$ is an upper bound on the number elements on the stack? We arrive at a contradiction…

I don’t understand where I am making the mistake, because the same statements are written in the 3rd edition of the book without any changes being made from the second edition which makes it probable that the statement is correct.

I have attached the corresponding portion of the text below: enter image description here

Pushdown automata from a given code for parsing a while statement

I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code:

void compile_while() {   // while ( expression )   if (symbol == SYM_WHILE) {     get_symbol();      if (symbol == SYM_LPARENTHESIS) {       get_symbol();        compile_expression();        if (symbol == SYM_RPARENTHESIS) {         get_symbol();          // zero or more statements: { statement }         if (symbol == SYM_LBRACE) {           get_symbol();            while (is_not_rbrace_or_eof())             compile_statement();            if (symbol == SYM_RBRACE)             get_symbol();           else {             syntax_error_symbol();              exit(EXITCODE_PARSERERROR);           }         } else           // only one statement without {}           compile_statement();       } else         syntax_error_symbol();     } else       syntax_error_symbol();   } else     syntax_error_symbol(); } 

First of all, I don’t understand why we need to construct PDA for it because we can do it without stack too and second, I don’t understand how the pushdown automata for it would look like.

Can someone help me to understand this task and show me how the PDA for it looks like?

Can a Non-Deterministic Pushdown Automata recognize $ \# a^nb^{2^n} \# $ which a TM can?

$ \# a^nb^{2^n} \# $

such that

• The alphabet of the machine is {, a, b, x}.

• The symbol x will never appear on the input a.

• The contents of the tape at completion may be anything.

• The head begins on the lefthand #.

• n ≥ 0.

I know that a Turing machine could recognize this language. But can a NPDA recognize this language too? I am thinking it can but I do not know how to start proving how/why?

Creating a Deterministic Push-Down Automaton for the Union of two languages


Suppose, we have $ L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $ L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$ . Now we want to create a Deterministic Push-Down Automaton for $ L_1\cap L_2$

I’ve created PDA’s for both languages:

$ M’=(Q,\Sigma,\Gamma,\Delta,s,F)$ with $ \Sigma=\{a,b\}$ , $ \Gamma=\{\}$ , $ Q=\{1,2,3,4\}$ , $ F=\{0\}$ , $ s=\{0\}$ and \begin{align} \Delta=\{&(0,a,\lambda,1,\lambda),(0,b,\lambda,0,\lambda)(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,3,\lambda),(2,b,\lambda,2,\lambda)\ &(3,a,\lambda,0,\lambda),(3,b,\lambda,3,\lambda)\} \end{align} where $ \Delta\subseteq Q_{old}\times (\Sigma \cup \{\lambda\})\times(\Gamma\cup \lambda)\times Q_{new}\times\Gamma^*$

and

$ M”=(Q,\Sigma,\Gamma,\Delta,s,F)$ with definitions above and $ \Sigma=\{a,b\}$ , $ \Gamma=\{\}$ , $ Q=\{1,2,3,4,5,6\}$ , $ F=\{6\}$ , $ s=\{1\}$ and \begin{align} \Delta=\{&(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,2,\lambda),(2,b,3,\lambda),(3,a,\lambda,4,\lambda),(3,b,\lambda,1,\lambda),\&(4,a,\lambda,5,\lambda),(4,b,\lambda,3,\lambda),(5,a,\lambda,2,\lambda),(5,b,\lambda,6,\lambda),(6,a,\lambda,6,\lambda),(6,b,\lambda,6,\lambda)\} \end{align}

$ M’$ accepts $ L_1$ and $ M”$ accepts $ L_2$ , but how to construct $ M^{\star}=M’\cap M”$ which accepts $ L_1\cap L_2$ ?

I know, that we could possibly do this with Deterministic Finite Automata, but I want to know how it would work with PDA’s.

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?

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.

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.