# Questions tagged [pushdown-automata]

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

370 questions
Filter by
Sorted by
Tagged with
11 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 ...
25 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.
28 views

### PDA a^n b^(n+m) a^m| n, m ≥0

Can someone please help me solve this PDA question. The language is given below: $L = \{a^n b^{n+m} a^m \mid n, m ≥0\}$ Thank you.
12 views

### Using a PDA, show that ( x * y ) + x is a valid string

Using a PDA, show that ( x * y ) + x is a valid string. im having trouble with part C
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 ...
20 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 ...
20 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, ...
37 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 ...
38 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 ...
29 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 : ...
38 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 ...
102 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 ...
65 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 ...
26 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.
44 views

65 views

### Make a Pushdown automata that accepts a language defined by strings that contain the same number of a and b [duplicate]

How do I build a pushdown automata that accepts the language over the alphabet $\Sigma = \{a, b\}$, defined by the strings $w$, such that $|w|_a = |w|_b$? I'm sorry I can't give any approach of what ...
65 views

### How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.
105 views

### Prove $L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $(mod$ $13) \}$ is regular or context-free or neither

$L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $(mod$ $13) \}$ Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-...
43 views

### NPDA transitions to different states by taking same input and popping same top element of a stack

Suppose i have some NPDA and there is some transition functions defined as: $\delta(q_{1},a,A) = (q_{2}, A)$ $\delta(q_{1},a,A) = (q_{3}, Z)$ Is it allowed? I understand, that since the NPDA is ...