Prof that exist an L regular language L1,L2,L3... are non-regular sub languages of L & L1⊆L2⊆L3...

726 Views Asked by At

proof that there is L which is regular language and there is an infinite subset of non-regular languages $L1,L2,L3 ... $(L1,L2,... different from L)

Such as $L1⊆L2⊆L3...$

which means that for every i>0 , Li ⊆ Li+1 and in addition for every i>0 $Li ⊆ L.$

from what I know non-regular languages cannot be applied by automata and is infinite. therefor, every $Li ⊆ Lj$ if $Li$ is infinite so does $Lj$.

in contrary to the assumption I must prove above.

I'm new at this field so I will appreciate for a beginner level explanation.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $u_n$ be the sequence of non-square integers: $u_1 = 2, u_2 = 3, u_3 =5$, etc. Now let $L_0 = \{a^{k^2} \mid k \geqslant 0 \}$ and, for each $n > 0$, $L_n = L_0 \cup \{u_1, \ldots, u_n\}$. Then the languages $L_n$ form an infinite chain of non-regular languages contained in the regular language $a^*$.