Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
97
questions with no upvoted or accepted answers
8
votes
1
answer
330
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}$...
- 1,269
6
votes
0
answers
315
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 ...
- 161
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 ...
4
votes
0
answers
336
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 ...
- 1,682
3
votes
0
answers
71
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$...
- 29.8k
3
votes
0
answers
33
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 ...
- 385
3
votes
0
answers
374
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 ...
- 141
3
votes
0
answers
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
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 ...
- 208
2
votes
0
answers
224
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 :
...
- 93
2
votes
0
answers
45
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
0
answers
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 ...
- 97
2
votes
0
answers
282
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 ...
- 121
2
votes
0
answers
129
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
0
answers
514
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. ...
- 21
2
votes
0
answers
826
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-...
- 1,637
2
votes
0
answers
74
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
0
answers
81
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 \}$...
- 12.4k
1
vote
2
answers
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 ...
- 11
1
vote
1
answer
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 ...
- 11
1
vote
0
answers
117
views
Why do PDAs always halt?
Can’t a PDA get stuck in a cycle of blank transitions?
Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases.
Does the ...
- 191
1
vote
0
answers
44
views
Unambiguous formal grammars for a specific class of languages
Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$.
Now suppose that $q \in \mathbb{Q}$ is a positive ...
- 131
1
vote
0
answers
66
views
Different PDA design processes -- both valid?
This video shows how to design PDA from a CFG:
https://www.youtube.com/watch?v=ZImtQBMSW_Y
Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
- 67
1
vote
0
answers
129
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 ...
- 111
1
vote
0
answers
190
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 ...
- 11
1
vote
0
answers
147
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
0
answers
427
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 $...
- 11
1
vote
0
answers
184
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
0
answers
78
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.
...
- 111
1
vote
0
answers
101
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
0
answers
22
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,378
1
vote
0
answers
218
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:
...
- 177
1
vote
0
answers
51
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,637
1
vote
0
answers
217
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,637
1
vote
0
answers
849
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 ...
- 327
1
vote
0
answers
559
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 ...
- 111
1
vote
0
answers
548
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$ :
( ...
- 205
1
vote
0
answers
176
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 ...
- 102
1
vote
0
answers
34
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
0
answers
78
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 ...
- 93
1
vote
0
answers
79
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 ...
- 11
1
vote
0
answers
44
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?
user39969
0
votes
0
answers
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?
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 ...
- 125
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 ...
- 3
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
0
votes
0
answers
44
views
Equivalent context free grammar for every pushdown automaton?
Equivalent context free grammar for pushdown automata
[edit] 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 ...
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 ...
- 315
0
votes
1
answer
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$.
Swathi A
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 ...
- 1