The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
0
votes
0answers
75 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
122 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
162 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$.
6
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
185 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
54 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
133 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
128 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
822 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
213 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 ...
3
votes
1answer
328 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
1k 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
56 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
69 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
243 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
565 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
736 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
412 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
743 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
272 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
60 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
104 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
429 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
297 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
306 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
217 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 ...
1
vote
2answers
17k 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
127 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
251 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
73 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
286 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
92 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 ...
-2
votes
1answer
62 views

Pushdown automaton for language with “or” [duplicate]

Find a pushdown automaton accepting the language $$L=\{A^i B^j C^k \mid 2k \le i \le 3k \text{ or } j \neq i+k \}.$$ I can't construct the automaton because I can only imagine it with multiple stacks ...
1
vote
1answer
439 views

Complement of DPDA

I read that we can find complement of DPDA by just complementing(toggling) the states of DPDA. Why can't we do the same with NPDA ? Also is DCFL closed under complement just because we can toggle ...
3
votes
3answers
5k views

Can you pop 2 elements at a time in a PDA

My question is N(a)=2N(b) ; No of a's = 2 * No of b's . So for every symbol b can I pop 2 a's simultaneously
1
vote
0answers
384 views

Why Acceptance by Final sate and Empty Stack in PDA?

Why there are two ways of accepting the input in PDA i.e. Acceptance by Final sate and Empty Stack I have seen examples which are accepted by both rules? There are some examples which are only ...
2
votes
2answers
2k views

Why are DCFL not closed under concatenation or Union whereas CFL is?

I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves ...
3
votes
1answer
652 views

Working of NPDA

I read that acceptance of languages by DPDA using empty stack is a subset of languages accepted by DPDA using final state because of prefix property. I understood this statement by taking an example ...
0
votes
0answers
84 views

A push down automaton that recognize exponential strings

How can I describe a Push Down Automaton that recognize the language $P=\{a^{2^n} | n \geq 0 \}$? My approach I know that the language can be described by a Turing Machine, but how i can the stack ...
-1
votes
1answer
796 views

How to build a PDA that accepts strings which have odd numbers of a and even numbers of b and has only 2 states?

How can i draw a PDA which has only 2 states and accepts strings which have odd number of a and even number of b? the alphabet is {a,b}, and the PDA has to be only 2 states?
0
votes
3answers
693 views

Are the sets of all finite automata and pushdown automata countable?

So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering ...
1
vote
1answer
214 views

is this a Context free Language : $L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$ [duplicate]

$L=\{W_1W_2 \mid W_1 \ne W_2 \: \text{and} \: |W_1|=|W_2|\}$ Alphabet = { a , b }* Considering L={WW} is not context free, shouldn't this be non context free as well? otherwise can you provide a ...
1
vote
1answer
417 views

Can we make a PDA with only 1 state which accepts a^n and n is odd?

We can have acceptance with empty stack, but in that case our stack at the start has to have a A in it, otherwise this machine will accept the empty string which is wrong But can we have a non empty ...
5
votes
3answers
952 views

Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
2
votes
2answers
2k views

Does DPDA accept all regular languages?

A DPDA which accepts by empty stack cannot accept all Regular Languages? Is it true that the DPDA cannot accept all regular languages? I am not able to understand this.As per my knowledge DPDA are ...