Turing Machine and Recursive Functions

Question 1

The intersection of two regular languages is regular.
T or F ?

Answer 1

TRUE

Question 2

The intersection of two recursive languages is recursive.
T or F ?

Answer 2

TRUE

Question 3

The intersection of two recursively enumerable languages is recursively enumerable.
T or F ?

Answer 3

TRUE

Question 4

The intersection of two Context free languages is Context-free.
T or F ?

Answer 4

FALSE.
CFL is not closed under intersection.

Question 5

The set of all recursively enumerable languages is closed under complementation.
T or F ?

Answer 5

FALSE.

Question 6

The set of all recursively enumerable languages is closed under intersection.
T or F ?

Answer 6

TRUE.

Question 7

The set of all recursively enumerable languages is a subset of the set of all recursive languages.
T or F ?

Answer 7

FALSE.
recursive is subset of recursively enumerable languages. not vice versa.

Question 8

The set of all recursively enumerable languages is an uncountable set.
T or F ?

Answer 8

FALSE.
Every Recursively enumerable language have a TM, and set of all TM’s is countable. Therefore, set of all Recursively enumerable languages is countable.

Question 9

Set of all syntactically valid C programs are countable.
T or F ?

Answer 9

TRUE
Set of all syntactically valid C programs. We can make a one to one equivalence for all valid C programs and all valid TM encodings. Since, the set of all valid TM encodings is countable, it means that the set of all syntactically valid C programs is also countable.

Question 10

Set of all languages over the alphabet {a,b} is countable.
T or F ?

Answer 10

FALSE
Set of all languages over the alphabet {a,b}. It is (2^∑⋆) which is uncountable as the power set of an infinite set is uncountable.

Question 11

Set of all non-regular languages over the alphabet {0, 1}.
T or F ?

Answer 11

FALSE.
We know that, set of all languages is uncountable and set of all Regular Languages is countable. So, the set of all non-regular languages should be uncountable as union of two countable sets cannot make an uncountable set.

Question 12

If a language L and its complement L’ are both recursively enumerable, then L must be recursive.
T or F ?

Answer 12

TRUE

Question 13

Complement of a context-free language must be recursive.
T or F ?

Answer 13

Complement of a context-free language may or maynot be CFL but since every CFL is CSL, and complement of CSL is always CSL.
So, Complement of a context-free language must be CSL, hence, must be recursive

Question 14

Turing decidable language mean Recursively Enumerable language and Turing recognizable language mean recursive language.
T or F ?

Answer 14

FALSE
Turing decidable language mean Recursive language and Turing recognizable language mean recursive enumerable language.

Question 15

Turing machines can be used to recognize all the languages.
T or F ?

Answer 15

TRUE