Questions tagged [pushdown-automata]

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

474 questions
Filter by
Sorted by
Tagged with
22 views

PDA for wcw^r confusion

Note-: The transition rules are in the form of inputsymbol, topofstack/operationontopofstack I think this(not the convention but the given PDA) is wrong because we are not doing this case. In state q1,...
81 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
28 views

Constructing PDA for $L = \{w\in\{a,b\}^{\ast}\;|\; |w|_a > 2|w|_b\}$

Construct a PDA, which recognizes the following language $L$: $L = \{w\;|\; |w|_a > 2|w|_b\}$, so it is the language that consists of words which have more than twice as many $a$'s as $b$'s. I ...
34 views

What kind of words does this PDA accepts

I have a PDA A = ({q0, q1}, Σ = {a, b}, Γ = {a}, δ, F = {q1}), with these transition functions δ: ((q0,a,ε),(q0,a)); ((q0,b,ε),(q0,a)); ((q0,a,ε),(q1,ε)); ((q1,a,a),(q1,ε)); ((q1,b,a),(q1,ε)). The ...
42 views

45 views

Deterministic Pushdown Automata that accepts #a = #b

I am trying to create a DPDA that accepts words from the following Language: $$L = \{wx \; | \;w \in \{a,b\}^*, \#a = \#b \}$$ My intuition was to initially put an $x$ on the stack and then write an ...
24 views

37 views

pushdown automata question

We define a new model: A "100-PDA" is a pushdown automaton with at most 100 states and with at most 100 symbols in the stack alphabet. Prove or disprove the following statement: "There ...
49 views

How to show that pda accepts empty language?

I have to show that a PDA accepts empty language, but for this I have to use some algorithm, with what kind of algorithms could I demonstrate it? I've heard about the algorithm from Moore, Brzozowski ...
34 views

Pushdown automaton with binary stack

I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language ...
33 views

Unambiguous formal grammars for a specific class of languages

Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$. Now suppose that $q \in \mathbb{Q}$ is a positive ...
36 views

PDA accepting of a specific symmetric language

Assume we have PDA that accepts a specific symmetric language on $\{a,b\}^*$. if we have $a$ This side of the string, on the other side of the string we have $aa$. and if we have $b$ This side of the ...
41 views

37 views

Construct a PDA that recognizes $L = \{w : w \neq a^n b^n : n ≥ 0\}$

I'm trying to find the PDA of the above language. I understand that this is the complement of the language $L_1=\{w : w=a^nb^n : n\geq0\}$ However, I can't understand the idea behind constructing the ...
40 views

PDA for the language { $a^i b^j c^k \mid i,j,k \geq0, 7j = 5i + 6k$ }

I have seen this similar question but I can't seem to apply the same technique for the equation $7j = 5i + 6k$
47 views

PDA for $\{a^ib^jc^k \mid (i+j) \bmod 3 = 0, k = i + j\}$

Construct a pushdown automaton that accepts $$\{a^ib^jc^k \mid (i+j)\bmod 3 = 0, k = i + j\}$$
73 views

Two way deterministic pushdown automaton accepting word consisting of two equal words

I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language: {ww | w ∈ {a, b}*} Does anyone have any idea? Thanks a lot
125 views

Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem: Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C ...
57 views

Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$

I want to construct a PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ where $Σ=\{a, b\}$. Here is my try: I know that context-free languages are closed under union operation. Also I know how to make a PDA for ...
180 views

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Consider the language $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements. $\quad\quad\text{I. }L$ is deterministic context-free. $\quad\quad\text{II. }L$ is context-...
34 views

Turing machine without return equivalent to Finite Automaton, PushDown Automaton or Turing Machine?

I have seen that a Turing machine without return is a Turing machine $M$ which at each stage of its calculation systematically moves its read / write head to the right.The aim of the exercise is to ...
44 views

Different PDA design processes -- both valid?

This video shows how to design PDA from a CFG: https://www.youtube.com/watch?v=ZImtQBMSW_Y Basically, we always have 4 basic states, and one of them is a "hub" for loops that implement ...
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?