1
$\begingroup$

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$.

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

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.