Ask 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.

+4
Answers (1)
  1. 12 November, 22:58
    0
    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.
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 { ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers