Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [pushdown-automata]

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

552 questions
Filter by
Sorted by
Tagged with
45 views

### Is the language L = {a^m b^n a^n b^m | m, n >= 1} context free?

Based on my understanding, I ended up at the following grammar: A -> bAa | λ S -> aSb | A | λ Is it sufficient to say the above language L = {a^m b^n a^n b^m ...
80 views

### problem understanding proof about deterministic pushdown automaton

I'm having problem understanding the first part of this proof. I don't understand why it needs to hang at $(p,\epsilon,\epsilon)$ why can't the automaton just keep going, just reading the rest of the ...
22 views

### Can I maintain Determinism of PDA just by changing stack symbol while keeping state and input symbol same?

for a transition $\delta(q,\sigma,X)$, if I keep state $q$ and input symbol $\sigma$ same but read different stack symbols in place of $X$ will it still be called deterministic PDA because as per my ...
• 71
33 views

• 143
1 vote
52 views

### infinite loop in PDA

let L be defined as $L = \{0^{2k} | k \in \mathbb{N}\} \subset \{0,1\}^*$. language L can be described by a nondeterministic pushdown automaton P such that there exists at least one input for which P ...
40 views

622 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 ...
51 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 ...
• 125
45 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 ...
1 vote
185 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 ...
• 51
58 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
50 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 ...
• 67
88 views

### How PDA decide when and which state to transform to?

[1] 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 ...
• 103
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 ...
• 51
52 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 ...
• 51
1 vote
91 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 ...
61 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 ...
63 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 ...
150 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 ...
457 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$.
100 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 ...
201 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 ...
69 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 ...
90 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
140 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,$ ...
• 13
99 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 ...
1 vote
1k 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 ...
• 11
39 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 ...
136 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 ...
347 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 (...
• 43
604 views

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, ... • 101 1 vote 1 answer 86 views ### Prove that the "6-rule" CFG for arithmetic expressions below is unambiguous Question: Prove that the 6-rule CFG for arithmetic expressions below is unambiguous. The CFG is as follows.$G = (V:=\{E,T,F\}, \Sigma:=\{+, \times,(,),x\},R,E\})$where$R$consists of 6 rules:$E\...
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 ...