# Recent questions and answers in Theory of Computation

1
Consider the set of strings on $\{0,1\}$ in which, every substring of $3$ symbols has at most two zeros. For example, $001110$ and $011001$ are in the language, but $100010$ is not. All strings of length less than $3$ are also in the language. A partially completed DFA that accepts this ...
2
Consider the languages: $L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$ and $L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$ Which one of the following statements is FALSE? $L_1 \cap L_2$ is a context-free language $L_1 \cup L_2$ is a context-free language $L_1 \text{ and } L_2$ are context-free languages $L_1 \cap L_2$ is a context sensitive language
3
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
4
Eliminate useless productions from $S\rightarrow a|aA|B|C,$ $A\rightarrow aB|\lambda,$ $B\rightarrow Aa,$ $C\rightarrow cCD,$ $D\rightarrow ddd.$
5
Eliminate all useless productions from the grammar $S\rightarrow aS|AB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?
6
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false
7
Use the exhaustive search parsing method to parse the string $abbbbbb$ with the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A|\lambda.$ In general, how many rounds will be needed to parse any string $w$ in this language?
1 vote
8
Find a grammar equivalent to $S\rightarrow aAB, A\rightarrow bBb, B\rightarrow A|\lambda$ that satisfies the conditions of Theorem 5.2. Theorem 5.2 Suppose that $G = (V, T, S, P)$ is a context-free grammar that does not have any rules of the form $A → λ,$ ... can be made into an algorithm which, for any $w ∈ Σ^*,$ either produces a parsing of $w$ or tells us that no parsing is possible.
9
Is the string $aabbababb$ in the language generated by the grammar $S → aSS|b$? Show that the grammar with productions $S\rightarrow aAb|\lambda,$ $A\rightarrow aAb|\lambda$ is unambiguous.
10
Which of the following is TRUE? Every subset of a regular set is regular Every finite subset of a non-regular set is regular The union of two non-regular sets is not regular Infinite union of finite sets is regular
11
Show that the grammar with productions $S\rightarrow SS,$ $S\rightarrow \lambda,$ $S\rightarrow aSb,$ $S\rightarrow bSa.$ is ambiguous.
12
Show that the grammar $S\rightarrow aSb|SS|\lambda$ is ambiguous, but that the language denoted by it is not.
13
Show that the following grammar is ambiguous. $S\rightarrow aSbS|bSaS|\lambda$
1 vote
14
here answer is given is A won''t it be B? as with A we cannot get 100 string,but with B we can
15
Construct an unambiguous grammar equivalent to the grammar in Exercise 6.
1 vote
16
Show that the following grammar is ambiguous. $S\rightarrow AB|aaB,$ $A\rightarrow a|Aa,$ $B\rightarrow b.$
17
Find an s-grammar for $L =$ {$a^nb^{n+1} : n ≥ 2$}.
18
Find an s-grammar for $L =$ {$a^nb^n : n ≥ 1$}.
19
Find an s-grammar for $L (aaa^*b + b)$.
20
Define what one might mean by properly nested parenthesis structures involving two kinds of parentheses, say ( ) and [ ]. Intuitively, properly nested strings in this situation are ([ ]), ([[ ]])[( )], but not ([ )] or (( ]]. Using your definition, give a context-free grammar for generating all properly nested parentheses.
21
Consider the derivation tree below. Find a grammar $G$ for which this is the derivation tree of the string $aab$. Then find two more sentences of $L(G)$. Find a sentence in $L(G)$ that has a derivation tree of height five or larger.
22
Consider the grammar with productions $S\rightarrow aaB,$ $A\rightarrow bBb|\lambda,$ $B\rightarrow Aa.$ Show that the string $aabbabba$ is not in the language generated by this grammar.
23
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is context-free.
24
Show that the complement of the language $L=$ {$ww^R:w∈$ {$a,b$}$^*$} is context-free.
1 vote
25
Show a derivation tree for the string $aabbbb$ with the grammar $S\rightarrow AB|\lambda,$ $A\rightarrow aB,$ $B\rightarrow Sb.$ Give a verbal description of the language generated by this grammar.
26
Show that the following language is context-free. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,|u|=|w|=2$}.
27
Let $L_1$ be the language $L_1 =$ {$a^nb^mc^k : n = m$ or $m ≤ k$} and $L_2$ the language $L_2 =$ {$a^nb^mc^k : n + 2m = k$}. Show that $L_1 ∪ L_2$ is a context-free language.
28
Let $L =$ {$a^nb^n : n ≥ 0$}. (a) https://gateoverflow.in/305106/peter-linz-edition-4-exercise-5-1-question-13-a-page-no-134 (b) Show that $L^k$ is context-free for any given $k ≥ 1$. (c) Show that $\overline{L}$ and $L^*$ are context-free.
29
Find a context-free grammar for $Σ =$ {$a, b$} for the language $L =$ {$a^nww^Rb^n : w ∈ Σ^*, n ≥ 1$}.
30
Show that $L =$ {$w ∈$ {$a,b,c$}$^* : |w| = 3n_a(w)$} is a context-free language.
31
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0, k ≥ 0$). (a) $L =$ {$a^nb^mc^k : n = m$ or $m ≤ k$}. (b) $L =$ {$a^nb^mc^k : n = m$ or $m ≠ k$}. (c) $L =$ {$a^nb^mc^k : k = n + m$}. (d) $L =$ {$a^nb^mc^k : n + 2m = k$}. (e) $L =$ ... $a, b, c$}$^* : n_a (w) + n_b (w) ≠ n_c (w)$}. (g) $L =$ {$a^nb^mc^k, k ≠ n + m$}. (h) $L =$ {$a^nb^mc^k : k ≥ 3$}.
1 vote
32
Find context free grammars for the following languages (with n>=0, m>=0, k>=0) (a) L={anbmck : n=m or m<=k} (b) L={ anbmck : n=m or m≠k} (c) L={anbmck : k=n+m } (d) L={ anbmck : n+2m=k} (e) L={anbmck : k=|n-m| } (f) L={ w ∈ {a,b,c}* : na(w)+nb(w)≠nc(w) } (g) L={ anbmck : k≠n+m } (h) L= { anbmck : K>=3}
33
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0$). (a) $L =$ {$a^nb^m : n ≤ m + 3$}. (b) $L =$ {$a^nb^m : n ≠ m − 1$}. (c) https://gateoverflow.in/208410/peter-linz-edition-4-exercise-5-1-question-7-c-page-no-133 (d) $L =$ {$a^nb^m : 2n ≤ m ≤ 3n$ ... $^* : n_a (v) ≥ n_b (v),$ where $v$ is any prefix of $w$}. (g) $L =$ {$w ∈$ {$a,b$}$^* : n_a (w) = 2n_b(w) + 1$}.
34
Which of the following is not a monotonically increasing grammar? (A) Context-sensitive grammar (B) Unrestricted grammar (C) Regular grammar (D) Context-free grammar
35
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
36
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
37
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\}$
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
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