Questions tagged [pushdown-automata]

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

79 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
1answer
305 views

Is there a strictly non-deterministic one-counter language whose complement is one-counter?

Let $A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$ Clearly, $\text{Deterministic one-counter} \subseteq A$ Is it the case that $ A = \text{Deterministic one-counter}$...
6
votes
0answers
255 views

Why does Non Determinism not enhance FA like it does for PDA

Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of ...
4
votes
0answers
112 views

Detecting loops in NPDAs

I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
3
votes
0answers
58 views

bounding the height of stack when checking acceptance pushdown automaton

Let $A$ be a nondeterministic PDA (with empty stack acceptance). I am looking for a reference for a statement of the following form. There exists a constant $c$, computable from $A$, such that: if $w$...
3
votes
0answers
25 views

Automaton without stack for visibly pushdown languages

This paper here describes an alternating automaton which can recognize visibly pushdown langauges without using a stack. Unfortunately the transformation from NVPA to such an automaton is skipped in ...
3
votes
0answers
264 views

How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
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
2
votes
0answers
97 views

Is the following PDA a DPDA or NPDA?

Let the language be : $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w)\}. $$ Now the PDA that I've designed for this language and seen at many other places is : ...
2
votes
0answers
40 views

kPDA handling multiple epsilon transtions

I'm assigned to build a kPDA with 2 stacks that handles {w#w, where w is a string of (0,1)*}. I understand the # delineates the two strings, but I'm unsure of the logic when popping off stacks with ...
2
votes
0answers
2k views

Turing machine VS Push Down Automaton in CFL

I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why? I know that a pushdown automaton can ...
2
votes
0answers
103 views

What is the simplest automaton that can compute the sum of two integers of arbitrary length?

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length? I ...
2
votes
0answers
95 views

Which transducer models replacement in regex?

I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order. For example: ABC => CAB, which, with ...
2
votes
0answers
226 views

Simulating a turing machine with DPDA with two stacks

In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input. ...
2
votes
0answers
586 views

Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

I read following here: Unambiguous grammars do not always generate a DCFL. Example: For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-...
2
votes
0answers
65 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 (...
2
votes
0answers
72 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R \}$...
1
vote
3answers
25 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 ...
1
vote
0answers
83 views

Question about proof of Lemma 2.41 - Sipser book

Doesn't the modification described in paragraph three potentially introduce non-determinism? For example, say neither a, b, x, nor y is the empty string (denoted e). If in the original machine P we ...
1
vote
0answers
45 views

A pda that accepts all strings over an alphabet

If you were asked to construct a pda that recognizes all strings over the alphabet {a,b,c,d}, that is L={w | w belongs to (a,b,c,d)*} How would that be constructed? My idea is to have one state as ...
1
vote
0answers
74 views

How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of ...
1
vote
0answers
123 views

Determine the language of the given NPDA

Thoughts I am wondering is the language $ab^*$, since $a$ pushes $X$ to the stack and $b$ pops, and if there is an $a$ there has to be a $b$ to get back to the final state? Also, is it right to say $...
1
vote
0answers
137 views

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) ...
1
vote
0answers
43 views

What is the class of automata with stack and unlimited amount of memory, addressable only by immediates?

Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code. ...
1
vote
0answers
59 views

How to visualize non-deterministic pushdown automata?

My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
1
vote
1answer
166 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. ...
1
vote
0answers
14 views

Is there anything like equivalence classes in PDA (and more expressive ones, perhaps)?

The motivation for this question is the fact that partitioning DFA into equivalence classes is the mechanism that is used in model testing to generate test cases. However, obviously, DFA cannot ...
1
vote
0answers
74 views

Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs

I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language: ...
1
vote
0answers
48 views

Finding language family of given language

I came across following problem: Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any language, then what is the smallest language family $L'$ belongs ...
1
vote
0answers
152 views

Is universality problem of single state NPDA decidable?

I came across following problem: Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable? Now I know for DPDA/DCFG/DCFL, universality problem is ...
1
vote
0answers
620 views

Constructing a turing machine from a PDA - dealing with non-determinism

Given a PDA $P$, I believe we can simulate it with a turing machine with 2 tapes - one for keep reading the input and one for the stack. But, a PDA transition function may have multiple transitions ...
1
vote
0answers
414 views

Why Acceptance by Final sate and Empty Stack in PDA?

Why there are two ways of accepting the input in PDA i.e. Acceptance by Final sate and Empty Stack I have seen examples which are accepted by both rules? There are some examples which are only ...
1
vote
0answers
390 views

How to draw NPDA for language $L = \{ a^i b^j c^m \mid m \ge \min( i,j) \} $

$L_1 = \{ a^i b^j c^m \mid m ≥ min(i,j) \}$ $L_2 = \{ a^i b^j c^m \mid m ≥ max(i,j) \}$ Which language is CFL ? ANS : $L_1$ is CFL but $L_2$ is NOT. My understanding :  For Language $L_1$ : ( ...
1
vote
0answers
131 views

Complexity of emptiness checking for visibly pushdown automata?

Visibly pushdown automata [1] are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness ...
1
vote
0answers
27 views

almost realtime push down relation vs realtime pushdown relation?

Almost realtime pushdown relation pop a symbol for each empty step. Realtime pushdown relation does not perform any empty step. What do they mean by empty step?
1
vote
0answers
65 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
71 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
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?
0
votes
0answers
29 views

What is the most commonly used/ most practical method to parse context sensitive languages?

what is the most commonly used / most practical method to parse CSLs ? By "most practical" I mean Not too theoretical but in opposite to that, with practical usecases Not too complicated (...
0
votes
1answer
49 views

Two way deterministic pushdown automaton accepting word consisting of two equal words

I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language: {ww | w ∈ {a, b}*} Does anyone have any idea? Thanks a lot
0
votes
1answer
25 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
1answer
39 views

What is the computational class of a pushdown automaton with real values?

Say there is a push-down automata, in this example I'll use a deadfish-like set: +: increase x by 1 0: set x to 0 ...
0
votes
0answers
20 views

Is there only one unique DPDA that accepts a specific language?

Or is it possible to construct more than one DPDA that accepts exactly the same language?
0
votes
0answers
20 views

Constructing a Push Down Automaton

Given a 7 tuple push down automaton M = (K, Σ, Γ, Δ, s, F) where K = {p, q, r}, Σ = {a, b, c}, Γ = {a}, s = p, and F = {r}, with the transitions ((p, b, ε), (q, ε)), ((q, a, e,), (p, a)), ((p, c, a), (...
0
votes
0answers
50 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
0answers
59 views

Is it necessary for a Push down Automaton (PDA) to have a stack?

I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
0
votes
2answers
55 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|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$ In this exersice I am not given any ...
0
votes
0answers
50 views

Convert PDA by final state in to cfg

Hope you all are doing well. I want your assistance. I have a PDA which is accepted by the final state. I need to convert it into cfg. So I want to ask, If I want to first convert this into ...
0
votes
0answers
33 views

Context free grammar to Chomsky normal form

I have a hard time understanding how to convert the following context free grammar to Chomsky Normal Form: S $\rightarrow$ aSX | B B $\rightarrow$ bBX | ε X $\rightarrow$ a | b I have a solution S $\...
0
votes
0answers
32 views

Can a pushdown automaton solve the halting problem for another Pushdown automaton?

Can a pushdown automaton solve the halting problem for another Pushdown automaton? It's already shown here turing machine can solve the halting problem for a pushdown automaton. Decidability of ...
0
votes
1answer
193 views

How to convert NPDA to PDA?

I have been given this Nondeterministic pushdown automata and I need to convert it to deterministic pushdown automata, I have been stuck with this for a while now, I know that there cant be ...