# Recent questions and answers in Theory of Computation

1
Consider the following languages: $L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$ $L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$ Which one of the following is TRUE? Both $L_{1}$ and $L_{2}$ are context-free. $L_{1}$ is context-free while $L_{2}$ is not context-free. $L_{2}$ is context-free while $L_{1}$ is not context-free. Neither $L_{1}$ nor $L_{2}$ is context-free.
2
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ ... be simulated for at least $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.
3
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$ $L$ is RE but $L'$ is not RE Both $L$ and $L'$ are RE $L$ is not RE but $L'$ is RE Both $L$ and $L'$ are not RE
4
Let $L=\{0^n1^n|n\ge 0\}$ be a context free language. Which of the following is correct? $\overline L$ is context free and $L^k$ is not context free for any $k\ge1$ $\overline L$ is not context free and $L^k$ is context free for any $k\ge1$ Both $\overline L$ and $L^k$ for any $k\ge1$ are context free Both $\overline L$ and $L^k$ for any $k\ge1$ are not context free
5
Which of the following regular expressions describes the language over$\{0, 1\}$ consisting of strings that contain exactly two $1$'s? $(0 + 1)^ * \ 11(0 + 1) ^*$ $0 ^* \ 110 ^*$ $0 ^* 10 ^* 10 ^*$ $(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^*$
6
Which of the following are regular sets? $\left\{a^nb^{2m} \mid n \geq 0, m \geq 0 \right\}$ $\left\{a^nb^m \mid n =2m \right\}$ $\left\{a^nb^m \mid n \neq m \right\}$ $\left\{xcy \mid x, y, \in \left\{a, b\right\} ^* \right\}$ I and IV only I and III only I only IV only
1 vote
7
Every cfg may not have equivalent pda T/F
8
Is the language $L=\left \{ (0^{n}1^{n})^{*} |n\geq 0 \right \}$ is DCFL ?
9
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)$
10
$L_1$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots .$ Define another language $L_2$ over $\Sigma \cup \left\{\text{#}\right\}$ ... $S_1$ is true but $S_2$ is not necessarily true $S_2$ is true but $S_1$ is not necessarily true Neither is necessarily true
11
Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string). $(00)^ * (\varepsilon +0)$ $(00)^*$ $0^*$ $0(00)^*$ (i) and (ii) (ii) and (iii) (i) and (iii) (iii) and (iv)
12
Let $M=(K, Σ, \sigma, s, F)$ be a finite state automaton, where $K = \{A, B\}, Σ = \{a, b\}, s = A, F = \{B\},$ $\sigma(A, a) = A, \sigma(A, b) = B, \sigma(B, a) = B \text{ and} \ \sigma(B, b) = A$ A grammar to generate the language accepted by $M$ ... $\{A → bB, A → aB, B → aA, B → bA, B → \epsilon)$ $\{A → aA, A → bA, B → aB, B → bA, A → \epsilon)$
13
Which of the following set can be recognized by a Deterministic Finite state Automaton? The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binary The numbers $1, 2, 4, 8,\dots 2^n, \dots$ written in unary The set of binary string in which the number of zeros is the same as the number of ones. The set $\{1, 101, 11011, 1110111, \dots\}$
14
Whether the given languages are recursive, recursively enumerable or non RE 1) $L = \left \{ <M> | <M> \ accepts \ all \ strings \ of \ length \ at \ most \ 5 \right \}$ 2) $L = \left \{ <M> | <M> \ accepts \ strings \ of \ length \ at \ most \ 5 \right \}$
1 vote
15
Given two deterministic CFG G$_1$ and G$_2$, is L( G$_1$ ) = L( G$_2$ ) ?
16
Let G be a grammar in CFG and Let W1 and W2 is element of G such that |w1| = |w2| then which of the following is true? A. Any derivation of W1 has exactly the same number of steps as any derivation of W2 B. Different derivation have different length C.Some derivation of W1 may be shorter that derivation of W2 D. None of the options
1 vote
17
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
18
for 1. given any two specific numbers 2. any two arbitrary numbers
19
Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then converting it to regular expression?
20
A minimal DFA diagram for the language A = {w| w contains at least one 1 and an even number of 0s follow the last 1}?
1 vote
21
Does the statement given below is true? If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.
22
Consider the regular grammar: $S \rightarrow Xa \mid Ya$ $X \rightarrow Za$ $Z \rightarrow Sa \mid \epsilon$ $Y \rightarrow Wa$ $W \rightarrow Sa$ where $S$ is the starting symbol, the set of terminals is $\{a\}$ ... deterministic finite automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA? $2$ $3$ $4$ $5$
23
Consider the following languages over the alphabet $\sum = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}|m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}|m,n \geq 0 \right \}$. Which of the following are context-free languages? $L_{1} \cup L_{2}$ $L_{1} \cap L_{2}$ I only II only I and II Neither I nor II
24
Let $L$ be the language represented by the regular expression $\Sigma^*0011\Sigma^*$ where $\Sigma = \{0, 1\}$. What is the minimum number of states in a DFA that recognizes $\bar{L}$ (complement of $L$)? $4$ $5$ $6$ $8$
25
Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ is always regular never regular always a deterministic context-free language always a context-free language
26
Context-free languages and regular languages are both closed under the operation (s) of : Union Intersection Concatenation Complementation
27
The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.
28
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$
29
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
30
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________
31
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\}$
1 vote
32
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)$
1 vote
33
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$
34
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... in $X_0$? $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$
35
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automation that accepts $L$? $n-1$ $n$ $n+1$ $2^{n-1}$
36
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$. $M_1$ $M_2$ Which one of the following is TRUE? $L_1 = L_2$ $L_1 \subset L_2$ $L_1 \cap L_{2}^{C} = \varnothing$ $L_1 \cup L_2 \neq L_1$
37
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$S \rightarrow abScT \mid abcT$$T \rightarrow bT \mid b$ ... $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$