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.

Question

Computers & Technology

Dania

21 June, 14:57

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.

+1

Answers (1)

Know the Answer?

Daniel Cowan · Answer 1

a. false

b. false

c. false

d. true

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.