# 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
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
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
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 ...
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
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
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
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
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
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 ...
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
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 ...
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
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
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 ...
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
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
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 (...
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
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 ...
1 vote
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
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
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
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
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 ...
1 vote
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 ...
1 vote
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