Computer Science and Information Technology - Theory of Computation
Exam Duration: 45 Mins Total Questions : 30
Which of the following is false?
- (a)
Regular sets are closed under complementation
- (b)
Regular sets are closed under intersection
- (c)
Regular sets are closed under reversed
- (d)
None of the above
The regular expression 0* (10*)* denotes the same set as
- (a)
0 (0 + 10)*
- (b)
(0 + 1)* 10(0 + 1)*
- (c)
(1*0)*1*
- (d)
None of these
Which of the following regular expressions over {0, 1} denote the set of strings and containing 100 as a sub-string?
- (a)
0*1010*
- (b)
0*(1*0)*
- (c)
0*101
- (d)
0* (0 + 1)*
Recursive languages are
- (a)
a proper subset of context-free languages
- (b)
always recognized by push-down automata
- (c)
also called type 0 language
- (d)
recognizable by turning machines
Which of the following languages is true the transition function \(\delta\)of a TM
- (a)
\(\delta\)(p, y, D)\(\rightarrow\)(q, X, D)
- (b)
\(\delta\)(p, y, D)\(\rightarrow\)(q, X, )
- (c)
\(\delta\)(q, X)\(\rightarrow\)(p, D)
- (d)
\(\delta\)(q, x)\(\rightarrow\)(p, y, D)
Consider the transition table of the TM given below
\(\delta \) | 1 | 1 | b |
q0 | qo0R | q11R | q2 bR |
q1 | q10R | q01R | - |
q2 | - | - | - |
Which of the following strings will not be accepted?
- (a)
010101
- (b)
101010
- (c)
100101
- (d)
(a), (b) and (c)
What is the CFL represented by the following CFG?
\(S\rightarrow AB/C\\ A\rightarrow 0A/\epsilon \\ B\rightarrow 1B2/1B/\epsilon \\ C\rightarrow 0C2/0C/D\\ D\rightarrow 1D/\epsilon \)
- (a)
\(\{ { 0 }^{ i }{ 1 }^{ j }{ 2 }^{ k }/i+j\le k\} \)
- (b)
\(\left\{ { 0 }^{ i }{ 1 }^{ j }{ 2 }^{ k }{ 1 }^{ ' }/\left( i=k \right) \right\} or\left\{ j\ge k\quad and\quad l\ge 0 \right\} \)
- (c)
\(\left\{ { 0 }^{ i }{ 1 }^{ j }{ 2 }^{ k }/k\le 1ork\le j \right\} \)
- (d)
None of the above
Let \(L\subseteq { \Sigma }^{ * }\) , where \(\Sigma =\{ a,b\} \) which of the following is true?
- (a)
L={x/x has an equal number of a's and b's is regular
- (b)
\(L=\{ { a }^{ n }{ b }^{ n }/n,\quad n\ge 1\} \) is regular
- (c)
L={x/x has more a's than b's} is regular
- (d)
\(L=\{ { a }^{ m }{ b }^{ n }/m\ge 3\quad ,\quad n\ge 1\} \)is regular
The string 1101 does not belongs to the set represented bygate-arihant-cs-it-c06-p342-q05
- (a)
110*(0+1)
- (b)
1 (0+1)* 101
- (c)
(10)* (01)* (00+11)*
- (d)
(00) + (11)*0)*
The major difference between a Moore and a Mealy machine is the output of the former depends
- (a)
only on the present input
- (b)
only on the present state
- (c)
only on the present state and present input
- (d)
None of the above
Which of the following problems is undeciable?
- (a)
Membership algorithm in context-free language
- (b)
Whether a context-free language is regular
- (c)
Whether a finite automata halts on all inputs
- (d)
Membership problem for type 0 language
Context-free language are
- (a)
close under union
- (b)
close under intersection
- (c)
close under complementation
- (d)
closed under Kleen closure
Which of the following is true?
- (a)
If language is context-free it can always be accepted by deterministic push-down automata
- (b)
The union of two context-free language is context free
- (c)
The intersection of two context-free language is context-free
- (d)
The complement of context-free language is context-free
Consider the following given below
\(S->aSb/bSb/\in \)
Which of the following strings cannot be generated using the grammar G?
- (a)
aabbaabb
- (b)
bbaabaab
- (c)
aaabbbaaa
- (d)
None of these
Context-free grammar is not closed under
- (a)
Kleen closure
- (b)
complementation
- (c)
union
- (d)
product
The language \({ a }^{ m }{ b }^{ n }{ c }^{ m+n }/m,n\ge 1\} \)is
- (a)
regular
- (b)
context free but not regular
- (c)
context sensitive but not context free
- (d)
type-0 but not context sensitive
The grammar S->aasbb/ab can generated the set
- (a)
{a2n+1b2n+1 n=1,2,3,....}
- (b)
{anbn/n=1,2,3,...}
- (c)
{a2n+1b2n+1/n=0,1,2,3,...}
- (d)
{a2n-1b2n-1/n=0,1,2,3,...}
Consider the production of grammar G as given below
\(S->aAb/bAs/aSa/bSb\\ A->\in /As/Ab\)
Which of the following strings cannot generated bygrammar?
- (a)
abbaaba
- (b)
aaabbbaaa
- (c)
aabbaa
- (d)
ababab
Consider the grammar G:
S->AB
A->\(aAA/\in \)
\(B->bBB/\in \)
Find the nullable symbol in the given grammar.
- (a)
A,B and S
- (b)
A and B
- (c)
B
- (d)
A
Let \(\Sigma =\{ a,b\} ,\quad L={ \Sigma }^{ * }\quad and\quad R=\{ { a }^{ n }{ b }^{ n }\)such that n>0}. Then the languange \(L\cup R\) and R are, respectively
- (a)
regular,regular
- (b)
not regular, regular
- (c)
regular, nor regular
- (d)
not regular, not regular
Consider the following statements:
(i) r+(s+t)=(r+s)+t
(ii)r(s+t)=rs+rt
(iii)(rs)*t=r(st)*
Which of the above is /are true about regular expression r,s and t?
- (a)
(i) only
- (b)
(ii) and (iii)
- (c)
(i), (ii) and (iii)
- (d)
None of these
How many variables remain in the grammar after removal of useless symbols?
\(S\rightarrow aBA\\ B\rightarrow bBC/b\\ C\rightarrow cC/D\\ A\rightarrow aAE/E\\ D\rightarrow aDD\\ E\rightarrow ED/eE/e\)
- (a)
3
- (b)
4
- (c)
5
- (d)
6
For the grammar given below, what is the equivalent CFG without E productions?
\(S\rightarrow ASB/\epsilon ,A\rightarrow Aa/\epsilon ,B\rightarrow bB/\epsilon \)
- (a)
\(S\rightarrow ASB/AB/A/AS,\quad A\rightarrow Aa/a,\quad B\rightarrow aB/b\)
- (b)
\(S\rightarrow ASB/AB/AS/SB/A/B/S,\quad A\rightarrow Aa/a,\quad B\rightarrow bB/b\)
- (c)
\(S\rightarrow ASB/AB,\quad A\rightarrow Aa/a,\quad B\rightarrow bB/\epsilon \)
- (d)
None of the above
Which of the following statements is/are true?
\((i)\quad abcd\quad \epsilon \quad { \left( { b }^{ * }{ a }^{ * } \right) }^{ * }{ \left( { d }^{ * }{ c }^{ * } \right) }^{ * }\\ (ii)\quad abcd\quad \epsilon \quad { \left( { d }^{ * }{ c }^{ * }{ b }^{ * }{ a }^{ * } \right) }^{ * }\\ (iii)\quad abcd\quad \epsilon \quad { \left( { b }^{ * }{ a }^{ * }+{ c }^{ * }{ d }^{ * } \right) }^{ * }\)
- (a)
(i) and (iii)
- (b)
(ii) and (iii)
- (c)
(i) and (ii)
- (d)
(i), (ii) and (iii)
\(M=\left( Q,\Sigma ,T,\delta ,{ q }_{ 0 },\notin ,$,F \right) \) is a LBA. Then, which of the following is necessarily true?
- (a)
L(m) is a CSL.
- (b)
L(m) is a CFL
- (c)
L(m) is regular
- (d)
None of these
Find CFG to accept \(\left\{ \omega /\omega \quad is\quad odd \right\} \).
- (a)
\(S\rightarrow 0AS/1AS/1\\ A\rightarrow 0S/1S/\epsilon \)
- (b)
\(S\rightarrow 0A/1\\ A\rightarrow 0S/1S/\epsilon \)
- (c)
\(S\rightarrow 0/1/0S0/0S1\\ S\rightarrow 1S1/\epsilon \)
- (d)
\(S\rightarrow 0/1/0S0/0S1\\ S\rightarrow 0|S|10S\)
Consider the grammar G={s}, {a, b}, {S, P} with productions \(S\rightarrow asa/bsb/\lambda \):
The language generated from this grammar is
- (a)
context free
- (b)
regular
- (c)
Both (a) and (b)
- (d)
None of these
L1 : {ai, bj ak / j = max {i, k}} is not CFL's
L2 : {an bn ci \(\neq \) n} is not CFL's
Which of the following statements is correct regarding the given languages?
- (a)
L1 only
- (b)
L2 only
- (c)
Both (L1) and (L2)
- (d)
None of these
The language \(L=\left\{ { \omega }_{ 1 }.{ \omega }_{ 2 },{ \omega }_{ 1 },{ \omega }_{ 2 }\epsilon { \left\{ a,b \right\} }^{ * },{ \omega }_{ 1 }\neq { \omega }_{ 2 }^{ R } \right\} \) with \(\epsilon =\left\{ a,b,c \right\} \) is context free. Statement whether the above statements is true?
- (a)
True
- (b)
False
- (c)
Not sufficient information
- (d)
None of the above
Consider the following statements:
(i) No valid crossing sequence may have a repeat state with the head moving in the same direction.
(ii) All valid crossing sequence are of even length and finite in number for a given 2 DFA.
(iii) In a valid crossing sequence, no two odd numbered and no two even numbered elements are identical.
(iv) A 2DFA with S, states can have valid crossing sequence of length atmost 25.
Which of the above statements, try to illustrate the same point?
- (a)
(i) and (iii)
- (b)
(ii) and (iv)
- (c)
(i), (ii) and (iii)
- (d)
(iii) and (iv)