1. True or False. T true, F false, and O- open, meaning that the answer is not known to science at this time. In the questions below. P and "NP denote P-TIME and 'F.-TIME, respectively Every language generated by an unambiguous context-free grammar is accepted by some DPDA b) The lan guage sa"b'c"d n 20 is recursive Let L be the language over a, b, c consisting of all strings which have more a's than b's and more b's than c's. There is some PDA that accepts L (d) The language sa"bc n 20 is in the class P. There exists a polynomial time algorithm which finds the factors of any positive integer, where the input is given as a binary numeral (f) The lan (g) guage {a"| n > 0} is context-free The language fa"b*c n 2 0 is context-free. The language {aw#1 j = i + k} is context-free The intersection of any regular languages with any context-free language is context-free If L is a context-free language over an alphabet with just one symbol, then L is regular P = NP. There is a deterministic parser for any context-free grammar The Boolean Circuit Problem is in P. (k)- The Boolean Circuit Problem is in Nc. The set of strings that your high school algebra teacher would accept as legitimate expressions is a context-free language (p) There exists a polynomial time algorithm which finds the factors of any positive integer exists where the input is given as a binary numeral The language consisting of all strings over [a, by which have more a's than b's is context-free Every context-free language is in P Every language accepted by a non-deterministic machine is accepted by some deterministic (q) machine The problem of whether two given context-free grammars generate the same language is decidable The problem of whether a given string is generated by a given context-free grammar is decidable Every bounded function is recursive There exists a mathematical proposition that can be neither proved nor disproved There is a non-recursive function which grows faster than any recursive function. There exists a machine' that runs forever and outputs the string of decimal digits of (the well-known ratio of the circumference of a circle to its diameter) (z)For every real number r, there exists a machine that runs forever and outputs the string of decimal digits of x 1. True or False. T true, F false, and O- open, meaning that the answer is not known to science at this time. In the questions below. P and "NP denote P-TIME and 'F.-TIME, respectively Every language generated by an unambiguous context-free grammar is accepted by some DPDA b) The lan guage sa"b'c"d n 20 is recursive Let L be the language over a, b, c consisting of all strings which have more a's than b's and more b's than c's. There is some PDA that accepts L (d) The language sa"bc n 20 is in the class P. There exists a polynomial time algorithm which finds the factors of any positive integer, where the input is given as a binary numeral (f) The lan (g) guage {a"| n > 0} is context-free The language fa"b*c n 2 0 is context-free. The language {aw#1 j = i + k} is context-free The intersection of any regular languages with any context-free language is context-free If L is a context-free language over an alphabet with just one symbol, then L is regular P = NP. There is a deterministic parser for any context-free grammar The Boolean Circuit Problem is in P. (k)- The Boolean Circuit Problem is in Nc. The set of strings that your high school algebra teacher would accept as legitimate expressions is a context-free language (p) There exists a polynomial time algorithm which finds the factors of any positive integer exists where the input is given as a binary numeral The language consisting of all strings over [a, by which have more a's than b's is context-free Every context-free language is in P Every language accepted by a non-deterministic machine is accepted by some deterministic (q) machine The problem of whether two given context-free grammars generate the same language is decidable The problem of whether a given string is generated by a given context-free grammar is decidable Every bounded function is recursive There exists a mathematical proposition that can be neither proved nor disproved There is a non-recursive function which grows faster than any recursive function. There exists a machine' that runs forever and outputs the string of decimal digits of (the well-known ratio of the circumference of a circle to its diameter) (z)For every real number r, there exists a machine that runs forever and outputs the string of decimal digits of x
