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 about state machines with a single stack for memory. They characterize the class of context-free languages.

2
votes
0answers
16 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
38 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
41 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
86 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
6 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
23 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
358 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
37 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
49 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 ...
0
votes
0answers
29 views

Is Pushdown Automata “equivalent” to RegEx with balancing group?

From my textbook, NFA, DFA, and Regular Grammar are "equivalent" in the sense that they can be transformed into each other. I learned from the Internet that: Nondeterministic Pushdown Automata is "...
1
vote
1answer
55 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
44 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
38 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
42 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
35 views

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

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
49 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
133 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
35 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
44 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
46 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
136 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
96 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
30 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
54 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
71 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
68 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
50 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
29 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
69 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
51 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
170 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
518 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
118 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
36 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
708 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
49 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
32 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
78 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
39 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
178 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
196 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
34 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
1answer
281 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
54 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
44 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
52 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 ...