# Questions tagged [pushdown-automata]

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

539 questions
Filter by
Sorted by
Tagged with
441 views

### Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem: Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C ...
126 views

### Turing machine without return equivalent to Finite Automaton, PushDown Automaton or Turing Machine?

I have seen that a Turing machine without return is a Turing machine $M$ which at each stage of its calculation systematically moves its read / write head to the right.The aim of the exercise is to ...
• 21
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
213 views

### Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Consider the language $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements. $\quad\quad\text{I. }L$ is deterministic context-free. $\quad\quad\text{II. }L$ is context-...
• 1,112
1 vote
92 views

### PDA accepting all words not of the form $b^na^n$

I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages. If I have context-free ...
• 67
1 vote
34 views

### Unix glob() function and formal language equivalence

Can we express the matching capabilities of Unix library function glob() using a single-stack push-down automata, i.e. set of context free formal languages? If not, ...
1 vote
53 views

### Can a Turing machine or Push Down Automaton construct languages of type 3?

I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a ...
1 vote
236 views

### Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$

I understand that the language $L = \{ a^mb^nc^k \mid m=n \text{ or } n=k \}$ is context-free because it can be represented as the union of $L_1 = \{a^mb^mc^k\}$ and $L_2 = \{a^mb^kc^k\}$, which are ...
1 vote
59 views

### Reduce PDA for a given language

I drew a Push-down Automata, accepting the following language: $$\{ xcy : x,y \in (a+b)^*, \#_a(x) > \#_{bb}(y) \}.$$ Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with ...
• 13
1 vote
216 views

### PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1

Consider the language $\{ uv : \text{$|u| \ge |v|$and$v$contains a 1}\}$. I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if ...
62 views

### Where to put the state in a two-stack push down automaton?

theoretically, the state is between the two kleene-stars of the work-alphabet gamma* q gamma* where q is the current state and each ...
• 201
927 views

### Can PDA have empty stack transition?

From a youtube video, this PDA can recognize any palindrom. However, from wikipedia, here is one of the criteria of PDAs. We clearly see that the transition function can't take an empty stack as ...
• 165
1 vote
72 views

76 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?
447 views

### How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?

I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA. I'm thinking to have n+1 states in a NFA, with the start state as the ...
• 21
391 views

### Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$

Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$ I have tried to find a pushdown automata and it turned out to be a ...
357 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 ...
232 views

### How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}. So m can be infinitely bigger than n but n can ...
70 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 ...
• 213
1k views

• 217
458 views

### How can I combine 2 PDA's into 1

I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$} I know the idea of building each one separately but how do I combine them into 1 PDA? LHS: for every 'a' I push 'A' inside stack and for ...
• 217
470 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?
• 101
146 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\mid w_1\in L_1\land w_2\in L_2\land |w_1|=|w_2| \right \}$$ In this exercise I am not given ...
• 217
281 views

### Formal definition of non deterministic PDA

How would you convert the following formal definition of deterministic pushdown automata into non deterministic ? Deterministic PDAs In general terms, a deterministic PDA is one in which there is at ...
353 views

### Turing Machine construction of M=wwRw form

Construct a Turing machine for M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}. I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
47 views

### checking configuration history of Turing machine using PDA

I am trying to understand the technique of using configuration history in proofs. To prove that: $\{<M>|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$ given $<M,w>$ we ...
• 109
1 vote
187 views

### Is this push-down automaton non-deterministic, as JFLAP states?

There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism. In this example it is detecting non-determinism in state ...
• 163