# Is the following language a Deterministic Context-Free Language?

I tried to show the following language is DCFL (Deterministic Context-Free Language):

$$L=\{wo^n\mid w\in\{a,b\}^*, n_a(w)=n_b(w)=n, |w|=2n\}$$

I tried to show that $$L$$ has a DPDA (Deterministic Push-Down Automota), but I get stuck to find a DPDA for $$L$$.

• Since $L \cap a^*b^*o^* = \{a^n b^n c^n\}$, your language isn't even context-free. Jul 31, 2021 at 13:43

Assume $$L$$ is context-free. Then by the pumping lemma for context-free languages we have a constant $$n_L$$ such that for every $$z \in L$$ with $$|z| \geq n_L$$ there exists a decomposition $$z = uvwxy$$ with properties (i) $$|vx| \geq 1$$ (ii) $$|vwx| \leq n_L$$ and (iii) $$\{uv^iwx^iy \mid i \in \mathbb{N}\} \subseteq L$$
Let $$z = a^{n_L}b^{n_L}o^{n_L}$$.
Clearly for every decomposition $$z = uvwxy$$ satisfying (i) and (ii), $$vwx$$ contains at most two different characters. Then, however, $$uv^2wx^2y$$ cannot have the same amount of $$o$$'s, $$a$$'s and $$b$$'s because of (i). This leads to a contradiction to our assumption and $$L$$ isn't context-free.
Your language isn't context-free. If we intersect it with the regular language $$a^*b^*o^*$$, we get one of the prototypical non-context-free languages, $$\{a^nb^no^n : n \in \mathbb{N}\}$$. Since the context-free languages are closed under intersection with a regular language, this shows that your original language isn't context-free.