# Recent questions and answers in Theory of Computation

1
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
2
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
1 vote
3
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
4
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 ________.
5
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
6
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
7
If $L$ and $\bar L$ are recursively enumerable then $L$ is regular context-free context-sensitive recursive
8
Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free I and II I and IV II and III II and IV
9
Which of the following is true for the language $\left\{ a^p \mid p \text{ is a prime } \right \}?$ It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free, but accepted by a Turing machine
10
Show that the language L={xy∣|x|=|y|,x≠y} is context free. Do not give links plz explain in simple manner
11
Context-free languages are closed under: Union, intersection Union, Kleene closure Intersection, complement Complement, Kleene closure
12
Define a context free languages $L \in \{0, 1\}^*$, $\text{init} (L) = \{u \mid uv \in L$ for some $v$ in $\{0, 1\}^*\}$ ( in other words, $\text{init}(L)$ is the set of prefixes of $L$ ... null string the set of all binary strings with exactly one more $0$ than the number of $1$'s or one more $1$ than the number of $0$'s None of the above
13
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
14
Construct a DFA over Σ=(a,b) so that it accepts all strings where 1) 2nd symbol from the right is 'a' 2) 3rd symbol from the right is 'a'
15
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string $S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon$ Which of the following strings is NOT generated by the grammar? $aaaa$ $baba$ $abba$ $babaaabab$
16
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2|w|+1 (b) log2|w| (c) log2|w|−1 (d) None of these
1 vote
17
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack. DPDA with empty stack accepts LR(0) grammar. Can someone explain in depth/or give good reference links?
18
Consider the machine $M$: The language recognized by $M$ is: $\left\{ w \in \{a, b\}^* \text{ | every a in$w$is followed by exactly two$b$'s} \right\}$ $\left\{w \in \{a, b\}^* \text{ | every a in$w$is followed by at least two$b$'s} \right\}$ ... $contains the substring$abb$'} \right\}$ $\left\{w \in \{a, b\}^* \text{ |$w$does not contain$aa$' as a substring} \right\}$
1 vote
19
$\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 \}$
20
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$
21
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
22
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
23
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?
24
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\}$ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
25
find grammar that generates L={a^nb^m:n>=0,m<n}
1 vote
26
If L be a language recognizable by a finite automata, then language from {L}={w such that w is prefix of v where v belongs to L},is a a. Regular Language b. Context Free language c. Context Sensitive Language d. Recursive Enumerable Language
1 vote
27
If a grammar G is both left linear as well as right linear then,what should be the case a) G is always not regular b) G may or may not be regular c) something else
28
Please follow the attachment how can we prove that the given language is not linear please explain?
29
L={a^m b^n | m-n=even} Is this language a regular language?
30
A. L2 is DCFL B. L2 is CFL but not DCFL C. L2 is not CFL D. None of these
31
ww^r complement is CSL Is this right or wrong If right please how can we prove
1 vote
32
L2={a^i b^(i^2) } where I is natural no. Identify the class of language and it's complement...
33
$L_1=\{(xy)^m(yz)^m\;,\;m\geq 1\}$ $L_2=\{a^mb^nc^k\;|\;m>n\;or\;m<n\}$ Which of the following is True? (a) $L_1$ is CFL, $L_2$ are DCFL (b) $L_1$ is DCFL, $L_2$ is CFL (c) Both $L_1$, $L_2$ are CFLs (d) Both $L_1$, $L_2$ are DCFLS
34
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
35
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
1 vote
36
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
37
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $\text{ has at least as many occurrences of }$ $(000)'$ $\text{s as}$ ... one of the following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
Consider the following state table for a sequential machine. The number of states in the minimized machine will be ... $4$ $3$ $2$ $1$
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ Which one of the following is TRUE? $L_1$ ... $L_1$ context- free but not regular and $L_2$ is context-free. Neither $L_1$ nor $L_2$ is context- free. $L_1$ context- free but $L_2$ is not context-free.
the minimum number of states in the PDA accepting the language $L=\left\{a^n b^m \mid n>m;m,n>0 \right\}$ a) 2 b) 3 c) 4 d) 5