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
2answers
107 views

Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties [duplicate]

Given a language $L$ over $\Sigma=\{a,b\}$ let us define $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ Prove: if $L$ is regular, then $L'$ is a context free language. I know how to ...
1
vote
2answers
46 views

CFG where u has same number of 1s as v [closed]

$$L=\{uv\in\{0,1,2\}^*\mid u\in\{0,1\}^*,v\in\{1,2\}^*, \text{ and }u\text{ has the same number of 1s as }v\}.$$ Here is my attempt solution, but it is not completely correct, any hint is appreciated ...
2
votes
0answers
40 views

Can pushdown automata be without epsilon transitions? [duplicate]

Are pushdown automata without $\varepsilon$-transitions as powerful as those with them? Intuitively, if we need to make such a transition, we could just add the letters on the next transition we take, ...
2
votes
0answers
187 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. ...
3
votes
1answer
559 views

Equivalence of PDA and a counting PDA

Lets define a counting PDA as equivalent to a PDA except that the transition relation can use the stack size. Formally, let's define the transition relation as $\Delta:Q\times (\Sigma \cup \{ \...
0
votes
2answers
1k views

Making a CFG for a^i b^j c^k such that i+j = 3k

I have the language $L = \{a^i b^j c^k \mid i+j=3k\}$, however I am struggling to convert it to a CFG. I have made it into a PDA fairly easily, its just now getting this to the CFG which is the issue....
1
vote
1answer
394 views

How to prove that a bounded pushdown automaton is regular?

I'm studying computer science and I want to show that a language which is accepted by a pushdown automaton with a bounded stack height is regular, but I'm totally lost... Can someone try to explain ...
1
vote
1answer
49 views

Simulate $n$-PDA with $n-1$-PDA

I've heard that every $n$-PDA when $n > 2$ is as powerful as $2$-PDA. Unfortunately every proof I'm able to find uses references to Turing Machines, which I haven't learned about yet. I'm sure ...
0
votes
0answers
66 views

Where is proof that palindrom language is nondeterministic? [duplicate]

It is well-known that the language over $T$ with at least 2 symbols is nondeterministic. for simplicity, the language $\{ww^R: w\in\{a,b\}\}$ (even-length palindroms of $a$, $b$) is context-free, but ...
0
votes
0answers
93 views

Can we skip an input in push down automata

Hi here I'm giving a language L3={0^m 1^(n ) 2^m | m,n ∈ N} I designed this stack machine in order to accept this given language. Here I'm skipping 1 (no matter how many 1s are there) . Is it ok to ...
2
votes
1answer
415 views

Understanding context free grammars in conjunction with PDA

I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really ...
2
votes
2answers
966 views

Which of the following languages is accepted by this Pushdown Automaton?

This is a question from a past paper. I am struggling to get my head around the concept of a PDA. I understand that it is a Finite Automaton with a stack but am stuck as far as answering questions ...
0
votes
1answer
142 views

Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $

So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ } is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL i even know the grammar for it ...
0
votes
0answers
88 views

Simulate deterministic PDA with 1-tape Turing machine?

Is it possible to write a 1-tape Turing machine in order to simulate a deterministic PDA? How would this be done?
1
vote
1answer
136 views

Does a DPDA halt on all inputs?

Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs? Is this problem decidable? The standard halting problem is "Given a DPDA and an input $x$, determine ...
-2
votes
2answers
177 views

How do I create a pushdown automata for a language where some characters occur in times in multiples of 2 or 3

I have an assignment to create a pushdown automata for $L=\{a^{3n} c^m b^{2n} \mid n,m\geq 0, m\!\mod\! 2=0\}$ and I am confused how to handle $2n$ and $3n$.
7
votes
1answer
2k views

Decidability of halting problem for DPDAs with $\epsilon$-transitions?

For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space. But what about PDAs with $\...
2
votes
1answer
199 views

Should we eliminate left recursion before using NPDA to simulate CFG?

I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser". It says: If a language is context free, then some pushdown automaton recognizes it. Let A be a ...
2
votes
1answer
57 views

Methods of finding a PDA [duplicate]

I am working on finding a PDA that accepts the following language: L = {0^i 1^j 0^k 1^l | i < j and k < l} I am having trouble figuring out how to break ...
0
votes
1answer
142 views

CFG to PDA - no empty transitions

Working for my exam, this question popped up. Given the production rules below, draw a pushdown automaton to recognise the language it generates: S → AB A → BA B → BB B → T T → b ...
2
votes
1answer
147 views

context free grammar not closed under relative complement using product construction of pda and dfa

Hello friends need a bit of help, I Know that given: $$L_1 \in L_{cfg}, L_2 \in L_{reg}$$ $$L_2/L_1\notin L_{cfg}$$ because if it was contex free it would imply that $L_{cfg} $ is closed under ...
2
votes
1answer
1k views

Does PDA epsilon transition only transition when there's no more input?

For the Pushdown Automata episilon transition $\epsilon$ which is shorthand for $\epsilon; \epsilon / \epsilon$, does this mean that at any point, regargless of if there is input or not, you can ...
0
votes
0answers
244 views

Does this PDA reject the string aabbcc?

I've been given a solution, included below and I do not see how it would reject a string where i=j. The example given should reject an input string such as aabbcc ...
4
votes
1answer
392 views

Basic doubt in converting PDA to DPDA

This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism. When we have input a with Z at the bottom of the stack, ...
2
votes
1answer
2k views

Can every DFA be simulated by a PDA?

Given a Deterministic Finite Automata (DFA) $M_1$, does there always exist a Pushdown Automata (PDA) $M_2$ that accepts the same language as $M_1$? I.e. can any DFA be simulated by a PDA? ...
1
vote
0answers
59 views

Constructing Context Free Grammar with 3 terminal symbols, with two dependent pairs

I am new to Context Free Grammars and am having trouble wrapping my head around how to approach writing a CFG for the following language: ...
0
votes
1answer
3k views

Is Acceptance by Empty stack and Final state possible in the same PDA?

$L$ is the language accepted by the above PDA : $L = \{a^n\mid n\geq 0\}\cup\{a^n b^n\mid n\geq 0\}$ and is deterministic context-free is the language accepted by the PDA how can we accept $a^n$? As ...
1
vote
2answers
71 views

Can a DPDA decide if two letters appear the same number of times mod 5?

$ L = \{ w ∈\{0,1\}^* \mid |w|_0 = |w|_1 \mod 5 \}$ So i tried figuring out why this is CFL and whether its DCFL or not but i couldn't come up with any PDA! I'm studying for my exam and this ...
1
vote
0answers
43 views

Is DCFL closed under union with RL? [duplicate]

So i know that DCFL is not closed under union, but what about union with RL? Because what if both of the languages can start with the same string?then when we are building the DPDA for the union and ...
1
vote
1answer
287 views

Why would this be a deterministic context free language? $L = \{a^n b^n | n>0 \}$ $\cup$ $\{ a^n b^{2n} | n < 100 \}$

so the book that I'm reading says this is a deterministic context free language $L = \{a^n b^n | n>0 \}$ $\cup$ $\{ a^n b^{2n} | n < 100 \}$ But i think this is wrong Because : at the ...
1
vote
1answer
672 views

PDA pushing nothing given an input and the current stack top

If we had a language $$\sum = \{a,b,c\}$$ for a pushdown automata, and the transition $$a;A/AA$$ means "If you read in an a and ...
0
votes
1answer
879 views

Constructing a PDA for the language $\{a^mb^n | m > n\}$

i saw in a book how to construct a PDA for a case with m is equal to n . It's pretty simple, just push a symbol for every a and pop this symbol for every b that the PDA reads. But, i don't found a way ...
0
votes
1answer
37 views

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? [duplicate]

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? I should probably use Ogden's lemma, but I don't know how to do that in this case.
0
votes
3answers
505 views

Push-down automaton for a language with number of 1s double than 0s

This questions is taken from a complexity theory course. Design a push-down automaton that recognize $L = x \in \{0,1\}^* $ such that $x$ contains a number of ones double than a number of zeros. ...
1
vote
1answer
982 views

Understanding PDA and Equivalence of PDA and CFG

When we wanted to construct a PDA for $0^n1^n$ the idea was to put all the zeroes (which is a part of the input string) to the stack associated with the PDA, and then pop each of them when we get a $1$...
1
vote
1answer
318 views

Generating a Context Free Grammar(CFG) from a Language

I would really appreciate if anyone could tell me how to generate CFG from this language. I am trying to learn the procedure of generating CFGs from CFLs and I am able to solve easier problems.. but I ...
1
vote
0answers
46 views

Finding language family of given language

I came across following problem: Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any language, then what is the smallest language family $L'$ belongs ...
3
votes
1answer
62 views

Systematic approach or algorithm for designing a pushdown automata that accepts a langauge

I understand that designing automatons is mostly a creative process but, a month ago I was having a discussion with a classmate about designing a NPDA or a DPDA that accepts a non-trivial language (...
1
vote
0answers
118 views

Is universality problem of single state NPDA decidable?

I came across following problem: Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable? Now I know for DPDA/DCFG/DCFL, universality problem is ...
1
vote
0answers
484 views

Constructing a turing machine from a PDA - dealing with non-determinism

Given a PDA $P$, I believe we can simulate it with a turing machine with 2 tapes - one for keep reading the input and one for the stack. But, a PDA transition function may have multiple transitions ...
1
vote
1answer
345 views

DPDA - a language that contains the same number of A and B

I need help with creating Deterministic pushdown automaton for language: L = {v1w | v, w ∈ {a, b, c}*, #a(v) = #c(w)} where the number "a" in the string v is the same as "c" in the w string. In the ...
1
vote
0answers
357 views

Comparing non-deterministic and also the deterministic expressive power of FA, PDA's and TM'S [closed]

I am sorta confused and also could not find a answer online, but in terms of expressive power, . Non-deterministic FA, PDA, TM NFA < NPDA < NTM ...
1
vote
2answers
271 views

Existence of one and two state PDAs

I came across following fact in Automata book by Hopcroft, Ullman: Theorem 1: For every PDA accepting by empty stack (PDAeS), there is an equivalent one state PDA accepting by empty stack. I was ...
2
votes
2answers
21k views

How to convert PDA to CFG

I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG? For example: to write CFG for the automata My attempt: $S=A_{03}$ because $...
0
votes
1answer
153 views

Pumping lemma to show a language is not context free [duplicate]

I have started pumping lemma for context-free grammar by reading Sipser's book and there are two questions right at the end end of the topic which I don't understand how to solve or where to start ...
1
vote
0answers
328 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-...
2
votes
1answer
1k views

Confusion about Definition of DPDA and $\epsilon$-move

The DPDA definition is from sipser's book, and it mentions that the following PDA can convert to DPDA. I tried it, then I confused the definition! By definition, I could construct these $\delta(q_1,...
0
votes
1answer
82 views

Closure of a CFL under specific operation

Consider the following operation on language $L$: $\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$ I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and ...
2
votes
1answer
364 views

Show that 0^n1^n is decidable

I would like to know how would one go about and answer this question. I know that a language is decidable if a turing machine exists that accepts the strings in that language, and rejects otherwise. ...
1
vote
1answer
100 views

Push Down automata:- Basic doubt

I was reading CFG's and PDA's. I need to understand one basic point in that.I have solved some questions on final state acceptance by PDA.But in every answer,the string always end with epsilon(means ...