Skip to main content

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
Filter by
Sorted by
Tagged with
8 votes
1 answer
334 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}$...
e_noether's user avatar
  • 1,319
7 votes
0 answers
332 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 ...
AnkithD's user avatar
  • 171
4 votes
0 answers
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 ...
VisiblyPushdownPerson's user avatar
4 votes
0 answers
404 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 ...
Ben I.'s user avatar
  • 1,710
4 votes
0 answers
410 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 ...
jchitel's user avatar
  • 151
3 votes
0 answers
40 views

Length of an $\varepsilon$-computation in complete DPDA

I consider a deterministic pushdown automaton. Given that there are some differences between definitions, here is mine: the syntax is given $A = (Q, \Sigma, \Gamma, \Delta, q_0, Z_0, F)$, with $q_0\...
Nathaniel's user avatar
  • 15.8k
3 votes
0 answers
73 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$...
Hendrik Jan's user avatar
  • 30.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 ...
Cilenco's user avatar
  • 415
3 votes
0 answers
3k 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
Angeline J. Tan's user avatar
2 votes
0 answers
137 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 ...
Peter Lenkefi's user avatar
2 votes
0 answers
241 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 : ...
Argon's user avatar
  • 103
2 votes
0 answers
46 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 ...
bangbangpowpow's user avatar
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 ...
Tom 's user avatar
  • 97
2 votes
0 answers
345 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 ...
Mys_721tx's user avatar
  • 121
2 votes
0 answers
131 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 ...
Arif Canakoglu's user avatar
2 votes
0 answers
554 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. ...
BotNzd's user avatar
  • 21
2 votes
0 answers
232 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 ...
RajS's user avatar
  • 1,677
2 votes
0 answers
919 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-...
RajS's user avatar
  • 1,677
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 (...
Maksim Yegorov's user avatar
2 votes
0 answers
83 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 \}$...
Vor's user avatar
  • 12.6k
1 vote
0 answers
35 views

Efficiently generating valid strings from a deterministic CFG, one symbol at a time, subject to a length limit

Background I'm writing algorithms for generating arbitrary strings from a formal language $L \subseteq \Sigma^*$, one symbol at a time from left to right, while also ensuring that the strings do not ...
Jerry Ding's user avatar
1 vote
0 answers
53 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 ...
Jacob Martina's user avatar
1 vote
1 answer
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 ...
stylusss's user avatar
1 vote
0 answers
170 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 ...
HappyFace's user avatar
  • 211
1 vote
0 answers
47 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 ...
Chain Markov's user avatar
1 vote
0 answers
74 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 ...
am2021's user avatar
  • 67
1 vote
0 answers
137 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 ...
Nathan Schmidt's user avatar
1 vote
0 answers
210 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 ...
user119006's user avatar
1 vote
0 answers
152 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 ...
Mohamad Hussein Naim's user avatar
1 vote
0 answers
472 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 $...
william's user avatar
  • 11
1 vote
0 answers
202 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) ...
DoubleRainbowZ's user avatar
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. ...
Kamila Szewczyk's user avatar
1 vote
0 answers
111 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 ...
Wellington Cesar's user avatar
1 vote
0 answers
23 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 ...
wvxvw's user avatar
  • 1,388
1 vote
0 answers
274 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: ...
foobarbaz's user avatar
  • 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 ...
RajS's user avatar
  • 1,677
1 vote
0 answers
860 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 ...
galah92's user avatar
  • 327
1 vote
0 answers
579 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 ...
Moody's user avatar
  • 111
1 vote
0 answers
563 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$ : ( ...
Aditya's user avatar
  • 205
1 vote
0 answers
178 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 ...
Devendra Bhave's user avatar
1 vote
0 answers
35 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?
Jeyachandran Rathnam's user avatar
1 vote
0 answers
84 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 ...
0xffffffff's user avatar
1 vote
0 answers
80 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 ...
theorcp's user avatar
  • 11
1 vote
0 answers
45 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?
user avatar
0 votes
0 answers
35 views

Write a PDA that accepts the language of strings over {a, b, c} where the number of instances of ab is equal to the number of instances of bc

As the question is stated above, these are the list of transition functions I currently have: $alphabet: {a, b, c}$ $start: q0$ $accepting: {q3}$ // Initialization $q0 ($ _, _ $\rightarrow$ \$, $q1)$ /...
Luke Jones's user avatar
0 votes
0 answers
45 views

PDA equivalent to an $\varepsilon$-free PDA

Say that a PDA is $\varepsilon$-free if it contains no $\varepsilon$ transitions (that is to say, $\varepsilon$ is not in the recognized string symbols even if it still is a stack symbol), but it may ...
Addem's user avatar
  • 367
0 votes
0 answers
74 views

Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
John Daniels's user avatar
0 votes
0 answers
56 views

1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts $L=\{a^{(n^2)} \mid n \geq 1\}$

Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of an input string is strictly a perfect square number. How can I do this in both approaches?
user164486's user avatar
0 votes
0 answers
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 ...
Rico1990's user avatar
  • 125
0 votes
0 answers
61 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 ...
Hiefenhoomer's user avatar