Prove whether the following languages are regular or non$-$regular. You may need to use the Pumping

Lemma, and you can also assume that the following languages are not regular:

LPRIME $=\{$ap : p in PRIME$\}$

L$01=\{0$n$1$n : n $>=0\}$

Lij $=\{0$i$1$j : i $<$ j$\}$

$($a$)[5$ marks$]$ The language of all integers $(\backslash$sigma $=\{0,1,...9\})$ whose length is divisible by $2$ or $3$ but

not $6.$

$($b$)[5$ marks$]$ The language L $=\{$aa$\}*\backslash$cup LPRIME

$($c$)[5$ marks$]$ The language L $=\{\backslash$sigma $0$n$1$n$\backslash$sigma $|$n $>=1\}$ where $\backslash$sigma $=\{0,1\}$ and $\backslash$sigma $$ is the set of all binary

strings.

$($d$)[5$ marks$]$ The language L $=\{\backslash$sigma in $\{$a$,$ b$,$ c$,$ d$\}$ : $|\backslash$sigma $|$a $+|\backslash$sigma $|$b $<|\backslash$sigma $|$c $+|\backslash$sigma $|$d$\}$ where $|$sigma$|$a is the

number of a$$s in $\backslash$sigma $,$ etc..

$($e$)[5$ marks$]$ The language L $=\{\backslash$sigma in $\{0,1\}$ : $|\backslash$sigma $|0=$ n$2|\backslash$sigma $|1=$ n$2,$ n $>=1\}.$ Spoiler alert: this is

not regular and requires the Pumping Lemma.

$($f$)[$Infinite Bonus marks$]$ Let L $=$ LPRIME $\backslash \{$aa$\}.$ Is the language L$=$ LL regular? Note: this

problem likely reduces to the Goldbach Conjecture, so solving it could possibly get you a million

dollars.

HINTS:$-$

Here are a couple of hints to help you with the first question of the assignment

$1$a and $1$c are both regular

$1$b and $1$d are both non$-$regular and do not need the pumping lemma; $1$e is non$-$regular and requires the pumping lemma.

Do not attempt $1$f

To show that a language is non$-$regular for $1$b and $1$d$,$ consider using the following method:

Assume the language L is regular and use this to get to a contradiction.

Use a second language that you know is regular.

Recall that if L and S are both regular, then L $[$operation$]$ S is regular for concatenation, union, Kleene$-*,$ complement, reversal, intersection, and set difference $($see the lecture on the Closure Properties$).$

Show that the resulting language after taking the $[$operation$]$ is known to be non$-$regular. This is a contradiction!

Therefore, at least one of the languages in the L $[$operation$]$ S must be non$-$regular, and since S is known to be regular, then L must be non$-$regular.

Hints: Consider using the language L$\_$odd $=($aa$)*$a for $1$b and the language L$\_$ac $=$ a$*$c$*$ for $1$d somehow.