Computer Science and Information Technology - Theory of Computation
Exam Duration: 45 Mins Total Questions : 30
Consider the following language:
(i) {0n / n} is a prime?
(ii) The set of all strings that do not have 3 consecutive 0's
Which of the above languages is/are regular sets?
- (a)
None of these
- (b)
Only (i)
- (c)
Only (ii)
- (d)
Both (i) and (ii)
State which of the following statements is true?
(1)For any unrestricted grammar G, there is a Turing machine T with L(T)=L(G)
(2)Every recursive language is recursively enumerable
(3)If L1 and L2 are recursively enumerable languages over \(\sum,\)y then L1 \(\cap\)L2 and L1\(\cup\) L2 are also recursively enumerable.
- (a)
Only (1) is true
- (b)
Only (2) is true
- (c)
All are false
- (d)
None of these
Let r=1(1+0)*,S=11*0 and t=1*0 be three regular expressions.Which are of the following is true?
- (a)
\(L(s)\subseteq L(r)andL(s)\subseteq (t)\)
- (b)
\(L(r)\subseteq L(s)andL(s)\subseteq (t)\)
- (c)
\(L(s)\subseteq L(t)andL(s)\subseteq (r)\)
- (d)
\(L(t)\subseteq L(s)andL(s)\subseteq (r)\)
Which of the following regular expression identifies is true?
- (a)
r(*)=r*
- (b)
(r*s*)*=(r+s)*
- (c)
(r*+s*)=(r+s)*
- (d)
r*s*=r*+s*
Which of the following definitions below generates the same language as L, where L{xnyn such that \(n\ge 1\} \) ?
(i) E->xEy/xy
(ii) xy/x+xyy+
(iii) x+y+
- (a)
i only
- (b)
i and (ii)
- (c)
(ii) and (iii)
- (d)
(ii) only
Nin-recursively enumerable languages are accepted by
- (a)
finite automaton with memory
- (b)
turing machine
- (c)
finite automaton
- (d)
None of the above
Let \(\Sigma =\{ 0,1\} ,L={ \Sigma }^{ * }\)and \(R=\{ { 0 }^{ n }\} ^{ n } \)such that n>0 } then languages \( L\cup R and R \) respectively
- (a)
regular, regular
- (b)
non-regular,regular
- (c)
regular,non-regular
- (d)
non-regular,non-regular
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
Consider the following languages:
\({ L }_{ 1 }=\{ \omega \omega /\omega \in \{ a,b\} *\} \\ { L }_{ 2 }=\{ \omega { \omega }^{ R }/\omega \in \{ a,b\} *{ \omega }^{ R },\quad is\quad the\quad reverse\quad of\quad \omega \} \\ { L }_{ 3 }=\{ { 0 }^{ 2i }/\quad i\quad is\quad an\quad integer\} \\ { L }_{ 4 }=\{ { 0 }^{ 2i }/\quad i\quad is\quad an\quad integer\} \)
Which of the following is regular?
- (a)
L1 and L 2
- (b)
L2,L3 and L 4
- (c)
L3 and L4
- (d)
Only L3
Consider the following two statements:
\({ S }_{ 1 }:\{ { 0 }^{ 2n }/n\ge 1\} \quad is\quad a\quad regular\quad language\\ { S }_{ 2 }:\{ { 0 }^{ 3 }/\quad { 1 }^{ n }{ 0 }^{ m+n }/m\ge 1\quad and\quad n\ge 1\} \quad is\quad a\quad regular\quad language\)
Which of the following statements is correct?
- (a)
Only S1 is correct
- (b)
Only S2 is correct
- (c)
Both S1 and S2 are correct
- (d)
Neither S1 nor S2 is correct
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
Consider the regular expression
r=0*(10*10*)10*
Which of the following are not valid strings?
(1) 0101010011
(2) 1111001111001
(3) 0011001100111
- (a)
Cannot be determined
- (b)
Only 1
- (c)
Only 2
- (d)
None of these
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
The language of PDA is
- (a)
context sensitive language
- (b)
context-free language
- (c)
regular language
- (d)
None of the above
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,...}
If G={{S},{a},S,{S->{SS}} find the language generated by G.
- (a)
L(G)=a*
- (b)
L(G)=a+
- (c)
\(L(G)=\phi \)
- (d)
Both (a) and (b)
The following context-free grammer
S->aB/bA
A->a/aS/bAA
B->b/bS/aBB
generates the string of terminals that have
- (a)
odd number a's and even number of a's
- (b)
even number of a's and even number of b's
- (c)
odd number of a's and odd number of b's
- (d)
equal number of a's and b's
Consider the grammar G:
S->AB
A->\(aAA/\in \)
B->\(bBB/\in \)
If G1 is constructed from G after eliminating the null productors, then G1 is given by
- (a)
S->AB, A->aAA/aAa, B->bBB/b
- (b)
S->AB/A/B, A->aAA/aA/a, B->bBB/bB/b
- (c)
S->AB/A/B, A-?aAA,/aA, B->bBB/bB
- (d)
S->AB, A->aAA/aA, B->bBB/bB
Which two of the following four regular expressions are equivalent?(E is empty string)
(i) 00* (E+0)
(ii) (00)*
(iii)0*0*
(iv) 0(00)*
- (a)
(i) and (ii)
- (b)
(ii) and (iii)
- (c)
(iii) and (iv)
- (d)
(i) and (iii)
Consider the following two statements:
(i) It is possible to construct an NFA with more number of states then its equivalent DFA.
(ii)There can be a DFA with more than one start state choose the correct option.
- (a)
Both are false
- (b)
Only (i) is false
- (c)
Only (ii) if false
- (d)
Both are true
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
Let A be language represented by regular expression (m+n)* and B be language represented by the regular expression (m+n*)* which of the following is true?
- (a)
A=B
- (b)
\(A\subset B\)
- (c)
\(B\subset A\)
- (d)
\(A\cap B=\phi \)
L={\(\omega \) the number of consecutive 1's in \(\omega \) is 0 or a multiple of 4}
L is represented by which of the following regular expressions?
- (a)
\({ \left( { \left( 1111+1 \right) }^{ * }{ 0 }^{ * } \right) }^{ * }\)
- (b)
\({ \left( 1111+10+0 \right) }^{ * }\)
- (c)
\({ \left( { 111 }^{ * }+{ 10 }^{ * } \right) }^{ * }\)
- (d)
\({ 0 }^{ * }{ \left( 111+1 \right) }^{ * }{ 0 }^{ * }\)
L is a regular set. Now, consider the following languages
\((i){ L }_{ 1 }=\left\{ { XCX }^{ R }/x\epsilon L \right\} \\ (ii){ L }_{ 2 }=\left\{ { XCY }^{ R }/x,y\epsilon L \right\} \)
Which of the above languages is/are regular?
- (a)
None
- (b)
Only (i)
- (c)
Only (ii)
- (d)
Both (i) and (ii)
Consider the regular expression R = (ab/abb)* bbab, which of the following is not in the set denoted by R?
- (a)
ababab
- (b)
abbbab
- (c)
abbabbbab
- (d)
ababbabbaab
Which of the following represent(s) the set of all strings over {0, 1} ending with 00 and beginning with 1?
(i) 1 (0* + 1*) 00
(ii) 1 (0* + 1*)* 00
(iii) 1 (0 + 1)* 00
- (a)
Only (i)
- (b)
Only (ii)
- (c)
Both (ii) and (iii)
- (d)
Only (iii)
L=language of all turing machine that accepts nothing which of the following is correct?
- (a)
L is recursively enumerable
- (b)
LC is recursively enumerable
- (c)
L is recursive
- (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)