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)
In every string at a language can be determined, whether it is legal or illegal in finite time, the language is called
- (a)
intractable
- (b)
undecidable
- (c)
decidable
- (d)
non-deterministic
Let R1 and R2 be regular sets defined over the alphabet \( { \Sigma }_{ i }\) then
- (a)
\({ R }_{ 1 }\cap { R }_{ 2 }\quad \) is not regular
- (b)
\({ R }_{ 1 }\cup { R }_{ 2 }\quad \)is regular
- (c)
\(\Sigma -{ R }_{ 1 }\) is regular
- (d)
\({ R }_{ 1 }\) is regular
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
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)\)
Nin-recursively enumerable languages are accepted by
- (a)
finite automaton with memory
- (b)
turing machine
- (c)
finite automaton
- (d)
None of the above
Which is the correct order of the given grammars from most restrictive to most general?
- (a)
Recursively enumerable, context free, context sensitive, regular
- (b)
Regular, context free, context sensitive, recursively enumerable
- (c)
Recursively enumerable, context sensitive, context free , regular
- (d)
Regular, context sensitive, context free , recursively enumerable
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)
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
\(\Rightarrow Z=\{ { a }^{ m }{ b }^{ n }/m\quad \ge ,\quad n\ge 1\} \) is regular as only for ambn can be constructed from DFA. In all other given languages there is a comparsion between number of a's and number of b's which cannot be designed by DFA.
Which of the following regular expression over {0,1} denotes the set of all strings not containing 100 as a sub-string?
- (a)
0*(1+0)*
- (b)
0*1010*
- (c)
0*1*01
- (d)
0*(10+1)*
For regular expression 0*(1+0)*,(1+0)* contains all strings over 1 and 0 which will contains string 100 also.
For regular expression
0*1010* \(\Rightarrow \) 0*10102 \(\Rightarrow \) 0*10100
The regular expression 0* 1* 01 does not contains all strings over 1 and 0.
Which of the following sets can be recognized by a deterministic finite state automation?
- (a)
The number 1,2,4,8,...2n .... which in binary
- (b)
The number 1,2,4,...2n written in unary
- (c)
The set of binary string in which the number of zero is the same as the number of ones
- (d)
The set {1,101,11011,1110111}
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
The string 0101010011 can be generated having regular expression 0*(10*10*)* 10*
\(\quad \quad \quad 0'(10*\quad 10*)^{ 2 }10*\\ \Rightarrow \quad 0(10*\quad 10*)\quad (10*\quad 10*)1\\ \Rightarrow \quad 0(1010)({ 10 }^{ 2 }1\wedge )1\\ \Rightarrow \quad 0101010011\)
The string 111100 11 11 00 111 can be generated using same regular expression as
\(\quad \quad \quad 0*(10*9\quad 10*)^{ 4 }10*\\ \Rightarrow \quad \wedge (10*10*)^{ 4 }1.\wedge \\ \Rightarrow \quad (10*\quad 10*)^{ 4 }1\\ \Rightarrow \quad (10*\quad 10*)(10*\quad 10*)(10*\quad 10*)(10*\quad 10*).1\\ \Rightarrow \quad 11(1110*)(11)(110*)1\\ \Rightarrow \quad 11\quad 11\quad 00\quad 11\quad 11\quad 00\quad 1\)
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
The language of PDA is
- (a)
context sensitive language
- (b)
context-free language
- (c)
regular language
- (d)
None of the above
The set {anbn/n=1,2,...} can be generated by which of the following CFC's?
(1) S->ab/aSb
(2) S->aaSbb/ab
(3) \(S->ab/aSb/\in \)
(4) S->aaSbb/ab/aabb
- (a)
1 and 4
- (b)
2 only
- (c)
2 and 4
- (d)
3 only
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,...}
The minimum set generated by the grammar S->aa S bb/ab is ab
S->aa S bb/ab a2n+1b2n+1 n=0
S->aa aa S bb bb/aa ab bb a3 b3 \(\Rightarrow \) a2n+1b2n+1 for n=1
S-> aa aa aa S bbbbbb/aaaaaa bbbbbbb- a2n+1b2n+1 n=3
a2n+1b2n+1 /n=0,1,2,3,....}
The reduced grammar equivalent to the grammar whose productions are
S->AB/CA
B->BC/AB
A->a
C->aB/b
- (a)
S->CA, A->a, C->b
- (b)
S->CA/B, B->BC/B, A->a, C->aB/b
- (c)
A->A(B/C),B->B(C/A),A->a,C->aB/b
- (d)
None of these
\({ \omega }_{ 0 }=\{ A,C\} \\ { \omega }_{ 1 }\Rightarrow \{ S,A,C\} \\ { \omega }_{ 2 }\Rightarrow \{ S,A,C\} \\ { P }^{ ' }\Rightarrow \{ S->CA,A->a,C->b\} \\ { \omega }_{ 0 }^{ ' }\Rightarrow \{ S\} \\ { \omega }_{ 0 }^{ ' }\Rightarrow \{ S,A,C\} \\ { \omega }_{ 2 }^{ ' }\Rightarrow \{ S,A,C\} \\ { P }^{ '' }\Rightarrow \{ S->cA,A->a,C->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
S->aB/bA
S->ab/abS/aaBB/ba/baS/bbAA/ab,ab
S->ab/abaB/abbA/aabSbS/aaa BB a BB
->ab/abab/abba/aabb/aabbabba/aaabbabb
We can see in all strings number of a's = Number of b's
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
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
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 \)
Language represented by the grammar \(S\rightarrow 00F,F\rightarrow 11S/11\) is described by
- (a)
(0011)*
- (b)
(00(11)*)*
- (c)
(0011)*
- (d)
(00+11)*
The language generated by grammar
\(S\rightarrow 00F\\ F\rightarrow 11S/11\)
String will be generated as
\(S\rightarrow 00F\)
\(\rightarrow \) 0011 S/0011
\(\rightarrow \) 001100 F
\(\rightarrow \) 00110011 S/00110011
\(\rightarrow \) 0011001100 F
\(\rightarrow \) 001100110011 S/001100110011
Means the language generated is
0011, 00110011, 001100110011....
\(\Rightarrow \) (0011)*
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)
In the given language \({ L }_{ 1 }={ XCX }^{ R }/x\epsilon L\), there is 1 comparison that xR should be reversed of x. Thus the language cannot be implemented by DFA. Hence, it is not a regular language.
For language \({ L }_{ 2 }=\left\{ { XCY }^{ R }/x,y\epsilon L \right\} \)there is no comparison between elements. So it is a regular language.
Which of the following is/are true?
\((i)\quad \left( \left( { \left( 01 \right) }^{ * }{ \left( 10 \right) }^{ * } \right) \cap \left( { \left( 10 \right) }^{ * }{ \left( 01 \right) }^{ * } \right) \right) =\left\{ \epsilon \right\} \\ (ii)\quad \left( { 01 }^{ * }{ 10 }^{ * } \right) \cap \left( { 10 }^{ * }01 \right) =\left\{ \epsilon \right\} \\ { (ii)\quad \left( { 0 }^{ * }{ 1 }^{ * }1 \right) }^{ * }\cap { \left( { 1 }^{ * }0^{ * }0 \right) }^{ * }=\left\{ \epsilon \right\} \)
- (a)
All
- (b)
Only (i)
- (c)
Only (iii)
- (d)
(ii) and (iii)
One string generated by regular expression \({ \left( 01 \right) }^{ * }{ \left( 10 \right) }^{ * }\)is 101010 (putting (01)*=\(\wedge \))
The same string can be generated by R \(\epsilon \) \({ \left( 10 \right) }^{ * }{ \left( 01 \right) }^{ * }\) (by putting (01)*=\(\wedge \))
Thus,
\({ \left( 01 \right) }^{ * }{ \left( 10 \right) }^{ * }\cap { \left( 10 \right) }^{ * }{ \left( 01 \right) }^{ * }\neq \left\{ \epsilon \right\} \)
The string in regular expression 01*10* will always start from 0 but the string in regular expression 10*01 will always start from 1. Thus, no common string would be in both regular expressions. Thus \(\left( { 01 }^{ * }{ 10 }^{ * } \right) \cap \left( { 10 }^{ * }01 \right) =\left\{ \epsilon \right\} \).
Consider the following
\((i)\quad { \left( { a }^{ * }b \right) }\cup \left( { ba }^{ * } \right) ={ \left( a+b \right) }^{ * }\\ (ii)\quad { \left( \left( { a }^{ * }{ b }^{ * } \right) +\left( { b }^{ * }{ a }^{ * } \right) \right) }^{ * }={ \left( a+b \right) }^{ * }\\ (iii)\quad { { \left( { \left( ab \right) }^{ * }+{ \left( ba \right) }^{ * } \right) } }^{ * }={ \left( a+b \right) }^{ * }\)
Which of the above statements are true?
- (a)
None
- (b)
(ii) and (iii)
- (c)
(i) and (ii)
- (d)
Only (ii)
\({ \left( { a }^{ * }b \right) }^{ * }\cup { \left( { ba }^{ * } \right) }^{ * }\)
\(\Rightarrow \quad { \left( { \left( b \right) }^{ * }+{ a }^{ * }b+{ ba }^{ * } \right) }^{ * }\)
Here, we can see that either the string contains \(\wedge \)or atleast 1 b but for regular expression (a+b)* the string (a)* can also be generated. Thus,
\({ \left( { a }^{ * }b \right) }^{ * }\cup { \left( { ba }^{ * } \right) }^{ * }\neq { \left( a+b \right) }^{ * }\)
\({ \left( \left( { a }^{ * }{ b }^{ * } \right) +\left( { b }^{ * }{ a }^{ * } \right) \right) }^{ * }\)
\(\left( { a }^{ * }+{ b }^{ * }+{ a }^{ * }{ b }^{ * }+{ b }^{ * }+{ a }^{ * }+{ b }^{ * }{ a }^{ * } \right) ={ \left( a+b \right) }^{ * }\)
\(\Rightarrow { \quad \left( \left( { a }^{ * }{ b }^{ * } \right) +\left( { b }^{ * }{ a }^{ * } \right) \right) }^{ * }={ \left( a+b \right) }^{ * }\\ \quad \quad \quad { \left( { \left( ab \right) }^{ * }+\left( ba \right) \right) }^{ * }={ \left( ab+ba \right) }^{ * }\)
\({ \left( ab+ba \right) }^{ * }\) does not contain the string (a)* thus \({ { \left( ab+ba \right) }^{ * } }^{ * }\neq { \left( a+b \right) }^{ * }\)
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
\(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
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