# GATE Questions & Answers of Theory of Computation Computer Science and Information Technology

#### Theory of Computation 103 Question(s) | Weightage 09 (Marks)

If $L$ is a regular language over $\mathrm\Sigma=(a,\;b),$ which one of the following languages is NOT regular ?

For $\mathrm\Sigma=\{a,\;b\},$ let us consider the regular language $L=\{x\vert x=a^{2+3k}\;\mathrm{or}\;x=b^{10+12k},\;k\geq0$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ?

Which one of the following languages over $\sum\;=\;\{a,\;b\}$ is NOT context-free?

Consider the following sets:

S1.       Set of all recursively enumerable languages over the alphabet {0,1}

S2.       Set of all syntactically valid C programs

S3.       Set of all languages over the alphabet {0,1}

S4.       Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?

Let $\mathrm\Sigma$ be the set of all bijections from {1, … , 5} to {1, … , 5}, where $id$ denotes the identity function, i.e. $id(j)=j,\;\forall j$. Let $\circ$ denote composition on functions. For a string $x=x_1\;x_2\;\dots\;x_n\in\mathrm\Sigma^n,\;n\leq0$ , let $\pi(x)=x_1\circ x_2\;\circ\dots\circ\;x_n$. Consider the language $L=\{x\in\mathrm\Sigma^\ast\vert\pi(x)=id\}$. The minimum number of states in any DFA accepting $L$ is .

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

The set of all recursively enumerable languages is

Which one of the following statements is FALSE?

Consider the following languages:

$\style{font-family:'Times New Roman'}{\begin{array}{l}\;\;\mathrm I.\left\{a^mb^nc^pd^q\vert m+p=n+q,\;\mathrm{where}\;m,n,p,q\geq0\right\}\\\;\mathrm{II}.\left\{a^mb^nc^pd^q\vert m=n\;\mathrm{and}\;p=q,\;\mathrm{where}\;m,n,p,q\geq0\right\}\\\mathrm{III}.\left\{a^\mathit mb^\mathit nc^\mathit pd^\mathit q\vert m=n=p\mathit\;\mathrm{and}\mathit\;p\neq q\mathit,\mathit\;\mathrm{where}\mathit\;m\mathit,n\mathit,p\mathit,q\mathit\geq\mathit0\right\}\\\mathrm{IV}.\left\{a^\mathit mb^\mathit nc^\mathit pd^\mathit q\vert mn=p+q\mathit,\mathrm{where}\mathit\;m\mathit,n\mathit,p\mathit,q\mathit\geq\mathit0\mathit\;\right\}\end{array}}$

Which of the languages above are context-free?

Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

(I) For an unrestricted grammar G and a string w, whether $\style{font-family:'Times New Roman'}{w\in L(G)}$
(II) Given a Turing machine M, whether L(M) is regular
(III) Given two grammars G1 and G2, whether L(G1) = L(G2)
(IV) Given an NFA N, whether there is a deterministic PDA such that N and P accept the same language.

Which one of the following statements is correct?

Given a language $L$, define $L^i$ as follows:

$\begin{array}{l}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;L^0=\left\{\varepsilon\right\}\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;L^i=L^{i-1}.\;L\;for\;all\;\;i>0\end{array}$

The order of a language $L$ is defined as the smallest $k$ such that $L^k=L^{k+1}.$ Consider the language $L_1$(over alphabet 0) accepted by the following automaton. The order of $L_1$ is _____.

Consider the following context-free grammar over the alphabet $\style{font-family:'Times New Roman'}{\sum=\{a,b,c\}}$ with S as the  start  symbol:

$\style{font-family:'Times New Roman'}{\begin{array}{l}S\rightarrow abScT\;\vert\;abcT\\T\rightarrow bT\;\vert\;b\end{array}}$

Which one of the following represents the language genrated by the above grammar?

Consider the following grammar:

$\style{font-family:'Times New Roman'}{\begin{array}{l}P\rightarrow xQRS\\Q\rightarrow yz\;\vert\;z\\R\rightarrow w\;\vert\;\varepsilon\\S\rightarrow y\\\end{array}}$

What is FOLLOW(Q)?

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 deteninistic finite-state automaton (DFA) accepting L is __________.

If G is a grammar with productions

$\style{font-family:'Times New Roman'}{S\rightarrow SaS\;\vert\;aSb\;\vert\;bSa\;\vert\;SS\;\vert\;\in}$

where S is the start variable, then which one of the following strings is not generated by G?

Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are non-terminals.

$\style{font-family:'Times New Roman'}{\begin{array}{l}G_1:S\rightarrow\;aSb\vert T,T\rightarrow cT\vert\in\\G_2:S\rightarrow bSa\vert T,T\rightarrow cT\vert\in\end{array}}$

The language $\style{font-family:'Times New Roman'}{L(G_{1\;})\;\cap\;L(G_2)}$ is

Consider the following languages over the alphabet $\style{font-family:'Times New Roman'}{\sum=\{a,b,c\}.}$

Let $\style{font-family:'Times New Roman'}{L_1=\{a^nb^nc^m\vert m,n\geq0\}\;and\;\;L_2=\{a^mb^nc^n\vert m,n\geq0\}.}$

Which of the following are context-free languages?

$\style{font-family:'Times New Roman'}{\begin{array}{l}\mathrm I.\;\;\;\;{\mathrm L}_1\cup\;{\mathrm L}_2\\\mathrm{II}.\;\;{\mathrm L}_1\cap\;{\mathrm L}_2\end{array}}$

Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language $\{x\;\#\;f(x)\vert x\in A^\ast\}$. Which of the following statemeant is true:

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?

I. $\style{font-family:'Times New Roman'}{{\mathrm L}_1\cup{\mathrm L}_2}$ is context-free.

II. $\style{font-family:'Times New Roman'}{\overline{{\mathrm L}_1}}$ is context-free.

III. L1-R is context-free

IV. $\style{font-family:'Times New Roman'}{{\mathrm L}_1\cap{\mathrm L}_2}$ is context-free.

Identify the language genrated by the following grammar, where S is the start variable

$\begin{array}{l}S\rightarrow XY\\X\rightarrow aX\;\vert a\\Y\rightarrow aYb\;\vert\in\end{array}$

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $\style{font-family:'Times New Roman'}{L=\{w_1aw_2\vert w_1,\;w_2\;\in\{a,b\}\ast,\;\vert w_1\vert=2,\;\vert w_2\vert\geq3\}}$ is _________.

Let $\delta$ denote the transition function and $\widehat\delta$ denote the extended transition function of the $\style{font-family:'Times New Roman'}{\mathit\in-\mathrm{NFA}}$ whose transition table is given below:

 $\style{font-family:'Times New Roman'}\delta$ $\style{font-family:'Times New Roman'}\in$ a b $\style{font-family:'Times New Roman'}\rightarrow$q0 {q2} {q1} {q0} q1 {q2} {q2} {q3} q2 {q0} $\style{font-family:'Times New Roman'}\phi$ $\style{font-family:'Times New Roman'}\phi$ q3 $\style{font-family:'Times New Roman'}\phi$ $\style{font-family:'Times New Roman'}\phi$ {q2}

Then $\style{font-family:'Times New Roman'}{\widehat\delta(q_2,aba)}$ is

Consider the following languages.

$\begin{array}{l}{\mathrm L}_1=\{\mathrm a^\mathrm p\vert\;\mathrm p\;\mathrm{is}\;\mathrm a\;\mathrm{prime}\;\mathrm{number}\}\\\;L_2=\{\mathrm a^\mathrm n\mathrm b^\mathrm m\mathrm c^{2m}\vert\;\mathrm n\geq0,\;\mathrm m\geq0\}\\\;L_3=\{\mathrm a^\mathrm n\mathrm b^\mathrm n\mathrm c^{2\mathrm n}\vert\;\mathrm n\geq0\}\\\;L_4=\{\mathrm a^\mathrm n\mathrm b^\mathrm n\vert\;\mathrm n\geq1\}\end{array}$

Which of the following are CORRECT ?

I. L1 is context-free but not regular

II. L2 is not context-free.

III. L3 is not context-free but recursive.

IV. L4 is deterministic context-free.

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turning machine M.

Which of the following decision problems are undecidable?

I. Given a regular expression R and a string $w$, is $\style{font-family:'Times New Roman'}{w\in L(R)}$ ?

II. Given context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}\phi$ ?

III. Given a context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}{\sum\nolimits^\ast}$ for some alphabet $\style{font-family:'Times New Roman'}\sum$ ?

IV. Given a Turning machine M and a string $w$, is $\style{font-family:'Times New Roman'}{w\in L(M)}$ ?

Which of the following languages is generated by the given grammar?

$S\rightarrow aS\left|bS\right|\varepsilon$

Which of the following decision problems are undecidable?

I. Given NFAs $N_1$ and $N_2$, is $L$($N_1$)∩$L$($N_2$) =$\mathrm\Phi?$

II. Given a CFG G = $(N,Σ,P,S)$ and a string $x\in\Sigma^\ast$, does $x\in L\ast\left(G\right)?$

III. Given CFGs $G_1$ and $G_2$, is $L$($G_1$) = $L$($G_2$)?

IV. Given a TM $M$, is $L\left(M\right)=\mathrm\Phi?$

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

Consider the following context-free grammars:

$G_1:\;S\rightarrow aS\vert B,B\rightarrow b\vert bB$
$G_2:\;S\rightarrow aA\vert bB,A\rightarrow aA\vert B\vert\varepsilon,B\rightarrow bB\vert\varepsilon$

Which one of the following pairs of languages is generated by $G_1$ and $G_2$, respectively?

Consider the transition diagram of a PDA given below with input alphabet and stack alphabet .Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that $\overset-Y$ reduces to W, and Z reduces to $\overset-X$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

The number of states in the minimum sized DFA that accepts the language defined by the regular expression

$\left(0+1{\right)}^{\ast }\left(0+1\right)\left(0+1{\right)}^{\ast }$

is ___________.

Language L1 is defined by the grammar:

Language L2 is defined by the grammar:

Consider the following statements:

P: L1 is regular

Q: L2 is regular

Which one of the following is TRUE?

Consider the following types of languages: L1 : Regular, L2 : Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?

I. is recursively enumerable

II. is recursive

III.${L}_{1}^{*}\cap {L}_{2}$ is context-free

IV.${L}_{1}\cup \overline{{L}_{2}}$ is context-free

Consider the following two statements:
I. If all states of an NFA are accepting states then the language accepted by the NFA is $\textstyle\sum_{}^\ast$.
II. There exists a regular language A such that for all languages $B$ , $\style{font-family:'Times New Roman'}{A\cap B}$ is regular.
Which one of the following is CORRECT?

Consider the following languages:
$L_1=\{a^{n\;}b^{m\;}c^{n+m}:m,n\geq1\}$
$L_2=\{a^{n\;}b^{n\;}c^{2n}:,n\geq1\}$
Which one of the following is TRUE?

Consider the following languages.
$L_1{=\left\{<M>\vert M\;\mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{some}\;\mathrm{input}\right\},}$
$L_2{=\left\{<M>\vert M\;\mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{all}\;\mathrm{some}\;\mathrm{inputs}\right\}\mathrm{and}}$
$L_3=\left\{<M>\vert M\;accepts\;\varepsilon\right\}$,
where for each Turing machine $M,<M>$ denotes a specific encoding of $M$. Which one of the following is TRUE?

Which one of the following grammars is free from left recursion?

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,

int a;
The grammars use $D$ as the start symbol, and use six terminal symbols int ; id [ ] num.
 Grammar G1 Grammar G2 $D\rightarrow\mathbf{int}\boldsymbol\;L;$ $D\boldsymbol\rightarrow\mathbf{int}\boldsymbol\;L;$ $L\rightarrow\mathbf{id}\lbrack E$ $L\boldsymbol\rightarrow\mathbf{id}\boldsymbol\;E$ $E\rightarrow\mathbf{num}\rbrack$ $E\rightarrow E\lbrack\mathbf{num}\rbrack$ $E\rightarrow\mathbf{num}\rbrack\lbrack E$ $E\rightarrow\lbrack\mathbf{num}\rbrack$

Which of the grammars correctly generate the declaration mentioned above?

For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?
I. ${\overline{L}}_{1}$ (complement of L1) is recursive
II. ${\overline{L}}_{2}$ (complement of L2) is recursive
III. ${\overline{L}}_{1}$ is context – free
IV. ${\overline{L}}_{1}\cup {L}_{2}$ is recursively enumerable Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the languages L(M) $\cap$ L(N) is ________.

Consider the NPDA $\left\langle Q=\left\{q_0,\;q_1,\;q_3\right\},\;\mathrm\Sigma=\left\{0.1\right\},\;\mathrm\Gamma=\left\{0,1,\perp\right\},\;\mathrm\delta\;q_\mathit0\mathit,\mathit\;\perp F\;=\left\{q_\mathit2\right\}\right\rangle$ where (as per usual convention) Q is the set of states, ∑ is the input alphabet, Γ is the stack alphabet, δ is the state transition function, q0 is the initial state, $\perp$ is the initial stack symbol, and F is the set of accepting states. The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automation?

Consider the following statements.

I.   The complement of every Turing decidable language is Turing decidable
II.  There exists some language which is in NP but is not Turing decidable
III. If L is a language in NP, L is Turing decidable

Which of the above statements is/are true?

In the context of abstract-systax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is _______.

Which of the following languages is/are regular?
L1:{wxwR|w, x $\in$ {a,b}* and |w|, |x| > 0},wR is the reverse of string w
L2: {anbm | m $\ne$ n and m, n $\ge$ 0}
L3: {apbqcr | p, q, r $\ge$ 0}

Consider the alphabet ${\sum }_{}^{}$ = {0, 1}, the null/empty string $\lambda$ and the sets of strings X0, X1, and X2 generated by the corresponding non-terminals of a regular grammar X0, X1, and X2 are related as follows.

X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {$\lambda$}

Which one of the following choices precisely represents the strings in X0?

Let L be the language represented by the regular expression $\sum _{}^{}$* 0011$\sum _{}^{}$* where $\sum _{}^{}$ = {0, 1}. What is the minimum number of states in a DFA that recognizes $\overline{)\mathrm{L}}$ (complement of L)?

Which of the following languages are context-free?

L1 = {ambnanbm |m, n$\ge$1}
L2 = {ambnambn|m, n $\ge$1}
L3 = {ambn|m = 2n+1}

which one of the following is TRUE?

Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?

Let L be a language and $\overline{)L}$ be its complement. Which one of the following is NOT a viable possibility?

Which of the regular expressions given below represent the following DFA? I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1

If ,consider

(I) ${L}_{1}.{L}_{2}$ is a regular language

(I)${L}_{1}.{L}_{2}=\left\{{a}^{n}{b}^{n}|n\ge 0\right\}$

Which one of the following is CORRECT?

Let Am B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let

Let Let Which one of the following is TRUE?

The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.

a*b*(ba)*a*

Let Σ be a finite non-empty alphabet and let ${2}^{{\sum }^{*}}$ be the power set of Σ*. Which one of the following is TRUE?

Which one of the following problems is undecidable?

Consider the following languages over the alphabet $\sum =\left\{0,1,c\right\}$:

${L}_{1}=\left\{{0}^{n}{1}^{n}|n\ge 0\right\}\phantom{\rule{0ex}{0ex}}$
${L}_{2}=\left\{wc{w}^{r}|w\in {\left\{0,1\right\}}^{*}\right\}\phantom{\rule{0ex}{0ex}}$
${L}_{3}=\left\{w{w}^{r}|w\in \left\{0,1\right\}*\right\}$

Here, wr is the reverse of the string w. Which of these languages are deterministic Context-free languages?

Consider the languages ${L}_{1}=\mathrm{\Phi }$ and ${L}_{2}=\left\{a\right\}$. Which one of the following represents ${L}_{1}{L}_{2}^{\ast }\cup {L}_{1}^{\ast }$?

Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognizable languages are closed under union and intersection.

Consider the following languages.
${L}_{1}=\left\{{0}^{p}{1}^{q}{0}^{r}|p,q,r\ge 0\right\}$
${L}_{2}=\left\{{0}^{p}{1}^{q}{0}^{r}|p,q,r\ge 0,p\ne r\right\}$
Which one of the following statements is FALSE?

Consider the DFA A given below. Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.

Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

Assuming P ≠ NP, which of the following is TRUE?

What is the complement of the language accepted by the NFA shown below? Assume $\Sigma$ = {a} and $\epsilon$ is the empty string. Which of the following problems are decidable?

 1) Does a given program ever produce an output? 2) If $L$ is a context-free language, then, is $\stackrel{-}{L}$ also context-free? 3) If $L$ is a regular language, then, is $\stackrel{-}{L}$ also regular? 4) If $L$ is a recursive language, then, is $\stackrel{-}{L}$ also recursive?

Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa 