UNIT-V UNDECIDABILITY

1 When a recursively enumerable language is said to be recursive.
2 Is it true that the language accepted by a non deterministic Turing Machine is different from recursively enumerable language?
3 When we say a problem is decidable? Give an example of undecidable problem?
4 Give two properties of recursively enumerable sets which are undecidable.
5 Is it true that complement of a recursive language is recursive? Justify your answer.
6 When a language is said to be recursive or recursively enumerable?
7 When a language is said to be recursive? Is it true that every regular set is not recursive?
8 When a problem is said to be decidable or undecidable? Give an example of an undecidable.
9 What do you mean by universal Turing Machine?
10.When a problem is said to be undecidable? Give an example of an decidable problem.
11.Show that the union of recursive language is recursive.

12.Show that the union of two recursively enumerable languages is recursively enumerable.
13.What is undecidability problem?
14.Show that the following problem is undecidable.“Given two CFG’s G1 and G2, is L(G1)∩L(G2)=Φ?”.
15.Define Ld.
16.Define recursively enumerable language.
17.Give an example for a non recursively enumerable language.
1 Differentiate between recursive and recursively enumerable languages.
2 Mention any two undecidability properties for recursively enumerable language.
21.Define Diagonal languages.
22.Give an example for an undecidable problem.