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
2answers
36 views

For every 4 ‘c’ in the input push a ‘c’ in the stack (Push down automata)

Given the following language: L = {$a^{2m}$ $c^{4n}$ $d^{n}$ $b^{m}$ : m,n >= 0} I’m trying to design a PDA. My aproach is: -for every 2 ‘a’ push an ‘a’ -for every 4 ‘c’ push a ‘c’ -then pop them ...
4
votes
1answer
65 views

Prove or disprove {wtw^R | |w| = |t|} is context free

The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$ It looks like the language can be "pumped" by context free pumping lemma, ...
0
votes
1answer
31 views

Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?

My assignment asks Let $S = \{ w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star ; (∃i < k) w_i\neq w_{i + 1}^r$ , i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. ...
0
votes
1answer
52 views

Is this a CFL: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$?

I recently found a question asking whether the language given below is context-free or not: $L_1 = \{wxyx | w, x, y \in (0 + 1)^+\}$ My intuition is that I can design a non-deterministic push-down ...
1
vote
1answer
27 views

Developing a Context Free Grammar whilst knowing the number of terminals

I am trying to develop a CFG for the language $L$ defined by: $L = \{a^{n+2}bba^{n-2} | n > 1\}$ The problem I am having is that I cannot develop the CFG for this language no matter what I try. ...
0
votes
1answer
25 views

Creating a PDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}

I didn‘t find a DPDA for the language L = {$a^{m}$ $b^{n}$ : m $\neq$ n}, so I guess an NPDA is the only option. NPDA are not very intuitive to me. The only solution I found online is: I don‘t ...
0
votes
1answer
43 views

Pushdown automaton from given code for parsing a while statement

I was preparing for my exam and have some questions that can possibly come on the test. There is a task to make pushdown automata from a given code: ...
1
vote
1answer
39 views

Can there be a language not Context free but still PDA acceptable?

Let the input alphabet be $Σ = \{1,x,=\}$ Let the stack alphabet be $\tau = \{1,\$\}$ where $\$$ is the initial stack symbol. Let,$q_0$ be the initial state of the PDA,$q_f$ be the final state of PDA,...
1
vote
2answers
68 views

How Intersection of Regular Language and a CFL is a CFL?

CFL is not closed under intersection. That means, if we have L1,L2 of CFL then L1 intersection L2 is not a CFL And we know, all Regular languages are CFL. Then ...
0
votes
0answers
29 views

What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
0
votes
0answers
40 views

Understanding PDA for odd length string with middle symbol 0

I came across this pdf, which describes the language of odd length string with middle symbol 0 as follows: Doubts: I dont understand the transition labels. In standard resources like books by ...
0
votes
1answer
34 views

Deterministic pushdown automaton for a given language

I am trying to make a deterministic pushdown automaton from this language but without success. Here is the language definition: $\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $ ...
0
votes
0answers
11 views

Push Down Automatas: Is it still an accept state if stack is not empty?

I'm currently seeing if a PDA is in an accept state give an input string. After reading the entire input tape, I am currently in the accept state. However, in the stack, there are two items in it. So ...
1
vote
1answer
76 views

Why no DPDA can accept Palindrome? (according to this proof)

This proof is from the book "Introduction to Languages and the Theory of Computation" by John C. Martin. My question is from the pink part at the second page: It follows in particular that no ...
3
votes
2answers
77 views

Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?

$ \# a^nb^{2^n} \# $ such that • The alphabet of the machine is {, a, b, x}. • The symbol x will never appear on the input a. • The contents of the tape at completion may be anything. • The head ...
1
vote
1answer
35 views

Creating a Deterministic Push-Down Automaton for the Union of two languages

Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for ...
0
votes
0answers
27 views

Prove that any PDA/CF language with 1 character is regular [duplicate]

I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.
0
votes
0answers
11 views

can a PDA without lamda-transition accept every context free language? [duplicate]

I want to know if every context-free-language can be constructed with a PDA without lambda transitions. I have tried to give a counter example but couldn't. Is there a theorem proving such statement ...
0
votes
0answers
27 views

Converting an NPDA to a CFG

I have a question regarding conversion of NPDA to CFG. The above picture is from my lecture slides. I dont understand why they are saying 1 can be popped while transitioning from q0 to q1. It is in ...
0
votes
0answers
22 views

Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters

I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
2
votes
1answer
43 views

Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?

I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ...
2
votes
1answer
54 views

Does this argument prove CFLs are not closed under union?

Context free languages are not closed under complementation. This follows from their property of non-closure under intersection: If CFLs were closed under complementation, then they must have also ...
2
votes
0answers
32 views

Is the following PDA a DPDA or NPDA?

Let the language be : $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w)\}. $$ Now the PDA that I've designed for this language and seen at many other places is : ...
0
votes
0answers
41 views

Pushdown Automata for number of a less than 2 times number of b

Suppose we want to design a pushdown automata for $L=\{x \in \{a,b \}^{*}:|x|_a<2|x|_b \}$, can anyone check whether my automata works? we have 4 states $\{q_0,q_1,q_2,q_3 \}$, three stack symbols ...
1
vote
1answer
124 views

Is Half - Palindrome subset of a context-free language context-free?

Suppose we have $L$ being a context-free language. Let $L'=\{x \in \Sigma^* | xx^R \in L \}$, is $L'$ context-free as well? I know that if $L$ is regular then $L'$ is regular as well by constructing a ...
1
vote
2answers
111 views

Proving the decidability of whether a CFG generates a particular string or not

Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$. Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string ...
1
vote
1answer
30 views

Can you create a deterministic PDA for non-palindomes?

Using non-determinism to create a PDA to recognize non-palindromes is easy. My first instinct was to say yes, but it would be extremely complicated. After thinking about it, I don't think you could.
0
votes
0answers
62 views

Constructing a PDA to accept the language {a^i b^j c^k where i,j,k>0 and i<=j<=2k}

Can anybody help me out with this? If I try to compare $a$'s with $b$'s to check if $j\ge i$ then I won't be able to compare the same number of $b$'s with the number of $c$'s that is to check if $j\le ...
1
vote
0answers
118 views

Pushdown Automata - constructing a PDA to recognise a language with at least as many as as bs

I am trying to construct a 3-state PDA to recognise (I need to create a transition diagram for this question) ...
0
votes
1answer
52 views

Pushdown Automata - can you have multiple transition functions options between 2 states?

I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states? For example, ...
2
votes
2answers
41 views

DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$

I need some help with the following task: I have to construct a DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$ with $|y|_1 \le k$ and $k \in \mathbb N: k\ge1$}\}$. How can I recognize that the new ...
0
votes
1answer
180 views

Pushdown Automaton to accept all strings such that no prefix has more 1’s than 0’s

Design a Pushdown Automata, accepting either by final state or by empty stack to accept the set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s This is a homework question,...
1
vote
0answers
34 views

What is the class of automata with stack and unlimited amount of memory, addressable only by immediates?

Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code. ...
4
votes
3answers
595 views

Context-free grammar of the concatenation of a string S and subsequence of reversed S

I have to find a Context-Free grammar that generates the language: $L_1 = \{x\#y\ |\ y$ is a subsequence of $x^R$, and $x\in\{a,b\}^*\}$, $\Sigma=\{a,b,\#\}$ The concatenation of two mutually ...
4
votes
1answer
188 views

A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...
1
vote
1answer
54 views

It is decidable whether a pushdown automaton will accept a word? [duplicate]

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable. I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
1
vote
2answers
56 views

L(M)=L where M is a TM that can move right or stay, so L is decidable

Suppose that L(M)=L where M is a one tape TM that can move right or stay. I need to Show that L is decidable. I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
3
votes
1answer
53 views

Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?

In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1] In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although ...
1
vote
0answers
46 views

How to visualize non-deterministic pushdown automata?

My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
2
votes
1answer
89 views

Is the halting problem solvable for NPDAs?

After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my ...
3
votes
1answer
43 views

Proof emptiness for PDA is $\mathcal{O}(n^3)$

It is well known that the emptiness problem vor PDAs is in $\mathcal{O}(n^3)$. I couldn't find a good paper proving this theorem. Furthermore a proof for VPAs would be fine for me as well if that is ...
0
votes
0answers
44 views

Find PDA for CFL = {x#y | |x| = |y| and x ≠ y} [duplicate]

I am studying push down automata. When I read a solution for showing $L = \{x\#y \mid x \neq y, x,y \in \{0,1\}^*\}$ is a CFL, I could understand $L = L_1 \cup L_2$, $L_1 = \{x\#y\mid|x| \neq |y|\}$, ...
0
votes
0answers
27 views

About Specification of PDA

I was learned NPDA is specified by a tuple $P = (Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) $, $Q$ is a finite set of states $\Sigma$ is a finite set of input symbols (input alphabet) $\Gamma$ is a finite ...
4
votes
0answers
87 views

Detecting loops in NPDAs

I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
-1
votes
1answer
178 views

Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }

$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$ I have trouble about this PDA. Anybody can help me about draw this PDA?
0
votes
0answers
284 views

a^nb^nc^nd^n using 2-stack PDA

I need to construct a PDA using 2 stacks for accepting the language $L = \{a^nb^nc^nd^n | $ $n \geq 0\}$. Pushing $a$'s to first stack and $b$'s to second and poping them for corresponding $c$'s and ...
1
vote
1answer
113 views

Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity

I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\#y$ where $x$ and $y$ are strings of 1s and 0s such that there ...
2
votes
0answers
36 views

kPDA handling multiple epsilon transtions

I'm assigned to build a kPDA with 2 stacks that handles {w#w, where w is a string of (0,1)*}. I understand the # delineates the two strings, but I'm unsure of the logic when popping off stacks with ...
0
votes
0answers
83 views

Proving the Complement of a DCFL is DCFL [duplicate]

If I Have a DCFL $L$ ( a CFL which can be recognised by a DPDA ), How do I prove that $\overline{L}$ is also a DCFL I checked my textbook for a proof but I wasn't able to understand the language. Can ...
3
votes
0answers
25 views

Automaton without stack for visibly pushdown languages

This paper here describes an alternating automaton which can recognize visibly pushdown langauges without using a stack. Unfortunately the transformation from NVPA to such an automaton is skipped in ...

1 2 3 4 5 8