edited by
8,517 views
33 votes
33 votes

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.
edited by

1 Answer

Best answer
36 votes
36 votes
  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. 
edited by

Related questions

40 votes
40 votes
4 answers
1
Kathleen asked Sep 13, 2014
7,108 views
If $G$ is a group of even order, then show that there exists an element $a≠e$, the identity in $G$, such that $a^2 = e$.
26 votes
26 votes
3 answers
4
go_editor asked Apr 24, 2016
3,564 views
Suppose we have a database consisting of the following three relations:$$\begin{array}{|c|c|} \hline \text {FREQUENTS} & \text {(CUSTOMER, HOTEL)} \\\hline \text {SERVES}...