3
$\begingroup$

We know that $L=\{0^i 1^{j^2}|i> 0,j\ge 0\} $ is irregular (by the Pumping Lemma), we have to use it to prove two things:

  1. $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular.
  2. $L_1$ is making all the three conditions (I don't know the exactly word at English for this...) of the Pumping Lemma.

For the first one - how do I prove it by the Pumping Lemma?

For the second - I have no idea and I'd like to get ant help!
(Because I can choose any word that I want, and I need to prove it for all the words in $L$).

Thank you!

$\endgroup$
3
  • 1
    $\begingroup$ regular + irregular = irregular, right? Wrong. For example, $\Sigma^* \cup \mathrm{anything} = \Sigma^*$. $\endgroup$ Dec 5 '15 at 15:47
  • $\begingroup$ Right! thank you! I'll use the Pumping Lemma! $\endgroup$
    – stud1
    Dec 5 '15 at 15:52
  • $\begingroup$ ad 2: "$L_1$ fulfills all the three conditions of the Pumping Lemma" -- if that is true, you can not use the Pumping Lemma to show that $L_1$ is irregular! $\endgroup$
    – Raphael
    Dec 5 '15 at 21:01
2
$\begingroup$

You don't need to use the pumping lemma to prove that $L_1$ is irregular. You can also make use of the closure properties of the regular languages.

We know that regular languages are closed under intersection. That is, if $L_1$ and $L_2$ are regular languages then $L_3 = L_1\cap L_2$ is also a regular language.

A nice way to prove that a language is irregular is to assume that it is regular and reach a contradiction using the closure properties of the regular languages.

For example consider the language $L_p = \{1^p: p\text{ is prime}\}$ we know that this is an irregular language. Let's consider $L_q = L_p \cup 0^*$. How can we prove that this language is irregular?

Let us assume for the purpose of contradiction that $L_q$ is regular, hence $L_q\cap 1^*$ is also a regular language since $1^*$ is a regular language. But wait.. The intersection is $L_p$ (the primes) which is not a regular language. Contradiction. So $L_q$ is irregular.

Your problem can be solved along the same lines.

$\endgroup$
1
  • $\begingroup$ So if I'm understand you right: 1. I can just take a word that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\}$ doesn't accept. 2. I will will take a word from $1^*$ and this the way I'll show that the $L_1$ making the pumping Lemma conditions? Thanks! $\endgroup$
    – stud1
    Dec 6 '15 at 9:15

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