# Questions tagged [pushdown-automata]

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

371 questions
Filter by
Sorted by
Tagged with
22 views

### Behavior of specific PDA for a certain input

Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push ...
28k views

### Is a push-down automaton with two stacks equivalent to a turing machine?

In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is ...
50 views

499 views

### Constructing a PDA with an unequal number of a/b

I'm looking at this pdf for problems: http://www.public.asu.edu/~ccolbou/src/355hw5solf10.pdf I found question 3g to construct a pushdown automata for the following: {${a^i b^j}$ | ${i \neq j}$} ...
46 views

### How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language? I think this could be a good exercise and the conditions are ...
118 views

### Constructing PDA to accept language $\{a^ib^j \mid 0 \leq j \leq 2i\}$

How can I construct a PDA which accepts the language $\{a^ib^j \mid 0 \leq j \leq 2i\}$?
226 views

### CFG problem solved with PDA - looking for alternative solution

I'm trying to find CFG for the language $$L = \{ a^nb^mc^kd^l | n + k = m + l, (n,m,k,l) \in \mathbb{N} \}$$ and what I have done so far is to make PDA which simply does the following: If on the ...
259 views

### Who first introduced the pushdown automaton?

I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble ...
49 views

84 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 ...
313 views

### Undecidable problem intersection of two DCFL languages is DCFL?

We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
12 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 ...
68 views

137 views

### Does a pushdown automata exists for the following language?

I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...