Suppose $ G$ is a $ CFG$ with m variables and not right side of production longer than $ l$ . Show that if $ A\Rightarrow^*_G\varepsilon$ , then there is a derivation of no more than $ \frac{l^m1}{l1}$ steps by which $ A$ derives $ \varepsilon$ . How close to this bound can you actually come?
Tag: pushdown
Is this pushdown automaton nondeterministic, as JFLAP states?
There is a tool called JFLAP, which, among other things, can analyze pushdown automata, and find nondeterminism.
In this example it is detecting nondeterminism in state q0
:
The first symbol in the transition represents the symbol read as input; the second symbol represents the symbol extracted from the stack; and the third symbol is the symbol pushed to the stack. λ represents the empty symbol, so this is an empty transition without checking the stack or pushing anything to it.
I am surprised, as that state seems to fulfill the conditions for determinism for pushdown automatons (if only because it only contains a single transition!). I would expect the next state to be q1
under any circumstance.
In comparison, JFLAP doesn’t find any nondeterminism here:
Mind you, the transition is the same, it only changes that this one adds something to the stack. Am I missing something or is JFLAP wrong in the first instance?
How to determine if a language produced by grammar is recognizable by deterministic pushdown automaton (DPDA)?
I have a following grammar: S > aSa  bSb  lambda.
And I have to figure out whether the language produced by this grammar is recognizable by DPDA. I can’t find any theoremas about it. Obviously, it’s a contextfree language and can be recognized by DPA, but what about DPDA?
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.

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.

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:
Use JFlap to generate a pushdown automata for the following constrained regular expression, submit a .jpg of your solution (a+b)mc2nbnam
(a+b)mc2nbnam (a+b)mc2nbnam (a+b)mc2nbnam (a+b)mc2nbnam (a+b)mc2nbnam it only needs to be done once. create using jflap thanks
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?
Deterministic pushdown automaton for a given language
I am trying to make a deterministic pushdown automaton from this language but without success. Here is the language definition:
$ \ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $
Thanks!
Can a NonDeterministic 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 PushDown 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 PushDown 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 nondeterministic 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?