Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [pushdown-automata]

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

0
votes
1answer
29 views

What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?

I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking ...
0
votes
0answers
22 views

How to construct a pushdown automata using final states criterion and empty stack criterion?

I have been looking for tutorials or goods explanations about how to build a pushdown automata using the final states criterion and using the empty stack criterion, but I have not found anything ...
0
votes
0answers
37 views

Does a PDA(push down automata) always needs to have an empty stack after the final state is reached? [closed]

I am learning PDA and trying to construct a PDA for { $a^i b^j c^k \mid i,j,k \geq1,(i!=j $ or j!=k) }. For this I drew this. $q2, q4 ,q5$ states are for the condition j!=k. $q1, q3$ states are ...
1
vote
1answer
38 views

Context Free Grammer and PDA [duplicate]

So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says "L contains palindromes that don’t ever have the same character occur twice ...
1
vote
1answer
62 views

Context Free Grammer and PDA (Palindrome but without characters repeating in a row)

So this a question from my book and I have to make CFG of this language but I am confused what does it mean when it says "L contains palindromes that don’t ever have the same character occur twice ...
1
vote
1answer
26 views

Why is this pushdown automata for some palindromes right?

$B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$ Solution: For example: $111$ should be accepted steps are $q_1 \to q_2$ stack: [$\$$] $q_2 \to q_2$ stack: $[\$, 1, 1]$ (using up $11$...
1
vote
1answer
55 views

PDA of the language where the number of a's are NOT equal to the number of b's

I have this NPDA for language L = {w: num_a(w) == num_b(w)} all loops in q1 ...
2
votes
0answers
71 views

What is the simplest automaton that can compute the sum of two integers of arbitrary length?

It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length? I ...
0
votes
0answers
30 views

How to find a Pushdown Automaton for two different strings joined by a distinct symbol? [duplicate]

As the title suggests, I am trying to find the PDA for the language, $\{x\#y \mid x,y\in\{a,b\}^*, x \neq y\}$. My PDA non-deterministic splits at the beginning to 2 cases. The first case check if the ...
0
votes
1answer
52 views

Construct a Deterministic Pushdown Automaton for unequal number of elements

Can anyone help me construct a deterministic PDA for the following language: $$L=\{w\in(a,b)^* \mid \#_a(w)\neq \#_b(w)\}$$ Or can anyone check if the following solution is correct?
6
votes
3answers
3k views

Why do pushdown automata use a stack?

I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?
-1
votes
1answer
29 views

Convert grammar to Greibach form

The grammar is $S \rightarrow AA|a$$A \rightarrow SA|ab$The actual question is to find an NPDA accepting the language generated by this grammar but for that i firstly need to convert it into Greibach ...
2
votes
0answers
62 views

Which transducer models replacement in regex?

I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order. For example: ABC => CAB, which, with ...
0
votes
1answer
145 views

PDA to accept language with more a's than b's and c's

My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of ...
3
votes
1answer
59 views

Undecidable problem intersection of two DCFL languages is DCFL?

We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an ...
1
vote
1answer
110 views

Can PDA model Turing Complete objects if the objects' state are finite?

I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract. I am trying to understand the proofs of Chapter 6. ...
1
vote
0answers
8 views

Is there anything like equivalence classes in PDA (and more expressive ones, perhaps)?

The motivation for this question is the fact that partitioning DFA into equivalence classes is the mechanism that is used in model testing to generate test cases. However, obviously, DFA cannot ...
2
votes
1answer
31 views

$a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?

A related question: How to prove that a bounded pushdown automaton is regular? Well I proved that $a_k$ for each $k$ is the set of all the regular language. Thus $\bigcup_1 ^{\infty} a_k = \bigcup_1 ^...
2
votes
3answers
376 views

Are all finitely recursive context free languages parseable with a regexp?

Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown ...
-1
votes
1answer
49 views

How to convert a CFL to a deterministic PDA?

I am trying to complete this question. However, I am unsure of the steps necessary to complete the conversion from a CFL to a deterministic PDA. I know that $ww' | w \in \left \{ a,b \right \}^{*}, w'...
0
votes
1answer
61 views

Does a pushdown automata exists for the following language?

I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another ...
1
vote
1answer
26 views

Minimum number of letters

I have an assignment that I have to do and the question is Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}. Im not looking for the answer but rather some direction. I ...
1
vote
1answer
116 views

Construct a pushdown automaton for $\{a^{2n}b^{3n}|n\ge0\}$

My idea is to (not formal) push an 'a' when we see an a, nondeterministically guess when n a's were seen from the input word, go to the next state. From there, when we see an a, push 2 'a's into the ...
1
vote
1answer
67 views

Nondeterministic PDA for the following language with Kleene star

I had a question regarding converting a language with the Kleene star production into a PDA. Here's the particular language I was looking at in my textbook: $$L = (aaa^*bab)$$ My normal approach to ...
2
votes
0answers
26 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, ...
1
vote
2answers
40 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 ...
1
vote
0answers
79 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. ...
2
votes
2answers
42 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
1answer
63 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 ...
0
votes
2answers
279 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....
0
votes
0answers
10 views

How can I know when I should remove b's and when put a's? [duplicate]

I have the next language L = { a^n b^m c^p | n,m,p >= 0, n=\m or m=/p } And I have to construct a pushdown automata I don't know how to start resolving it Any suggestion? Thanks.
1
vote
1answer
39 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
59 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
50 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 ...
0
votes
0answers
51 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?
7
votes
2answers
152 views

Is this language a Deterministic CFL? $L = \{ a^n (a+b)^n | n>0\}$

$L = \{ a^n (a+b)^n | n>0\}$ a book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using ...
0
votes
1answer
106 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
52 views

Is there a NPDA with only 2 states for every Context Free Language?

So i saw this statement in a book but it had no proof is this even true? because i cannot come up with any idea that can make every CFL into a 2 state NPDA! how is that even possible?! also if this ...
1
vote
1answer
61 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
96 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$.
2
votes
1answer
96 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 ...
0
votes
0answers
67 views

PDA for concatenated languages

I am making a PDA for the following language: L = {0^i 1^j 0^k 1^l} where i > j and k > l I divided this up and made a PDA that worked for ...
2
votes
1answer
34 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 ...
2
votes
1answer
84 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 ...
0
votes
0answers
69 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 ...
1
vote
1answer
298 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 ...
3
votes
1answer
623 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? ...
3
votes
1answer
162 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
40 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
1k 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 ...