Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
539
questions
3
votes
2
answers
441
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 ...
- 33
-2
votes
1
answer
126
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 ...
- 21
1
vote
0
answers
66
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 ...
- 67
2
votes
2
answers
213
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-...
- 1,112
1
vote
2
answers
92
views
PDA accepting all words not of the form $b^na^n$
I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages.
If I have context-free ...
- 67
1
vote
1
answer
34
views
Unix glob() function and formal language equivalence
Can we express the matching capabilities of Unix library function glob() using a single-stack push-down automata, i.e. set of context free formal languages? If not, ...
- 111
1
vote
1
answer
53
views
Can a Turing machine or Push Down Automaton construct languages of type 3?
I am not quite sure, whether automata can construct languages over their types. For example, a Push down automaton can construct a language of type 2 - does that mean that a PDA also can construct a ...
- 13
1
vote
1
answer
236
views
Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$
I understand that the language $L = \{ a^mb^nc^k \mid m=n \text{ or } n=k \}$ is context-free because it can be represented as the union of $L_1 = \{a^mb^mc^k\}$ and $L_2 = \{a^mb^kc^k\}$, which are ...
- 123
1
vote
1
answer
59
views
Reduce PDA for a given language
I drew a Push-down Automata, accepting the following language:
$$
\{ xcy : x,y \in (a+b)^*, \#_a(x) > \#_{bb}(y) \}.
$$
Here $\#_{bb}(y)$ counts the number of times that $bb$ appears in $y$, with ...
- 13
1
vote
1
answer
216
views
PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1
Consider the language $\{ uv : \text{$|u| \ge |v|$ and $v$ contains a 1}\}$.
I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if ...
- 37
3
votes
1
answer
62
views
Where to put the state in a two-stack push down automaton?
theoretically, the state is between the two kleene-stars of the work-alphabet
gamma* q gamma*
where q is the current state and each ...
- 201
3
votes
1
answer
927
views
Can PDA have empty stack transition?
From a youtube video, this PDA can recognize any palindrom.
However, from wikipedia, here is one of the criteria of PDAs.
We clearly see that the transition function can't take an empty stack as ...
- 165
1
vote
1
answer
72
views
Some questions regarding methods for solving pushdown automata problems
I have found some problems whose solving "patterns" appear quite recently, and I am not sure if the way I'm solving them is the most correct/efficient one:
For example, take this language:
$\...
- 239
1
vote
1
answer
143
views
Is there a pushdown automaton for $\Sigma^* \setminus \{ a^n b^n c^n \mid n \ge 0\}$?
According to this statement:
Every regular language is context-free. Regular languages are closed under complement, so the complement of a regular language is regular. Consequently, any regular ...
- 113
0
votes
1
answer
439
views
Drawing a DPDA for the language $L=\{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ in Sipser's format
As I know $L=\{w\in\{a,b\}^*\mid n_a(w)=n_b(w)\}$ is a deterministic context free language. I have drawn a push dawn automata for this language in the format of Sipser as the following
However, as ...
- 43
1
vote
1
answer
129
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
0
votes
1
answer
162
views
Can PDA accept only by final state without finish reading input?
I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
- 151
-1
votes
1
answer
71
views
What is the computational class of a pushdown automaton with real values?
Say there is a push-down automaton, in this example I'll use a Deadfish-like set:
+: increase x by 1
0: set x to 0
...
0
votes
1
answer
669
views
Create a PDA that accepts the following language
I need to create a PDA that accepts by empty stack and accepts the language formed by strings over the alphabet $\{a, b\}$ of the form: $uw$, where $w$ is the string $u$ reversed and doubled. So, for ...
- 3
0
votes
1
answer
2k
views
{a^n b^n c^n | n>=1} - PDA
I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive.
How I attempted it ...
- 3
3
votes
0
answers
71
views
bounding the height of stack when checking acceptance pushdown automaton
Let $A$ be a nondeterministic PDA (with empty stack acceptance). I am looking for a reference for a statement of the following form.
There exists a constant $c$, computable from $A$, such that:
if $w$...
- 29.8k
1
vote
1
answer
1k
views
Decidability of PDA
I have following problem:
INFPDA={⟨A⟩ |A is PDA and L(A)=infinite language}
Prove that this is decidable problem.
So my idea how to solve this problem is the ...
- 141
1
vote
1
answer
268
views
Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?
I was looking for the limitations of a CFG. I think there is some limitation given there are only finitely many states of a PDA (or non-terminals in a CFG).
I suspect that languages like $\text{L} = \{...
- 194
0
votes
0
answers
76
views
Is there only one unique DPDA that accepts a specific language?
Or is it possible to construct more than one DPDA that accepts exactly the same language?
2
votes
3
answers
447
views
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?
I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the ...
- 21
0
votes
1
answer
391
views
Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
I have tried to find a pushdown automata and it turned out to be a ...
user119726
3
votes
3
answers
357
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 ...
- 41
0
votes
2
answers
232
views
How can I efficiently construct a CFG from a language
I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}.
So m can be infinitely bigger than n but n can ...
- 41
0
votes
0
answers
70
views
The class of grammars recognizable by backtracking recursive-descent parsers
It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
- 213
0
votes
1
answer
1k
views
Converting PDA to CFG
I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\...
0
votes
1
answer
280
views
PDA kleene star construction
I know how to prove that CFL are closed under kleene star operation using CFG.
I can't find online or in class notes a proof using PDA.
I would appreciate description of the basic idea (not formal).
- 109
0
votes
1
answer
76
views
Is it possible to form a PDA for this language?
$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$
Is this even context free?
I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (...
- 217
0
votes
1
answer
458
views
How can I combine 2 PDA's into 1
I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$}
I know the idea of building each one separately but how do I combine them into 1 PDA?
LHS: for every 'a' I push 'A' inside stack and for ...
- 217
0
votes
0
answers
470
views
Is it necessary for a Push down Automaton (PDA) to have a stack?
I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA:
Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
- 101
0
votes
2
answers
146
views
Build PDA for a language with unknown input alphabet
$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows:
$$L_{12}=\left \{ w_1\cdot w_2\mid w_1\in L_1\land w_2\in L_2\land |w_1|=|w_2| \right \}$$
In this exercise I am not given ...
- 217
-1
votes
1
answer
281
views
Formal definition of non deterministic PDA
How would you convert the following formal definition of deterministic pushdown automata into non deterministic ?
Deterministic PDAs In general terms, a deterministic PDA is one in
which there is at ...
-1
votes
1
answer
353
views
Turing Machine construction of M=wwRw form
Construct a Turing machine for
M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}.
I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
0
votes
1
answer
47
views
checking configuration history of Turing machine using PDA
I am trying to understand the technique of using configuration history in proofs.
To prove that:
$\{<M>|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$
given $<M,w>$ we ...
- 109
1
vote
1
answer
187
views
Is this push-down automaton non-deterministic, as JFLAP states?
There is a tool called JFLAP, which, among other things, can analyze push-down automata, and find non-determinism.
In this example it is detecting non-determinism in state ...
- 163
0
votes
0
answers
49
views
Context free grammar to Chomsky normal form
I have a hard time understanding how to convert the following context free grammar to Chomsky Normal Form:
S $\rightarrow$ aSX | B
B $\rightarrow$ bBX | ε
X $\rightarrow$ a | b
I have a solution
S $\...
- 1
-1
votes
1
answer
140
views
Create a PDA for the given language
The task is to create a PDA for this language. The |u| a reffers to the number of a's in that word. I have tried working on it as two separate languages that I can later combine, but I fail to even do ...
- 3
0
votes
0
answers
159
views
Can a pushdown automaton solve the halting problem for another Pushdown automaton?
Can a pushdown automaton solve the halting problem for another Pushdown automaton?
It's already shown here turing machine can solve the halting problem for a pushdown automaton.
Decidability of ...
- 336
0
votes
1
answer
72
views
Is there any property about height of PDA?
I'm trying to find a PDA for $L$ which modifies the stack height at most one.
$L=\{a^ib^i\mid i\geq 0\}$
I think there is no such PDA but how can I prove it?
My attempt is for a given string, find ...
- 1
0
votes
1
answer
149
views
Solving membership problem for a PDA-generated language without converting the PDA to a CFG
The classic solution for the membership problem of a language generated by a PDA is to convert said PDA to a CFG and then to use CYK or a similar algorithm. I was wondering if there are any known ...
- 156
0
votes
0
answers
148
views
context-free language : if yx belongs to cfl then xy is also cfl [duplicate]
I faced a problem.
What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language.
C is a Context-Free Language.
I think we can use the PDA ...
- 109
2
votes
1
answer
217
views
When our two-state PDA constructed from CFG is non-deterministic PDA?
We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
- 358
-1
votes
1
answer
80
views
How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A
Let us consider the following Context-Free Grammar
G = ({S,A,B,C,D},{a, b}, S, P)
with production rules P:
S → SSA | Bb
A → BSA
B → A | Cb
C → AD | Cb | ɛ
D → a | b | ɛ
Let L be the language ...
- 3
-1
votes
1
answer
669
views
Construct a PDA that recognizes the following language: L={uawb: u,w ∈ {a,b}*, |u|=|w|}
I am having trouble finding the PDA with 1 state for this one. So far my solution is this but i cant figure out how to get to 1 state.
Alphabet:
{a, b},
Stack alphabet (the first symbol is the ...
- 25
0
votes
2
answers
302
views
PDA with more than one initial state
I'm wondering if PDAs with more than one initial states are also accepting context free languages.
If found that question on this site about NFAs and would like to know if this answer is also valid ...
user119625
4
votes
3
answers
99
views
$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language
Let $\mathcal{L}$ be context free language over alphabet $\Sigma$. Define $\mathcal{G}$ as
$$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ ...
- 207