# Recent questions tagged theory-of-computation

1 vote
1
Consider $L=L_1 \cap L_2$ where $L_1 = \{ 0^m 1^m 20^n 1^n \mid m,n \geq 0 \}$ $L_2 = \{0^m1^n2^k \mid m,n,k \geq 0 \}$ Then, the language $L$ is Recursively enumerable but not context free Regular Context free but not regular Not recursive
2
Let $L_1$ and $L_2$ be languages over $\Sigma = \{a,b\}$ represented by the regular expressions $(a^* +b)^*$ and $(a+b)^*$ respectively. Which of the following is true with respect to the two languages? $L_1 \subset L_2$ $L_2 \subset L_1$ $L_1 = L_2$ $L_1 \cap L_2 = \phi$
1 vote
3
Which of the following statements is true? The union of two context free languages is context free The intersection of two context free languages is context free The complement of a context free language is context free If a language is context free, it can always be accepted by a deterministic pushdown automaton
1 vote
4
Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems: Is $L(G_1)=L(G_2)$? Is $L(G_2) \leq L(G_1)$? Is $L(G_1)=R$? Which of the problems are undecidable? Choose the correct answer from the options given below: $(a)$ only $(b)$ only $(a)$ and $(b)$ only $(a)$, $(b)$ and $(c)$
5
Consider the following languages: $L_1=\{a^{\grave{z}^z} \mid \grave{Z} \text{ is an integer} \}$ $L_2=\{a^{z\grave{z}} \mid \grave{Z} \geq 0\}$ $L_3=\{ \omega \omega \mid \omega \epsilon \{a,b\}^*\}$ Which of the languages is(are) regular? Choose the correct answer from the options given below: $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_1$ only $L_2$ only
6
Which of the following grammars is(are) ambiguous? $s \rightarrow ss \mid asb \mid bsa \mid \lambda$ $s \rightarrow asbs \mid bsas \mid \lambda$ $s \rightarrow aAB \\ A \rightarrow bBb \\ B \rightarrow A \mid \lambda \text{ where } \lambda \text{ denotes empty string}$ Choose the correct answer from the options given below: $(a)$ and $(c)$ only $(b)$ only $(b)$ and $(c)$ only $(a)$ and $(b)$ only
7
Match $\text{List I}$ with $\text{List II}$ $L_R:$ Regular language, $LCF$: Context free language $L_{REC}:$ Recursive langauge, $L_{RE}$ ... options given below: $A-II, B-III, C-I$ $A-III, B-I, C-II$ $A-I, B-II, C-III$ $A-II, B-I, C-III$
8
Consider the following regular expressions: $r=a(b+a)^*$ $s=a(a+b)^*$ $t=aa^*b$ Choose the correct answer from the options given below based on the relation between the languages generated by the regular expressions above: $L(r) \subseteq L(s) \subseteq L(t)$ $L(r) \supseteq L(s) \supseteq L(t)$ $L(r) \supseteq L(t) \supseteq L(s)$ $L(s) \supseteq L(t) \supseteq L(r)$
9
Given below are two statements: Statement $I$: The problem Is $L_1 \wedge L_2 = \phi$? is undecidable for context sensitive languages $L_1$ and $L_2$ Statement $II$: The problem Is $W \in L$? is decidable for context sensitive language $L$. (where $W$ is ... $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
10
If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called decidable undecidable interpretive non-deterministic
11
The defining language for developing a formalism in which language definitions can be stated, is called syntactic meta language decidable language intermediate language high level language
12
Regular expression $(a \mid b)(a \mid b)$ denotes the set $\{a,b,ab,aa\}$ $\{a,b,ba,bb\}$ $\{a,b\}$ $\{aa,ab,ba,bb\}$
13
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens
1 vote
14
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ Only $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
15
A language $L$ for which there exists a $TM\;\;’T’,$ that accepts every word in $L$ and either rejects or loops for every word that is not in $L,$ is said to be Recursive Recursively enumerable NP-HARD None of the above
1 vote
16
The logic of pumping lemma is a good example of the pigeon-hole principle the divide and conquer technique recursion iteration
17
Which of the following definitions generates the same languages as $L,$ where $L = \{x^{n}y^{n},n \geq 1\}$ $E \rightarrow xEy \mid xy$ $xy \mid x^{+}xyy^{+}$ $x^{+}y^{+}$ $(i)$ $(i)$ and $(ii)$ only $(ii)$ and $(iii)$ only $(ii)$ only
18
Choose the correct statements. A total recursive function is also a partial recursive function A partial recursive function is also a total recursive function A partial recursive function is also a primitive recursive function None of the above
1 vote
19
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$ $DFA$ $NFA - 1$ All of the options
20
Complement of a $DFA$ can be obtained by : making starting state as final state. make final as a starting state. making final states non-final and non-final as final. None of the options
21
Concatenation Operation refers to which of the following set operations : Union Dot Kleene None of the options
22
Which of the following statements is true ? Melay and Moore machines are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.
1 vote
23
If $L1$ and $L2$ are regular sets then intersection of these two will be : Regular Non Regular Recursive Non Recursive
24
Let $P, Q, R$ be a regular expression over $\Sigma$. If $P$ does not contain null string, then $R=Q+RP$ has a unique solution ___________ . $Q^{*}P$ $QP^{*}$ $Q^{*}P^{*}$ $\left ( P^{*}O^{*} \right)^{*}$
A finite automaton accepts which type of language : Type $0$ Type $1$ Type $2$ Type $3$
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
What is the relation between $DFA$ and $NFA$ on the basis of computational power ? $DFA$ > $NFA$ $NFA$ > $DFA$ Equal Can't be said