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
1
vote
1answer
450 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
888 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
97 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
1answer
277 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?
2
votes
2answers
163 views

Is the language with decreasing numbers of a, b and c context-free by pumping lemma?

So I've been given the following language on an assignment. It is the only question I have left of 10, and I've been racking my brains out trying to solve it for hours. $$L=\{w:w\in(a+b+c)^*, n_a(...
-1
votes
1answer
219 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
89 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 ...
4
votes
1answer
392 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
0answers
13 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 ...
3
votes
1answer
91 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
500 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
vote
1answer
190 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 ...
3
votes
3answers
11k views

Push down automata for $\{a^n b^n c^n | n \ge 0\}$

I am learning about context free languages. I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's. Intuitively however it seems that a ...
-1
votes
1answer
273 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
152 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
27 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
215 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 ...
2
votes
2answers
136 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
42 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
192 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
588 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
477 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
68 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
110 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
514 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
1k 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
147 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
90 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
179 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
191 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
213 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
67 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
154 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
167 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
256 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
447 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
64 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
48 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
304 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
763 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
980 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.

1 2
3
4 5
8