1
$\begingroup$

I am asking this question here, because I am not allowed to comment on the thread that I am actually interested in, but maybe someone can still help me?

I alredy found an anwser to the Problem above (in the post linked to this question), but I still don't understand, why I can't just use that one case $s = \alpha \beta^p \gamma^p$. I can show for that case, that it doesn't fit the pumping lemma for regular languages. Isn't the point of condratiction, that I have to find just one case that doesn't fit the hypothesis?

Actually I am not even supposed to use the pumping lemma, but the definitions of closure for regular languages. And that is where I started with $(i=1) \Rightarrow (j=k) = i \neq 1 \vee j = k$. And then I wanted to use the properties of closure, like in the first anwser in the post I linked. (I was also thinkg of using a regular expression? It seemed easier) But if I can't just find that mentioned one word to proove the language not regular (without the PL)? I am confused. I hope it makes sense. I am genuinely interested in understanding this problem.

Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

$\endgroup$
2
  • $\begingroup$ Some background is missing here. In the second paragraph, you're asking why you can't just you the single case $s = \alpha\beta^p\gamma^p$. However, I have no idea what any of these symbols are. $\endgroup$ – Yuval Filmus May 16 '20 at 10:21
  • $\begingroup$ @Nienna Can you edit the question to show $s=\alpha\beta^p\gamma^p$ does not fii the pumping lemma for regular languages? (I might be wrong, but I will bet the pumping lemma you referred to is the most common version in various textbooks.) $\endgroup$ – John L. May 17 '20 at 6:09

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.