Questions tagged [pushdown-automata]
Questions about state machines with a single stack for memory. They characterize the class of context-free languages.
566 questions
3
votes
1
answer
637
views
Is $L = \{ a^n b^m c^k \mid n,m,k > 0\ \text{and}\ k = |n - m| \}$ CFL or DCFL?
The language is:
$$
L = \{ a^n b^m c^k \mid n,m,k > 0 \text{ and } k = |n - m| \}.
$$
Splitting cases:
If $n > m$: $L_1 = \{ a^n b^m c^{n-m} \mid n > m > 0 \}$
If $m > n$: $L_2 = \{ a^...
- 91
1
vote
0
answers
50
views
CFG for language a^m b^n where m >= 2n - 3
I am trying to make CFG for
$$
L = \{ a^m b^n \mid m \ge 2n - 3, m,n \ge 0 \}
$$
Mostly I study TOC from YouTube, I don’t have classmates or teacher to ask. I know how to make CFG for simple cases ...
- 91
0
votes
1
answer
92
views
How does an non deterministic PDA compute?
This is the PDA of the language
$L=\{ww^{R}:w\in\left(0\cup1\right)^{*}\}$
Where $w^{R}$ is the reverse of string.
Let $s=0110$ be the string, clearly $s\in L$. My query is as follows,
My query:-
PDA ...
- 179
7
votes
1
answer
311
views
Is the following language context free $\{xy\mid |x|=|y|\land \#_a(x)=\#_b(y)\}$?
I was discussing context free languages with some friends, when we came up with the following language over the alphabet $\Sigma=\{a,b\}$:
$$L=\{xy\mid |x|=|y|\land \#_a(x)=\#_b(y)\}.$$
Intuitively, ...
- 4,964
0
votes
1
answer
79
views
Why is the complement CFL?
I have this language:
$L = \{a^nb^nc^kd^k∣n > k\}$
I get why $L$ isn't context free, but why $\bar{L}$ context free?
- 101
1
vote
1
answer
133
views
Can we assume final states in DPDAs have no $\epsilon$-transitions?
I'm struggling with a conceptual issue related to deterministic pushdown automata (DPDAs) as described in the book Introduction to Automata Theory, Languages, and Computation (3rd ed.) by Hopcroft, ...
- 367
3
votes
1
answer
151
views
How to construct a DPDA for a $\{x\#y \mid x \in L \land xy \in L\}$ when $L$ is a DCFL
Assume $L$ is accepted by a deterministic pushdown automaton (DPDA) $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$. I want to construct a DPDA that accepts the following language:
$$ \{x\#y \mid x \in ...
- 367
2
votes
2
answers
142
views
Why does this PDA qualify as deterministic if multiple transitions are possible after reading a symbol?
In the book Introduction to Automata Theory, Languages, and Computation (3rd ed.) by Hopcroft, Ullman, and Motwani, a deterministic PDA (DPDA) is defined as follows:
A PDA $ P = (Q, \Sigma, \Gamma, \...
- 367
2
votes
1
answer
136
views
Non-Regular DCFL Without Prefix Property
A language $ L $ has the prefix property if there are no two distinct strings $ x $ and $ y $ in $ L $ such that $ x $ is a prefix of $ y $.
It is known that a language $ L $ is accepted by a ...
- 367
1
vote
1
answer
148
views
Show that $L=\{a^nb^m:n>m\}$ is a deterministic context-free language
Above language $L$ is a context-free language, but I found that this language can only represented by the NPDA. Because the conditions of DPDA (Deterministic PDA) says:
If $\delta(q, \lambda, b)$ is ...
- 56
2
votes
1
answer
178
views
Implementing a TM with FIFO Machine
I am attempting to simulate a TM on a FIFO machine. My initial approach is the following:
\begin{align*}
\text{Starting string:} & \quad \text{uabv}\rightarrow bv\#ua \\
\text{Step 1:} & \quad ...
- 21
2
votes
2
answers
134
views
Making a CFG for $L = {a^i b^j c^k d^m : i + 2j = 3k + m; i, j, k, m>= 0}$?
I am trying to construct a context-free grammar (CFG) for the following language:
$L = \{a^i b^j c^k d^m : i + 2j = 3k + m; \, i, j, k, m \geq 0\}$
So far, I've tried doing something like this:
$S =...
- 21
3
votes
1
answer
273
views
Understanding a bound for derivation length of any string in Pumping lemma for context-free languages
The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz:
Let $L$ be an ...
- 137
0
votes
1
answer
74
views
Should a PDA reject words not in language?
Let's say we want to construct the PDA for the following language:
$$L_4 = \{w_1bw_2 | w_1, w_2 \in \{a,b,c \}^* \ and \ (\#ab\in w_1) = (2 \times \#c \in w_2)\}$$
Let's consider the following PDA ...
- 111
9
votes
1
answer
438
views
Are Context-Free languages closed under XOR?
First, let's generalize the notion of XOR on strings over the ${0,1}$ alphabet. For strings of the same length, the XOR is the bitwise XOR. For strings of different lengths, we define $ \text{xor}(w, \...
- 93