decidablity

Question

$L1 = a^{p}$ | p is prime .

$L2 = a^{p}$| p is odd .

state the decidability of below statement. 

1) $L1 \cup L2$  is regular

2) regular expression of   $L1 \cup L2$  is $a(aa)^*$

Answer 1

L1={aa,aaa,aaaaa,.....}

L2={a,aaa,aaaaa,......}

$L1\cup L2$={a,aa,aaa,aaaaa,..........}

1)it is REGULAR,SO IT IS DECIDABLE.

2)REGULAR EXPRESSION IS =aa+a$(aa)^{*}$.

Comments

l1 = CSL

l2 = reg .

---

tell my mistake ?

---

@ kunal L2 is not csl it regular.

so csl U reg =csl.//it is sometimes regular also.

Answer 2

L1 : Not regular .. as prime numbers in power

L2 : It's Regular language and regular expression : a(aa)*

So for L1 U L2 = Recursive U Regular = Recursive U Recursive = Recursive Language [Recursive language closed under Union]

But L1 U L2 is nothing but set of prime powers or odd enumerations [but except 2 a prime no. is odd always] --> so L1 U L2 = {aa} U {a(aa)*}..Hence Regular.

But how can be " regular expression of   L₁ U L₂  is a(aa)^* " --> asked for decidability, it should be true/false statement

As L1UL2 = {aa} U {a(aa)*}  [ Hence statement is false ].

Comments

a^9 is there is the language L1 U L2.check once

---

DCFL U REG=DCFL.//some times it is regular

i already gave an example.

---

Yeah Correct for L1 U L2 expression will be {aa} U {a(aa)*} 

And for second I have also said same thing what you are saying ... see "always DCFL but not always regular".