Theory of Computation
Q151.
Nobody knows yet if P = NP. Consider the language L defined as follows : L=\left\{\begin{matrix} (0+1)^{*}\; \; \; if P=NP\\ \Phi \; \; otherwise \end{matrix}\right. Which of the following statements is true ?Q152.
Let L \subseteq \{0,1\}^* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k states?Q154.
Let P be a regular language and Q be a context free language such that Q \subseteq P. (For example, let P be the language represented by the regular expression p*q* and Q be \{p^{n}q^{n}|n\in N\} Then which of the following is ALWAYS regular?Q155.
For \Sigma =\{a,b\}, let us consider the regular language L=\{x|x=a^{2+3k} \; or \; x=b^{10+12k}, k\geq 0\}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?Q156.
If L is a regular language over \Sigma =\{a,b\}, which one of the following languages is NOT regular ?Q157.
Let L \subseteq \Sigma^* where \Sigma = \left\{a,b \right\}. Which of the following is true?Q158.
If L_{1}=\{a^{n}|n\geq 0\} and L_{2}=\{b^{n}|n\geq 0 \}, Consider (I) L_{1}\cdot L_{2} is a regular language (II) L_{1} \cdot L_{2}= \{a^{n}b^{n}|n \geq 0\} Which one of the following is CORRECT?Q159.
Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the following choices is correct?Q160.
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?