# Recent questions and answers in Theory of Computation

1
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\}$
2
What can be said about a regular language $L$ over $\{ a \}$ whose minimal finite state automaton has two states? $L$ must be $\{a^n \mid n \ \text{ is odd}\}$ $L$ must be $\{a^n \mid n \ \text{ is even}\}$ $L$ must be $\{a^n \mid n \geq 0\}$ Either $L$ must be $\{a^n \mid n \text{ is odd}\}$, or $L$ must be $\{a^n \mid n \text{ is even}\}$
3
Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$ I only I and II II and III II only
4
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
5
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
6
Let $\Sigma=\{a,b\}.$ Given a language $L\underline\subset \Sigma^{\ast}$ and a word $w\in\Sigma^{\ast}$, define the languages: $Extend(L,w) :=\{xw\:|\:x\in L\}$ $Shrink(L,w) :=\{x\:|\:xw\in L\}$Show that if $L$ is regular, both $Extend(L,w)$ and $Shrink(L,w)$ are regular.
7
For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be the value of $x$ interpreted as a binary number, where $a_0$ is the most significant bit. More formally, $val(x)$ is given by $\Sigma_{0 \leq i < n} 2^{n-1-i} .a_i$ Design a finite automaton that accepts exactly the set of binary strings $x$ such that $val(x)$ is divisible by either 4 or 5.
1 vote
8
Consider the set of all words over the alphabet $\{x, y, z\}$ where the number of $y$&rsquo;s is not divisible by 2 or 7 and no $x$ appears after a $z$. This language is: regular not known to be regular context-free but not regular recursively enumerable but not context-free
1 vote
9
Let $A$ be a regular language. Consider the following operations on $A$: $2A:=\{xy \mid x, \: y \in A \text{ and } x=y\}$ $A^2 :=\{xy \mid x, \: y \in A\}$ One of these operations necessarily leads to a regular language and the other may ... proof that it is regular. For the non-regular operation, give an example of an $A$ such that applying the operation on it results in a non-regular language.
10
Let $\Sigma = \{a, b\}$. For a word $w \: \: \in \Sigma^*$ let $n_a(x)$ denote the number of $a$'s in $w$ and let $n_b(x)$ denote the number of $b$'s in $w$. Consider the following language: $L:=\{ xy \mid x, \: y \in \Sigma^*, \: \: n_a(x) = n_b(y)\}$ What can we say about $L$? $L$ is regular, but not context-free $L$ is context-free, but not regular $L$ is $\Sigma^*$ None of these
11
Let $L_1$ and $L_2$ be languages over an alphabet $\Sigma$ such that $L_1 \subseteq L_2$. Which of the following is true: If $L_2$ is regular, then $L_1$ must also be regular. If $L_1$ is regular, then $L_2$ must also be regular. Either both $L_1$ and $L_2$ are regular, or both are not regular. None of the above.
12
For a string $x=a_0a_1 \ldots a_{n-1}$ over the alphabet $\{0, 1, 2\}$, define $val(x)$ to be the value of $x$ interpreted as a ternary number, where $a_0$ is the most significant digit. More formally, $val(x)$ is given by $\Sigma_{0 \leq i < n} 3^{n-1-i} \cdot a_i.$ Design a finite automaton that accepts exactly the set of strings $x \in \{0, 1, 2\}^*$ such that $val(x)$ is divisible by 4.
1 vote
13
Let $\Sigma = \{0, 1\}$. Let $A, \: B$ be arbitrary subsets of $\Sigma^\ast$. We define the following operations on such sets: $A+B := \{ w \in \Sigma^\ast \mid w \in A \text{ or } w \in B \}$ ... $A$ and $B$? If yes, give a proof. If not, provide suitable $A$ and $B$ for which this equation fails.
14
For a regular expression $e$, let $L(e)$ be the language generated by $e$. If $e$ is an expression that has no Kleene star $\ast$ occurring in it, which of the following is true about $e$ in general? $L(e)$ is empty $L(e)$ is finite Complement of $L(e)$ is empty Both $L(e)$ and its complement are infinite
15
Let $Σ = \{a, b\}$. Given words $u, v \in Σ*$ , we say that $v$ extends $u$ if $v$ is of the form $xuy$ for some $x, y ∈ Σ^*$ . Given a fixed word $u$, we are interested in identifying whether a finite state automaton accepts some word that extends $u$. ... reports Yes if some word in the language of $\mathcal{A}$ extends $u$ and No if no word in the language of $\mathcal{A}$ extends $u$.
16
Let $Σ = \{a, b, c\}$. Let Leven be the set of all even length strings in $Σ^*$ $(a)$ Construct a deterministic finite state automaton for $L_{even}$. $(b$) We consider an operation $Erase_{ab}$ that takes as input a string $w \in Σ^*$ and erases all occurrences of the pattern $ab$ ... in $L:$ $Erase_{ab}(L)$:= $\{ Erase_{ab}(w)\ |\ w\in L\}$ Show that $Erase_{ab}(L_{even}$) is a regular language.
17
The regular expression $(a^*+b)^*$ is equivalent to which of the following regular expressions: $a^*b^*$ $(a^*b+b)^*$ $(a+b^*)^*$ $(a^*b)^*$
1 vote
18
Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$ Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$ Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$ Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
19
Which of the words below matches the regular expression $a(a+b)^{\ast}b+b(a+b)^{\ast}a$? $aba$ $bab$ $abba$ $aabb$
1 vote
20
Let us assume a binary alphabet $\Sigma=\{a,b\}.$ Two words $u,v\in \Sigma^{\ast}$ are said to be conjugates if there exist $w_{1},w_{2}\in \Sigma^{\ast}$ such that $u=w_{1}w_{2}$ and $v=w_{2}w_{1}.$ Prove that $u$ and $v$ are conjugates if and only if there exists $w\in \Sigma^{\ast}$ such that $uw=wv.$
1 vote
21
Consider an alphabet $\Sigma=\{a,b\}.$ Let $L_{1}$ be the language given by the regular expression $(a+b)^{\ast}bb(a+b)^{\ast}$ and let $L_{2}$ be the language $baa^{\ast}b.$ Define $L:=\{u\in\Sigma^{\ast}\mid \exists w\in L_{2}\: s.t.\: uw\in L_{1}\}.$ Give an example of a word in $L.$ Give an example of a word not in $L.$ Construct an NFA for $L.$
22
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario? We know of polynomial time algorithms for both A and B. We only know of exponential time algorithms for both A and B. We only know an ... a polynomial time algorithm for B. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.
1 vote
23
Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true? The shortest word in $L(A)$ has length at most $n-1.$ The shortest word in $L(A)$ has length at least $n.$ The shortest word not in $L(A)$ has length at most $n-1.$ The shortest word not in $L(A)$ has length at least $n.$
1 vote
24
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not context-free context-free, but not regular both regular and context-free neither regular nor context-free
25
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
1 vote
26
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________
27
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one? $L_1.L_2$ $L_1 \cap L_2$ $L_1 \cap R$ $L_1 \cup L_2$
28
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 _______
29
Suppose we want to design a synchronous circuit that processes a string of $0$'s and $1$'s. Given a string, it produces another string by replacing the first $1$ in any subsequence of consecutive $1$'s by a $0$ ... $\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}$
30
In a pushdown automaton $P=(Q, \Sigma, \Gamma, \delta, q_0, F)$, a transition of the form, where $p,q \in Q$, $a \in \Sigma \cup \{ \epsilon \}$, and $X,Y \in \Gamma \cup \{ \epsilon \}$, represents $(q,Y) \in \delta(p,a,X).$ Consider the ... $\Gamma = \{ \#, A\}$. The number of strings of length $100$ accepted by the above pushdown automaton is ___________
31
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is ... $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$
32
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free? $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
33
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal $\text{DFA}$ with $k$ states. Which one of the following languages must necessarily be accepted by a minimal $\text{DFA}$ with $k$ states? $L-\{01\}$ $L \cup \{01\}$ $\{0,1\}^* – L$ $L \cdot L$
34
Concatenation Operation refers to which of the following set operations : Union Dot Kleene None of the options
35
Give an algorithm that takes a DFA $A$ and computes the number of strings of length $n$ $($for some given $n$ not related to the number of states of $A)$ accepted by $A.$Your algorithm should be polynomial in both $n$ and the number of states of $A.$
36
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$ ... and $L_2$ are decidable $L_1$ is decidable and $L_2$ is undecidable $L_1$ is undecidable and $L_2$ is decidable Both $L_1$ and $L_2$ are undecidable
37
Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free? $L_1 \cap \overline{L_2} \\$ $\overline{\overline{L_1} \cup \overline{L_2}} \\$ $L_1 \cup (L_2 \cup \overline{L_2}) \\$ $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
1 vote
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free? $L_1 \cap L_2$ $L_1 \cdot L_2$ $L_1- L_2$ $L_1\cup L_2$
Consider the following language: $L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$ Which one of the following deterministic finite automata accepts $L?$
​​​​​​Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true