# Questions tagged [pushdown-automata]

Questions about state machines with a single stack for memory. They characterize the class of context-free languages.

539 questions
Filter by
Sorted by
Tagged with
21 views

### CFGs and Pushdown Automata

Is this the CFG for part (a), S -> AxxyxxA A -> Ax|ε If this is the answer then this grammar would accept &...
7 views

### Construct a pda

Construct the pda that accept following language L * 1 = {a ^ m * b ^ n / 2 * n <= m <= 3n, n >= 1} Trace the operation of M on the string aaaaabb
224 views

### Can PDA model Turing Complete objects if the objects' state are finite?

I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract. I am trying to understand the proofs of Chapter 6. ...
32 views

### 1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts L={a^(n^2)|n≥1}

Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of a an input string is strictly a perfect square number. How can I do this in both approaches?
3k views

### Constructing a PDA for the language $\{a^mb^n | m > n\}$

i saw in a book how to construct a PDA for a case with m is equal to n . It's pretty simple, just push a symbol for every a and pop this symbol for every b that the PDA reads. But, i don't found a way ...
143 views

### PDA for equal number of as and b's where n>=1

How to design Push Down Automata for a language that has equal number of a's and b's where $n \ge 1$? I got how to do it for $n \ge 0$, not able to get it for $n \ge 1$.
57 views

### Can we give an example Context-Free Language that a DPDA can not recognize

Can we give an example Context-Free Language that a DPDA can not recognize. If we DPDA can not recognize can you explain why?
1 vote
771 views

### Understanding this PDA for non-palindromes over {0,1}

I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help ...
1k views

### Are 2 independent PDAs equivalent to a turing machine?

I was thinking about the language $a^nb^nc^n$, which is obviously not context free, but if we run it through 2 automata at the same time (the first for $a$ and $b$ and the second for $b$ and $c$ and ...
592 views

### Can we skip an input in push down automata

Hi here I'm giving a language L3={0^m 1^(n ) 2^m | m,n ∈ N} I designed this stack machine in order to accept this given language. Here I'm skipping 1 (no matter how many 1s are there) . Is it ok to ...
1 vote
205 views

### Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?

Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if ...
146 views

### Build PDA for a language with unknown input alphabet

$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows: $$L_{12}=\left \{ w_1\cdot w_2\mid w_1\in L_1\land w_2\in L_2\land |w_1|=|w_2| \right \}$$ In this exercise I am not given ...
1 vote
80 views

### Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $G$ for $$L = \{a^i b^{i+j+k} c^j d^k\}$$ so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
134 views

How to construct DPDA for the following language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n$ $L_1 = \{a,b\}^* \setminus a^nb^n =\{a^i b^j \, | \, i>j\}\,\cup\,\{a^i b^j\ \ | \ i<j\}\,\cup\... -1 votes 1 answer 170 views ### Show that the language$L=\{w|w$has odd length and the middle symbol is a$0\}$is Context-Free and construct a PDA that accepts it Were w is any string composed over the alphabet$\Sigma = \{0,1\}$. For the first part of the exercise I've tried decomposing the problem into three different ones, mainly the first one is for the ... 0 votes 0 answers 50 views ### Constructing an equivalent Pushdown Automaton I'm working on an exercise (not relevant for evaluation) that involves constructing an equivalent nondeterministic stack machine from a given machine with epsilon-transitions. However, I'm having ... 0 votes 0 answers 45 views ### can a DPDA have two transition to different states when you pop a different symbol? I have a question about the DPDA. Is it possibly to have two transitions that read the same input but do different in the stack? An example would be A transition from q1 to q2 where I read input ( pop ... 0 votes 1 answer 40 views ### can you read and push different symbols in a DPDA? I have an easy question about the DPDA. Could you read an input and push a different symbol to the stack. An example would be A transition from q1 to q2 where read input is v pop is epsilon(empty ... 0 votes 0 answers 11 views ### Deterministic pushdown automata that checks for a specific variable in nesting levels I want to define a DPDA based on a set of rules: one or more uppercase letters ('A'-'Z') is a formula. one or more lowercase letters ('a'-'z') is a formula. if X and Y are formulas, then this is a ... 1 vote 1 answer 91 views ### Can a pushdown automaton write more than one symbols on to stack on one reading from from input tape? The formal definition of the pushdown automata according to Mike Sisper's book on theory of computation is as follows: . The transition function however only takes in one symbol from the stack (after ... 0 votes 0 answers 44 views ### Equivalent context free grammar for every pushdown automaton? Equivalent context free grammar for pushdown automata  This machine does not accept L = {a^(n)b^(n)c^(n) | n > 0} and instead accepts L = {a^(2n+1)b^(2n+1)c^(2n+1)}; also, as a side note ... 1 vote 1 answer 42 views ### Simple pushdown automata question I'm trying to derive the language it represents. However, I'm kind of new to those topics. What happens if input b is gathered once or more than one time at state q without a in the stack? It does not ... 0 votes 0 answers 84 views ### Constructing a PDA for$L=${$\exists i,k\in \mathbb{N} : |w|=2k, w_i \neq w_{k+i}$} I have the main idea, yet I'm uncertain on how to construct this PDA (in terms of states, transitions) We can assume the alphabet$\Sigma$is {$0,1$}, proving for$\Sigma=${$0,1$} is a sufficient ... 0 votes 1 answer 59 views ### How PDA decide when and which state to transform to?  gives an example for PDA which contains rules of: (p,e,Z,q,Z) (p,e,A,q,A) and says, The third and fourth instructions say that, at any moment the automaton ... 3 votes 2 answers 2k views ### Mike Sipser and Wikipedia seem to disagree on Chomsky's normal form Here's what Wiki says: And here's what Mike Sipser says in his Introduction to Theory of Computation: The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting ... -1 votes 1 answer 71 views ### What is the computational class of a pushdown automaton with real values? Say there is a push-down automaton, in this example I'll use a Deadfish-like set: +: increase x by 1 0: set x to 0 ... -1 votes 1 answer 50 views ### The book says 27 terminals but I only see 10. Where are they? On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the ... 0 votes 1 answer 48 views ### Pushdown Automata Construction I had an assignment in which I had to design a pushdown automata that recognizes the language${w \in [a,b,c]^*|w }$have the same number of "ab" and "ba". Tried to make a pushdown ... 3 votes 3 answers 357 views ### PDA for a language where the second part is not the reverse of the first part I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where$L \subseteq ({a,b,c})^*$So$n$and$m$are both a ... 4 votes 0 answers 61 views ### Is the following language recognizable by a visibly pushdown automaton? Consider the alphabet$\Sigma = \Sigma_c \cup \Sigma_i \cup \Sigma_r$separated into call, internal, and return letters. Assume that$c \in \Sigma_c, r \in \Sigma_c$, and$a \in \Sigma_i$. I have a ... 1 vote 1 answer 262 views ### Designing a PDA without using CFG -> PDA for the language$ \{ a^nb^m | n \le m \le 2n \}L= \{ a^nb^m | n \le m \le 2n \}$As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to ... 1 vote 2 answers 4k views ### PDA of the language where the number of a's are NOT equal to the number of b's I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ... 0 votes 0 answers 111 views ### prove that Every DPDA has an equivalent DPDA that always reads the entire input string I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ... 3 votes 2 answers 81 views ### Implementation details of "transitions" of Non-deterministic push-down automata I am reading "Introduction to the Theory of Computation" 3rd edition ~ by Michael Sipser, page 113-114 - topic: "Context free languages, push down automata" He states that the ... 0 votes 1 answer 90 views ### PushDown automata for a^(n) b^(2n) c^(2n) d^(n) i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)" i am arguing that there is no pda for that question but our ta says that we can push 5x to the ... 0 votes 1 answer 53 views ### What characteristics would a PDA$A$where$L(A)=\Sigma^*$have? I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ... 0 votes 1 answer 162 views ### Can PDA accept only by final state without finish reading input? I am defining, a string$w$is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input$w$(no matter whether the ... 0 votes 1 answer 979 views ### Design a Pushdown automaton for$L = \{a^nb^m | n \le m \le 3n \} L = \{a^nb^m | n \le m \le 3n \} $This is by far the hardest pushdown automaton I had to design. I literally have no idea where to start. Here's my thought process. Firstly, I thought that for each ... 0 votes 1 answer 125 views ### Constructing PDA for$L = \{w\in\{a,b\}^{\ast}\;|\; |w|_a > 2|w|_b\}$Construct a PDA, which recognizes the following language$L$:$L = \{w\;|\; |w|_a > 2|w|_b\}$, so it is the language that consists of words which have more than twice as many$a$'s as$b$'s. I ... 0 votes 1 answer 57 views ### Intersection of CFL and DCFL Is CFL$\cap$DCFL = CFL, always true? CFL - Any Context Free Language DCFL - Any Deterministic Context Free Language 1 vote 1 answer 97 views ### Shuffle of a DCFL and a regular language This is problem 88 from Miscellaneous exercises of Kozen's "Automata and Computability". The shuffle$A||B$of two languages$A$and$B$is defined as$\{w \mid w = a_1b_1\ldots a_kb_k,$... 0 votes 1 answer 49 views ### Push Down Automata I am learning about context free languages. I understand how$\{a^nb^nc^n|n>0\}$can be shown to be not context free using the pumping lemma for CFL's. Intuitively however it seems that a pushdown ... 0 votes 1 answer 36 views ### Context Free Language Twist [duplicate] I am trying to recognize a particular language, L= {a^n b^k | n<=k<=2n} and according to me it should not be CFL, as i can see two comparision i.e. firstly number of a is compare to keep count ... 0 votes 1 answer 711 views ### CFG and PDA for the set of strings in$\{a, b, c\}^∗$such that the number of b’s is equal to the sum of number of a’s and c’s I'm trying to find the CFG and PDA for the above language. I have so far come up with this$S \to S_1S_2 \\ S_1 \to aS_1b \\ S_2 \to bS_2c$However, I realized that this is just a subset of the ... 2 votes 0 answers 101 views ### Minimizing DPDA Is there an efficient algorithm for minimizing a deterministic PDA in terms of states? Is it even computable? I know that it is not possible to minimize a PDA in general, but my question is about ... 0 votes 1 answer 3k views ### Push down automata acceptance by Empty stack and final state I have a very basic question. Can we have a PDA which can accept a string by both final states and empty stack? Can the same PDA accept by the two modes simultaneously ? If there are final states ... 2 votes 2 answers 239 views ### Intuition for Sipser's proof of PDA to CFG I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two. He splits the proof (... 0 votes 0 answers 360 views ### Non-deterministic Pushdown Automaton to Context-Free Grammar While doing the exercise about questions about transforming NPDA to CFG, I encountered the following question: Find a CFG for the following NPDA$M = (\{q_0, q_1\}, \{a, b\}, \{A, z\}, \delta, q_0, z, ...
I got a question: Design a pushdown automata that can recognize strings in L= {$a^n b^{2n} c^{3n} | n ≥ 0$} . I tried to think and design it, but I couldn't find it. The best that I can think of is ...