2
$\begingroup$

Without using pumping lemma for deterministic context-free languages I need to prove that the language $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic.

Someone suggested me that I could try to deduce that if it were deterministic then the language $\{a^nb^nc^n\colon n\ge0\}$ would be context-free. But I don't really see how to use it.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ What kind of argument are you allowed to use? $\endgroup$ – Yuval Filmus Jan 23 '16 at 17:35
  • $\begingroup$ @Yuval Filmus just some argument that does not use pumping lemma $\endgroup$ – Rodrigo Jan 23 '16 at 17:41
  • 2
    $\begingroup$ Well, you can include a proof of the pumping lemma and then you're fine. $\endgroup$ – Yuval Filmus Jan 23 '16 at 17:44
  • 1
    $\begingroup$ Take a look at the technique suggested here: cs.stackexchange.com/a/38476/683. $\endgroup$ – Yuval Filmus Jan 23 '16 at 17:55
  • $\begingroup$ Once you have a proof, please answer your own question. $\endgroup$ – Yuval Filmus Jan 24 '16 at 21:33

Your Answer

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

Browse other questions tagged or ask your own question.