349 views
0 votes
0 votes
Someone explain...

L1 ={a^p / p is prime}
L2 ={a^p / p is odd}
S1 : L1 ∪ L2 is regular
S2 : Regular expression of L1 ∪ L2 is a(aa)*

A) S1 is decidable(correct)
S2 is undecidable(not correct)
B) S1,S2 is decidable
C) S1 , S2 is undecidable
D) None

2 Answers

Best answer
1 votes
1 votes

L1= {a2, a3, a5, a7, a11, a13 ....}

L2= {a1, a3, a5, a7, a9 ....}

L1 U L2 = {a1,a2,a3,a5,a7,a9,.....} = {all odd no of a and a2}

So S1 is decidable

In regex a(aa)*  we can't find a2

So S2 is undecidable.

selected by
0 votes
0 votes
L1 is Recursive
L2 is Regular

Recursive  ∪ Regular is Recursive .

Since L1  ∪ L2 is Recursive .
hence  No regular Expression can be formed .

No related questions found