The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [pushdown-automata]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
88 views

Is $L / R$ context free?

I was reviewing the post If $L$ is context-free and $R$ is regular, then $L / R$ is context-free? I completely understand why $L/R$ is context free. I just tried a different approach, which is not ...
2
votes
1answer
153 views

PDA with an unusual double inequality

I have an odd PDA problem that I cant seem to construct. I haven't come across one like this before. $L = \{w\in\{a,b\}^{*} : 3\#_{a}(w) \leq 5\#_{b}(w) \leq 4\#_{a}(w)\}$ Could I get some pointers ...
-2
votes
2answers
1k views

If accepted by dpda and npda,then it is regular. Is it correct?

If accepted by dpda and npda,then it is regular. Is it correct?.I had confusion that some where I studied that a regular language is exactly should accepted by finite automata.....
4
votes
1answer
279 views

Proof that PDA's with different definitions have same expressive power

Let $P$ be a push down automaton $(Q,\Sigma,\Gamma,\delta,q_s,F)$, where $Q$ is the set of states, $\Sigma$ is the input alphabet $\Gamma$ is the stack alphabet $\delta$ is the transition function ...
4
votes
1answer
352 views

Parsing CFLs (simulating PDA vs CYK algorithm)

We can simulate the PDA and parse the language with the following operations (vaguely): Read the input symbol and top of stack - $O(1)$ Check all the transition rules (must check all for non-...
0
votes
0answers
392 views

Converting a CFG with epsilons into a DPDA

I have a CFG: S -> $T$ T -> T+T|T-T|T/T|(T)|CX|I X -> XX |C|N|_|@ C -> a|b|c|....|z|A|B|C|...|Z|_ N -> 0|1|2|....|9 I -> NI|N Here @ means epsilon. The above is a valid arithmetic expression ...
2
votes
1answer
2k views

Why can you push multiple symbols on a PDA stack at once?

I'm really new to learning about PDA's and stuff, i understand that on a edge between 2 nodes you'll have something like this a,b->c. This means: if a is in the beginning of your string and b is on ...
5
votes
1answer
753 views

Why can PDAs only write one symbol to the stack according to this definition?

This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser. The transition is defined as $$ \delta: Q\times \Sigma_\varepsilon \times ...
0
votes
1answer
167 views

I can't understand this example of PDA Automata

looking for old tests of Language Theory, I see this exercise: Give a PDA automata that recognize the language $L = \{w \in \{a,b\}^*,\ 2|w|_a=3|w|_b\}$ They propose this solution: Can anyone help ...
0
votes
0answers
16 views

What is the pushdown automata for the language {0, 1}* Where |0| = 2 * |1| or |1| = 2 * |0|? [duplicate]

Having a lot of trouble figuring this out. It seems to me to be impossible. I could do one side of the OR - but the fact that the string can begin with 100 1's and then have 200 b's seems like it can'...
4
votes
1answer
2k views

Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
2
votes
1answer
334 views

Is a PDA's stack size linear bounded in input size?

I was thinking as follows: At each step, a PDA can put arbitrary many symbols onto the stack. But this number is constant for every individual PDA, so it can't be more than, say, $k$ symbols per step. ...
2
votes
1answer
66 views

Prove that language of possible stack content is regular

So, here's the problem: Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let $$L = \{ \gamma \in \Gamma^* \hspace{5pt}|\hspace{5pt} \exists_{x,y\in \Sigma^*} \exists_{q\in Q}: (s,x,\bot)...
0
votes
2answers
1k views

Proof for TM accepting any PDA-language

How do you suggest I go about proving this: Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine....
0
votes
1answer
335 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = \{\text{...
0
votes
1answer
904 views

Determine whether a context-free language is deterministic or not

I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown ...
3
votes
2answers
327 views

How to understand pushdown automata intuitively?

What is an intuitive way of understanding what a push down automaton is capable of computing?
1
vote
1answer
3k views

PDA for all non-palindromic strings of even length

I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$. I already turned it in, but I know I had it ...
5
votes
1answer
677 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
1
vote
0answers
59 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
1
vote
0answers
62 views

turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
1
vote
1answer
1k views

Why do we pop the dollar symbol when it's already present in the stack in PDA?

Could anyone tell the reason for popping the top of stack(dollar symbol) as said in this lecture(p.54) when there's already dollar symbol in the stack. I would like to know if we could replace the ...
0
votes
1answer
87 views

Characterizing a CFG equivalent to a special type of PDA

Consider a nondeterministic PDA $P$ which pushes/pops at most one stack symbol on a transition. Suppose that for every string $\sigma \in L(P)$, there is an accept computation of $\sigma$ in $P$ which ...
0
votes
1answer
82 views

Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A. I'm trying to think in terms of what to save on the ...
-1
votes
1answer
624 views

Converting a language to a PDA?

I am trying to convert the follow language $$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$ We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though ...
0
votes
1answer
87 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
0
votes
0answers
215 views

What is the difference between Moore's algorithm and partition refinement algorithm for DFA minimization?

Both the algorithms use the partition method to minimize the DFA. I cannot understand the difference between them. Can someone give an example where we can see the difference between them.
5
votes
1answer
11k views

Deterministic vs. Non-Deterministic PDA?

The following is an example of language $a^nb^n$ where $n \geq 1$ From what I have heard that in finite state machines if you see epsilon moves, then it is NFA otherwise it is DFA. But in this case, ...
1
vote
1answer
111 views

Calculi for a computability class

Proving two push down automata equivalent is undecidable. But proving two finite state machines equivalent is decidable. You also cannot write a programming language that allows expressing the ...
2
votes
2answers
647 views

Techniques to create a PDA for a language that is the conjunction of two languages

When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are ...
0
votes
1answer
209 views

DPDA for $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ according to empty stack criterion

I'm having some trouble with the following language: $L_1 = \{0^i1^j2^k3^m | i,j,k\ge 0,m = i+j+k\}$ with alphabet $A=\{0,1,2,3\}$ I'd like to find a deterministic pushdown automata to recognise it ...
2
votes
0answers
29 views

Why we don't care about minimizing Push Down Automata & Turing Machines? [duplicate]

I never heard or read about the concepts of "Minimizing Push Down Automata or Turing Machines"? why we are not concerned about minimizing them, in general?
2
votes
1answer
369 views

Why is this NPDA?

I am studying PDA at the moment, and I came up with this question. The figure above tells me that although both PDA accept the same language, one is non-deterministic and the other is deterministic. ...
-1
votes
1answer
110 views

Is a Pushdown Automata possible for this language?

PDA for a Language L = { $a^i b^j \mid i \neq 2j+1 \}$ over the Alphabet $\Sigma = \{a,b\}$ If it can be constructed, how? Edit : I've tried make the PDA for $$L = \{ a^i b^j \mid i = 2j+1 \}$$ (...
-1
votes
1answer
632 views

How to find what language a PDA accepts?

Given the following PDA describe the language it accepts. ...
3
votes
0answers
2k views

What are some applications of 2 stack pushdown automata?

What are some real world application for 2 stack pushdown automata, as i can only find pushdown automata applications in the internet
0
votes
2answers
291 views

Can a deterministic language be accepted by a deterministic Push Down Automaton?

I have a question that asks me to show that the PDA of the language L is not deterministic, but that the language is nevertheless deterministic. I was under the assumption that any deterministic ...
3
votes
2answers
4k views

Find a pushdown automaton for { x#y ∣ x ≠ y }

I was told to built a PDA that recognizes the following language: $$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$ My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
1
vote
1answer
5k views

Pushdown automaton for complement of { ww | … }

I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams). So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not ...
2
votes
0answers
64 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (...
1
vote
0answers
41 views

Language involving length constraints and reversal

Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language? It is turning out to be really tricky. Is there an easy way to show this?
-4
votes
1answer
452 views

How to design a PDA for the language of words with s a's, t b's and s⋅t c's? [closed]

I have the language $\qquad L=\{ a^s b^t c^m \mid s,t,m \; \in \; \mathbb{N^{+}} \text{ and } t<4, s \cdot t=m\}$. How do I go about designing a PDA for it ? I can't figure out a way to deal ...
2
votes
2answers
2k views

Formal construction of PDA intersecting a DFA

Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$ and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$ What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$ I don't ...
3
votes
1answer
141 views

When does a PDA split?

In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. ...
9
votes
1answer
1k views

Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
4
votes
1answer
541 views

How powerful is a k-stack pushdown automaton with a unary stack alphabet?

I'm interested in pushdown automata with a unary stack alphabet: let's call them UPDA's. Define a $k$-UPDA to be a pushdown automaton with $k$ stacks, each with a unary stack alphabet. I've figured ...
1
vote
1answer
1k views

Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$

I've been studying Computation Theory, and in an exercise I am asked to construct a PDA that accepts the language $L=\{x\in(a,b), \#_a(x) = 2\#_b(x)\}$, where $x$ is the input string and $\#_a(x),\#_b(...
0
votes
0answers
74 views

Linear time parsing from star of context free language

I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar: ...
14
votes
4answers
588 views

Push Down Automatons “guess” - what does that mean?

I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted ...
2
votes
1answer
3k views

Converting final state PDA to empty stack PDA

I'm having a problem understanding this conversion. Let's say we have a CFL like this: $ { a^nb^m : n > m } $ A final state acceptance PDA for this language would push $A$ symbols in the stack for ...