Closure of Languages, regular, decidable: Also computable numbers! Is a countabl

Question

Closure of Languages, regular, decidable: Also computable numbers!

Is a countable union of regular languages necessarily regular? Decidable? Is a countable union of decidable languages necessarily decidable? Are the decidable languages closed Kleene closure? Concatenation? Union? Complementation? Are the non-decidable languages closed Kleene closure? Concatenation? Union? Are the non-finitely-describable languages closed under concatenation? Kleene closure? Complementation? Union? Can an non-computable number be rational? Must an irrational number be non-computable?

Explanation / Answer

1)
YES, the countable union of regular languages are regular. The idea is to take two NFAs, N1 and N2 say for 2 regular languages A1 and A2, and combine them into one new NFA, N. Machine N must accept its input if either N1 or N2 accepts this input. The new machine has a new start state that branches to the start states of the old machines with E arrows. In this way the new machine nondeterministically guesses which of the two machines accepts the input. If one of them accepts the input,N will accept it, too.

YES. Say for any 2 decidable(turing decidable) languages L1 and L2,let M1,M2 be the turing machines(TM's) that recognize them.We construct a TM M' that recognizes the union of M1 and M2. On input "w" run M1 and M2 alternatively on w step by step.If both accept then accept, and if both halt and reject then reject.If any of M1 and M2 accepts 'w' then M' will accept 'w' then the accepting TM will come to accepting state after finite number of steps.

2)
YES there can be decidable languages that are closed under complementation,kleene star,intersection

consider kleene star

construct a machine M' given a machine M that accepts a decidable language L. Now M' on input of w
cuts the inut string w into concatenated parts of w1.w2.w3.........wn and then run M on all w(i) and id M accepts all of them M' accepts and if M halts and rejects any one of them then M' will halt and reject.

No.there cannot be non-decidable languages that are closed under kleene star.We can't construct a TM for them

3)
YES there can be non-finitely desrcibable languages that are closed under the given set of operations
there are many languages that satisfy the pumping lemma

4)NO. there can't be a non-computable number which is rational. all the rational numbers all computable.
NO. irrational numbers can be computable.
example :- sqrt(2) is a computable number

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.