GATE CSE 1992 | Question: 16

Question

Which of the following three statements are true? Prove your answer.

1. The union of two recursive languages is recursive.
2. The language $\{O^n \mid n\text{ is a prime} \}$ is not regular.
3. Regular languages are closed under infinite union.

Comments

$\color{red}{\text{Find Detailed Video Solution Below}}$ $\color{BLACK}{\text{  , With Proof of each statement:}}$

https://youtu.be/QLYJXbQsyaI

---

gateoverflow.in/?qa=blob&qa_blobid=8929616163903734815

---

Of the three, Statements 1 and 2 are TRUE, while Statement 3 is FALSE.

Statement 1: The union of two recursive languages is recursive. (TRUE)

Proof:

Let $L_1$ and $L_2$ be two recursive languages. By definition, a language is recursive if and only if there exists a Total Turing Machine (a Decider) that halts for every input, outputting Accept if the string is in the language and Reject if it is not.

Let $M_1$ be the decider for $L_1$, and $M_2$ be the decider for $L_2$. We can construct a new Turing Machine $M$ to decide the union language $L_1 \cup L_2$ as follows:

On input string w:
1. Run M1 on input w.
2. If M1 accepts, ACCEPT.
3. If M1 rejects, run M2 on input w.
4. If M2 accepts, ACCEPT.
5. If M2 rejects, REJECT.

Now for the other two options, 

(2) is classois non regular language can be proved by pumping lemma

(3) is false take the example of simple non regular language a^n b^n | n>0 here the individual elements like ab, aabb, aaabbb etc are regular languages but union of them is not considered regular as the above language is CFL 

Answer 1

1. True. Recursive languages are closed under union.
2. True. The language is context sensitive (we can write a C code right?) but not context-free (can be proved using pumping lemma for context-free languages).
3. False. Regular languages are closed under finite union but not under infinite union. 

Comments

@Pranavpurkar Finite is always regular. All of L1={a1b1}, L2={a2b2}, L3=(a3b3}... are finite languages, hence are regular. @meghna ‘s example is correct. 

Link

---

Abhrajyoti00

ohh i think i got my mistake.

the mistake i did was , as she considered  L1 = $a^{1}b^{1}$   so i got confused with Ln (it would be better if some other variable was taken)

as then Ln = $a^{n}b^{n}$  but here  n is some constant , that’s why finite.

Thanks buddy!

---

{01} U {0011} U {000111} U {00001111}...............................infinitely do
language is L={0'n1'n | n>0}
here all languages are regular but there infinite union makes in non regular

Answer 2

here is the answer for it. 

Answer 3

Of the three, Statements 1 and 2 are TRUE, while Statement 3 is FALSE.

Statement 1: The union of two recursive languages is recursive. (TRUE)

Proof:

Let $L_1$ and $L_2$ be two recursive languages. By definition, a language is recursive if and only if there exists a Total Turing Machine (a Decider) that halts for every input, outputting Accept if the string is in the language and Reject if it is not.

Let $M_1$ be the decider for $L_1$, and $M_2$ be the decider for $L_2$. We can construct a new Turing Machine $M$ to decide the union language $L_1 \cup L_2$ as follows:

On input string w:
1. Run M1 on input w.
2. If M1 accepts, ACCEPT.
3. If M1 rejects, run M2 on input w.
4. If M2 accepts, ACCEPT.
5. If M2 rejects, REJECT.

Now for the other two options, 

(2) is classois non regular language can be proved by pumping lemma

(3) is false take the example of simple non regular language a^n b^n | n>0 here the individual elements like ab, aabb, aaabbb etc are regular languages but union of them is not considered regular as the above language is CFL