We changed our privacy policy. Read more.

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
4
votes
1answer
1k 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, ...
1
vote
0answers
86 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
4k 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
80 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
71 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
474 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 ...
0
votes
1answer
182 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 ...
1
vote
1answer
1k 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
2k 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
40 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.
1
vote
2answers
1k 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$...
2
votes
1answer
460 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
48 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 ...
1
vote
0answers
167 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 ...
3
votes
1answer
83 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
670 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
0answers
656 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 ...
0
votes
1answer
182 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
2answers
587 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
0answers
660 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-...
0
votes
1answer
93 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
3k 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,...
2
votes
1answer
757 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
195 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
65 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 ...
0
votes
3answers
1k views

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

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
630 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
1answer
949 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 ...
1
vote
0answers
417 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 ...
3
votes
3answers
4k 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
1k 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
142 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 ...
0
votes
3answers
1k 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 ...
2
votes
1answer
402 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
583 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 ...
-1
votes
1answer
2k 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?
3
votes
1answer
5k 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 ...
0
votes
1answer
181 views

Check if given language is CFL

Assume language $L$ as follow:- $$ L = \{ a^n b^x c^m d^y | (n=m) \lor (x=y)\} $$ Is it possible to design DPDA/NPDA for this? I know if the condition would have been "and" then it is not possible. ...
7
votes
2answers
1k views

Do NPDA work in parallel?

Assume my language is $$ L= ww^{r}\ $$ Now when we use NPDA for this,we will guess middle every time. It may be actual middle or it may not, so a new branch is created every time as I have a choice ...
0
votes
1answer
3k views

PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
1
vote
1answer
288 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 ...
3
votes
1answer
3k views

simulation of PDA with 2-tape Turing machine [closed]

Can someone give me suggestions how can I construct a 2-tape Turing machine which simulates PDA ?
1
vote
0answers
458 views

How to draw NPDA for language $L = \{ a^i b^j c^m \mid m \ge \min( i,j) \} $

$L_1 = \{ a^i b^j c^m \mid m ≥ min(i,j) \}$ $L_2 = \{ a^i b^j c^m \mid m ≥ max(i,j) \}$ Which language is CFL ? ANS : $L_1$ is CFL but $L_2$ is NOT. My understanding :  For Language $L_1$ : ( ...
-1
votes
1answer
296 views

construct a deterministic PDA for the language

Can someone help me to construct a deterministic PDA for the following language: $L = \{0^n1^m | n \geq m$ and $m,n \geq 0 \}$ Here is my suggestion : the states are z0,z1,z2 , z0 is final state ...
1
vote
1answer
1k views

Context free grammar for $bin(n)bin(n+1)^R$

It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free. Here, at 1.b, is a PDA which ...
0
votes
0answers
102 views

Providing an algorithm for a given PDA

I was asked the next question in my homework assignment: I just want to make sure that I fully understand what it is that's required of me. Am I asked to find an algorithm which decides if the ...
3
votes
1answer
960 views

If a language L is regular then the given operation sort(L) is context free

I was asked in one of my homework tasks this next question and I'm not quite sure how to handle it: Sort(w) is an operation which takes a string (w) from a given language and sorts the characters in ...
2
votes
2answers
1k views

Given a DFA A, give a formal construction of a PDA with three states M such that L(A) = L(M)

given a Deterministic Finite Automata, I am looking for a formal construction of Push Down Automata with 3 states such that the languages of the DFA and the PDA are the same. How we can prove ...
2
votes
1answer
350 views

Do deterministic context free grammars always have corresponding deterministic push down automata?

A language $L$ is deterministic context-free if and only if there is a deterministic push-down automaton M such that $L = L(M)$. According to the answer key of this quiz, the above statement is ...
1
vote
0answers
844 views

Equivalence of final state and empty stack PDA [duplicate]

I have done some reading on these two types of PDA and, to my layman eye, it looks like one simply 'wraps' an empty stack PDA with some extra transitions to create the final state PDA. Since these are ...

1
3 4
5
6 7
10