Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?

Related MCQs

• Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L’ (complement of L) also context-free? 3) If L is a regular language, then is L’ also regular? 4) If L is a recursive language, then, is L’ also recursive?
• Consider the following decision problems: (P1) Does a given finite state machine accept a given string (P2) Does a given context free grammar generate an infinite number of stings Which of the following statements is true?
• Consider the following two problems on undirected graphs: α: Given G(V,E), does G have an independent set of size |v|—4? β: Given G(V,E), does G have an independent set of size 5? Which one of the following is TRUE?
• Which of the following are decidable ? 1. whether the intersection of two regular language is infinite. 2. whether a give context free language is regular 3. whether two push down automata accept the same language. 4. whether a given grammar is context free
• Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free
• Consider the following expression grammar. The seman-tic rules for expression calculation are stated next to each grammar production. E → number E.val = number. val | E '+' E E(1).val = E(2).val + E(3).val | E '×' E E(1).val = E(2).val × E(3).val The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
• Consider the following grammar. S -> S * E S -> E E -> F + E E -> F F -> id Consider the following LR(0) items corresponding to the grammar above. (i) S -> S * .E (ii) E -> F. + E (iii) E -> F + .E Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?
• Consider the grammar defined by the following production rules, with two operators ∗ and + S --> T * P T --> U | T * U P --> Q + P | Q Q --> Id U --> Id Which one of the following is TRUE?
• Consider the languages L1={0^{i}1^{j}|i != j}, L2={0^{i}1^{j}|i = j}, L3 = {0^{i}1^{j}|i = 2j+1}, L4 = {0^{i}1^{j}|i != 2j}. Which one of the following statements is true?
• Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE?