1
$\begingroup$

I hope you could help me as you have done before (thanks again)

In a previous exam I saw this question; it is asked to identify if the language is Regular, CFL or Non CFL.

Question Asked

In my opinion this language is CFL... but, again my opinion is not good ! :/

I have think about the problem as followed :

For the first part (before the intersection) the language is a^i b^j c^k | i != j or i != k or k != j. This is a CFL since it's the union of multiple CFL languages. Am I right ? (Thanks Draconis)

Then for the second part, this is also a CFL since I could easily write a CFG of it or a PDA.

Then the intersection, it means that now the language is :

{a^i b^j c^k | (i != j or i != k or k != j) and ( i = j ) }
==> {a^i b^j c^k | i = j != k} <=== this is probably my mistake. (I don't understand why)

But my result is a CFL... unfortunately, my result is wrong.

Please help me to understant, my exam is soon and looking at my answer it doesn't look good...

Thnaks a lot in advance !

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael ♦
    Mar 6, 2019 at 8:04
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael ♦
    Mar 6, 2019 at 8:04
  • 2
    $\begingroup$ You seem to try to re-formulate the language using some form of ad-hoc algebraic transformations. That's not a solid approach unless you use closure properties and are in general very, very careful. We have reference questions that explain techniques for either direction for exercises like this; you may want to check them out. $\endgroup$
    – Raphael ♦
    Mar 6, 2019 at 8:07
  • $\begingroup$ As for your question, I don't understand: "But my result is a CFL... unfortunately, my result is wrong." -- What do you mean? You came to the conclusion that the language is what but think that's wrong why? (Either way, you didn't give a proof of anything.) $\endgroup$
    – Raphael ♦
    Mar 6, 2019 at 8:08
  • $\begingroup$ Use the same techniques found in cs.stackexchange.com/q/33228/755. $\endgroup$
    – D.W. ♦
    Mar 7, 2019 at 20:58

0

Reset to default

Browse other questions tagged or ask your own question.