Question

Determine whether each of the following is True or False. Justify your answer. (a) Every infinite set is countable. (b) If N is the set { hGi : G is CFG that does NOT generate all strings }, then N is r.e. (c) It is undecidable to determine whether an NFA accepts its own encoding. (d) If a language L is context-sensitive, then there is a Printer-TM that prints out L in order.

Answer 1

a. false

b. false

c. false

d. true

Step-by-step explanation:

(a) False, this is because the set of all real numbers are example of infinite uncountable set.

(b) False, this is because it is undecidable problem to test if a grammar G generates all possible strings over the alphabet and hence to check if set N containing all such CFG is not even recursive-enumerable.

(c) False, this is because there is decidable Turing machine to test if a NFA accepts the input string which includes it's own encoding.

(d) True, this is becsuse it's possible for context-sensative language.