Questions tagged [pushdown-automata]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
1k views

Syntax of a Pushdown Automata transition function

I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax: $\delta(q, \lambda, S) = ...
9
votes
1answer
22k views

Convert CFG to PDA

Is there any set of rules or methods to convert any context free grammar to a push down automata? I already found some slides online but I wasn't able to understand them. In slide 10 he speaks ...
1
vote
1answer
2k views

How to generate a pushdown automata for accepting a language?

I have an exercise in my book to come up with a pushdown automaton accepting a language. The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings ...
4
votes
2answers
6k views

Give CFG and PDA for the words that start and end with the same symbol

I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite ...
2
votes
1answer
2k views

Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?

$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ Is this language a context free language? If yes give a PDA. If no, give a proof. The pumping lemma for context free languages doesn't seem to work ...
2
votes
2answers
9k views

Constructing PDA for $a^{2n} b^{3n}$

So I have been given the task of creating an PDA that recognises the language $\{a^{2n} b^{3n} \mid n = 0,1,2,\dots\}$. Am I right in thinking that it needs to have at least 3 times number of $b$'s ...
3
votes
1answer
253 views

Proving that a specific language is a CFL, and that another language is not a CFL

I have two languages $C_1$ and $C_2. \left(\Sigma=\{0,1\}\right)$: $C_1=\left\{xyz\mid x,z \in \Sigma^*, y \in \Sigma^*1\Sigma^*, \text{ where } |x|=|z| \geq |y|\right\}$, and $C_2=\left\{xyz\mid x,z ...
4
votes
6answers
15k views

Are Turing machines more powerful than pushdown automata?

I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave ...
-1
votes
1answer
1k views

Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
5
votes
1answer
697 views

Deterministic context-free languages are closed under regular right-product

I am looking for a proof for the following problem: For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language. Note:...
3
votes
1answer
2k views

How can one simulate a PDA with a FIFO queue PDA?

I'm trying to figure out how a pushdown automata (PDA), which we know uses a stack (LIFO) can be simulated by a queue (FIFO). I understand that in a regular PDA, we only have access to the top most ...
3
votes
2answers
3k views

CFG and PDA for the grammar that has perfectly nested parentheses and brackets

I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets. $\qquad\begin{align} S &\to [S] \\ S &\to (S) \\ S &\to SS \\ S &\to \varepsilon \...
3
votes
3answers
1k views

Constructing deterministic PDA for not regular language

Let the input alphabet be $\Sigma = \{a,b,c\}$ and L be the language of all words in which all of the a’s come before all of the b’s and there are the same number of a’s as b's and arbitrarily many c’...
1
vote
2answers
2k views

When generating a PDA from a CFG do I have a receiving state?

Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.
2
votes
1answer
953 views

Eliminating useless productions resulting from PDA to CFG converison

In my class we used a Pushdown Automata to Context Free Grammar conversion algorithm that produces a lot extraneous states. For example, for two transitions, I am getting the following productions ...
7
votes
1answer
727 views

Converting a context free grammar to a PDA — is my solution correct?

I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG: $\qquad\begin{align} S &\to R1R1R1 \\ R &\to ...
3
votes
1answer
4k views

Context-free grammar to a pushdown automaton

I'm trying to convert a context free grammar to a pushdown automaton (PDA); I'm not sure how I'm gonna get an answer or show you my progress as it's a diagram... Anyway this is the last problem I have ...
22
votes
1answer
2k views

Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa) There may also exist a Deterministic Pushdown ...
12
votes
2answers
2k views

Does the language of Regular Expressions need a push down automata to parse it?

I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
9
votes
3answers
2k views

If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I'm am stuck solving the next exercise: Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
4
votes
1answer
3k views

How does a two-way pushdown automaton work?

Note that by "two-way pushdown automaton", I mean a pushdown automaton that can move its reading head both ways on the input tape. I recently had the question of determining the computational power ...