# Questions tagged [pushdown-automata]

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

385 questions
Filter by
Sorted by
Tagged with
341 views

### a^nb^nc^nd^n using 2-stack PDA

I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n |$ $n \geq 0\}$. Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...
119 views

### Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity

I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\#y$ where $x$ and $y$ are strings of 1s and 0s such that there ...
39 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 ...
25 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 ...
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 ...
65 views

155 views

### PDA for the language of strings containing the same number of a and b

Need idea for solving the following pushdown automata: $\mathcal{L}=\{w\in\sum ^* | \#a(w)=\#b(w),|w|\geqslant 0\} \,\,\,\, \sum=\{a,b\}$ In the beginning I thought to PUSH A for input a, and then ...
688 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}$} ...
49 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 ...
48 views

### Grammar of words with exactly $k$ prefixes in another grammar

Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that $$L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\}$$ where $\text{Pref}(w)$ is the set ...
138 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\}$?
185 views

### Does left factoring CFG make it unambiguous?

I came across following problem: If the CFG is left factored then it must be Unambiguous and Not left Recursive. TRUE/FALSE? I have many thoughts about this. But I feel they are somewhat ...
312 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 ...
50 views