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
0answers
18 views

Prove or disprove the following language is context free

The language $L$ defined as: $L = \{wtw^R | w,t \in \{0,1\}^\star \text{ and } |w| = |t| \}$ It looks like the language can be "pump" by context free pumping lemma, but pumping lemma doesn't prove ...
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
42 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
25 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. ...
2
votes
3answers
3k 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 ...
4
votes
4answers
480 views

Relaxing the stack in a push down automata

Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol ...
0
votes
1answer
21 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 ...
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,...
0
votes
1answer
40 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
2answers
66 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
33 views

is L not decidable? [closed]

Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$. Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable? But isn't $L$ decidable since it is possible to ...
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?
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 ...
0
votes
0answers
30 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
33 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
150 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. ...
3
votes
2answers
76 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
32 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
24 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
40 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 ...
8
votes
2answers
270 views

Is {a^n (a+b)^n | n>0} a Deterministic CFL?

$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 ...
2
votes
0answers
31 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 : ...
1
vote
1answer
119 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 ...
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 ...
0
votes
1answer
49 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, ...
1
vote
2answers
100 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
1answer
149 views

Does left factoring CFG make it unambiguous?

I came across following problem: If the CFG is left factored then it must be Unambiguous and Not left Recursive. TRUE/FALSE? I have many thoughts about this. But I feel they are somewhat ...
0
votes
0answers
59 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
117 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) ...
3
votes
2answers
1k views

Why DCFL is not closed under kleene star?

I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example
1
vote
2answers
121 views

Formal definition of an empty stack accepting PDA

PDA's are usually defined using the 7-tuple convention. $M=(Q, \Sigma, \Gamma, \delta, q_{0}, Z, F)$ F is the set of accepting states. I want to design a PDA accepting by empty stack, so using ...
7
votes
3answers
4k 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?
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
173 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
2answers
375 views

Why is this pushdown automaton 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
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
588 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 ...
26
votes
3answers
1k views

Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?

Is the following language context free? $$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$ As pointed out by sdcvvc, a word in this language can also be ...
4
votes
1answer
171 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 ...
2
votes
5answers
11k views

Explaining why a grammar is not LL(1)

I need some help with explaining why a grammar is not LL(1). Let us take the following grammar: $$ \begin{align} S \rightarrow & aB \mid bA \mid \varepsilon \\ A \rightarrow & aS \mid bAA \\ ...
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
54 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
51 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 ...

1 2 3 4 5 8