Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
Your language isn't context free.
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.
