# Questions & Answers of Theory of Computation

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

Question No. 10

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?

Question No. 17

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)?

Question No. 22

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 __________.

Question No. 34

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?

Question No. 37

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

Question No. 38

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}}$

Question No. 39

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:

Question No. 104

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.

Question No. 116

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}$

Question No. 125

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 _________.

Question No. 139

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

Question No. 140

Consider the following languages.

$\style{font-family:'Times New Roman'}{\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 n\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.

Question No. 141

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)}$

Question No. 26

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

S→ aS|bS|ε

Question No. 27

Which of the following decision problems are undecidable?

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

II. Given a CFG G = (N,Σ,P,S) and a string x∈Σ, does x∈L(G)?

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

IV. Given a TM M, is L(M) =Φ?

Question No. 28

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

Question No. 52

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?

Question No. 53

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?

Question No. 54

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?

Question No. 126

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 ___________.

Question No. 127

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?

Question No. 128

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

Question No. 152

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?

Question No. 153

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?

Question No. 154

Consider the following languages.
$L_1$ = $\{\vert\;M\;$ \mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{some}\;\mathrm{input}$\},$
$L_2$ = $\{\vert\;M\;$ \mathrm M\;\mathrm{takes}\;\mathrm{at}\;\mathrm{least}\;2016\;\mathrm{steps}\;\mathrm{on}\;\mathrm{all}\;\mathrm{inputs}$\},$ and
$L_3$ = $\{\vert\;M\;$ accepts $\varepsilon\;\},$
where for each Turing machine M, $\style{font-family:'Times New Roman'}{\left\langle M\right\rangle}$ denotes a specific encoding of M. Which one of the
following is TRUE?

Question No. 155

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

Question No. 156

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[10][3];
The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num.
 Grammar G1 Grammar G2 $D\boldsymbol\rightarrow\boldsymbol i\boldsymbol n\boldsymbol t\boldsymbol\;\boldsymbol L\boldsymbol;$ $D\boldsymbol\rightarrow\boldsymbol i\boldsymbol n\boldsymbol t\boldsymbol\;\boldsymbol L\boldsymbol;$ $\boldsymbol L\boldsymbol\rightarrow\boldsymbol i\boldsymbol d\lbrack E$ $\boldsymbol L\boldsymbol\rightarrow\boldsymbol i\boldsymbol d\boldsymbol\;E$ $E\rightarrow\mathrm{num}\rbrack$ $E\rightarrow E\lbrack\mathrm{num}\rbrack$ $E\rightarrow\mathrm{num}\rbrack\lbrack\mathrm E$ $E\rightarrow\lbrack\mathrm{num}\rbrack$

Which of the grammars correctly generate the declaration mentioned above?

Question No. 28

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

Question No. 49

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 ________.

Question No. 50

Consider the NPDA 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?

Question No. 120

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?

Question No. 128

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

Question No. 145

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

Question No. 146

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}

Question No. 160

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?

Question No. 232

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)?

Question No. 244

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}

Question No. 25

which one of the following is TRUE?

Question No. 26

Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?

Question No. 45

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

Question No. 46

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

Question No. 125

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?

Question No. 126

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?

Question No. 145

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

Question No. 146

Let Let Which one of the following is TRUE?

Question No. 225

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

a*b*(ba)*a*

Question No. 226

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

Question No. 245

Which one of the following problems is undecidable?

Question No. 246

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?

Question No. 8

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 }$?

Question No. 17

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.

Question No. 32

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?

Question No. 33

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.

Question No. 41

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)?

Question No. 4

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

Question No. 12

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

Question No. 24

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?

Question No. 25

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

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

Question No. 46

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 language is shown below.

The missing arcs in the DFA are

Question No. 8

Which of the following pairs have DIFFERENT expressive power?

Question No. 19

The lexical analysis for a modem computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

Question No. 24

Let P be a regular language and Q be a context-free language such that Q $\overline{)\subset }$ P. (For example, let P be the language represented by the regular expression p* q* and Q be { pn qn | n $\in$ $\mathbb{N}$}). Then which of the following is ALWAYS regular?

Question No. 26

Consider the languages L1. L2 and L3 as given below.

L1= {0p 1q | p, q ∈ N},

L2= {0p 1q | p, q ∈ N and p = q} and

L3 = {0p 1q 0r | p, q, r ∈ N and p = q = r}. Which of the following statements is NOT TRUE?

Question No. 42

Definition of a language L with alphabet {a} is given as following.
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?

Question No. 45

A deterministic finite automaton (DFA) D with alphabet ∑ = {a, b} is given below.

Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?

Question No. 17

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

Question No. 39

Let L = {w ∈ (0 + 1)*|w has even number of |s|, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?

Question No. 40

Consider the languages L1 = {0i1j | ij}. L2 = {0i1j | i = j}. L3 = {0i1j | i = 2j + 1}. L4 = {0i1j | i ≠ 2j}. Which one of the following statements is true?

Question No. 41

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 a non-deterministic finite automaton that accepts L?

Question No. 12

S → aSa|bSb|a|b

The language generated by the above grammar over the alphabet {a,b} is the set of