THEORY OF COMPUTATION MCQ SET 1

This entry was posted in THEORY OF COMPUTATION MCQ on by
1 Let R1 and R2 be regular sets defined over alphabet ∑ then

(a.) R1 UNION R2 is regular
(b.) R1 INTERSECTION R2 is regular
(c.) ∑ INTERSECTION R2 IS NOT REGULAR
(d.) R2* IS NOT REGULAR
2

Consider the production of the grammar S->AA A->aa A->bb Describe the language specified by the production grammar.

(a.) L = {aaaa,aabb,bbaa,bbbb}
(b.) L = {abab,abaa,aaab,baaa}
(c.) L = {aaab,baba,bbaa,bbbb}
(d.) L = {aaaa,abab,bbaa,aaab}
3 Give a production grammar that specified language L = {ai b2i >= 1}

(a.) {S->aSbb,S->abb}
(b.) {S->aSb, S->b}
(c.) {S->aA,S->b,A->b}
(d.) None of the above
4 Which of the following String can be obtained by the language L = {ai b2i / i >=1}

(a.) aaabbbbbb
(b.) aabbb
(c.) abbabbba
(d.) aaaabbbabb
5 Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.

(a.) {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}
(b.) {S->aS,S->bA,A->bB,B->bBa,B->bB}
(c.) {S->aaS,S->bbA,A->bB,B->ba}
(d.) None of the above
6 The production Grammar is {S->aSbb,S->abb} is

(a.) type-3 grammar
(b.) type-2 grammar
(c.) type-1 grammar
(d.) type-0 grammar
7 Which of the following statement is wrong?

(a.) A Turing Machine can not solve halting problem.
(b.) Set of recursively enumerable languages is closed under union.
(c.) A Finite State Machine with 3 stacks is more powerful than Finite State Machine with 2 stacks
(d.) Context Sensitive grammar can be recognized by a linearly bounded memory machine.
8 Which of the following statement is wrong ?

(a.) Recursive languages are closed under union.
(b.) Recursive languages are closed under complementation.
(c.) If a language and its complement are both regular then the language must be recursive.
(d.) A language is accepted by FA if and only if it is recursive
9 Which of the following statement is wrong ?

(a.) Every recursive language is recursively enumerable
(b.) A language is accepted by FA if and only if it is context free.
(c.) Recursive languages are closed under intersection
(d.) A language is accepted by a FA if and only if it is right linear.
10 Which of the following statement is true ?

(a.) All languages can be generated by CFG
(b.) The number of symbols necessary to simulate a Turing Machine(TM) with m symbols and n states is mn.
(c.) Any regular languages has an equivalent CFG.
(d.) The class of CFG is not closed under union.
11 Recursively enumerable languages are not closed under

(a.) Complementation
(b.) Union
(c.) Intersection
(d.) None of the above
12 Regular expression (x/y)(x/y) denotes the set

(a.) {xy,xy}
(b.) {xx,xy,yx,yy}
(c.) {x,y}
(d.) {x,y,xy}
13 Regular expression x/y denotes the set

(a.) {x,y}
(b.) {xy}
(c.) {x}
(d.) {y}
14 The regular expression denote a language comprising all possible strings of even length over the alphabet (0,1)

(a.) 1 + 0(1+0)*
(b.) (0+1)(1+0)*
(c.) (1+0)
(d.) (00+0111+10)*
15 The regular expressions denote zero or more instances of an x or y is

(a.) (x+y)
(b.) (x+y)*
(c.) (x* + y)
(d.) (xy)*
16 The regular expression have all strings in which any number of 0′s is followed by any number of 1′s followed by any number of 2′s is :

(a.) (0+1+2)*
(b.) 0*1*2*
(c.) 0* + 1 + 2
(d.) (0+1)*2*
17 The regular expression have all strings of 0′s and 1′s with no two consecutive 0′s is :

(a.) (0+1)
(b.) (0+1)*
(c.) (0+∈) (1+10)*
(d.) (0+1)* 011
18 The regular expression with all strings of 0′s and 1′s with atleast two consecutive 0′s, is :

(a.) 1 + (10)*
(b.) (0+1)*00(0+1)*
(c.) (0+1)*011
(d.) 0*1*2*
19 Which of the following is NOT the set of regular expression R = (ab + abb)* bbab

(a.) ababbbbab
(b.) abbbab
(c.) ababbabbbab
(d.) abababab
20 Which string can be generated by S->aS/bA, A->d/ccA

(a.) aabccd
(b.) adabcca
(c.) abcca
(d.) abababd
21 The regular sets are closed under

(a.) Union
(b.) Concenteration
(c.) Kleen closure
(d.) All of the above
22 Which of the following statement is wrong ?

(a.) the regular sets are closed under intersection
(b.) the class of regular sets is closed under substitution
(c.) The class of regular sets is closed under homomorphism
(d.) Context Sensitive Grammar(CSG) can be recognized by Finite State Machine
23 A FSM can be considered, having finite tape length without rewinding capability and unidirectional tape movement

(a.) Turing machine
(b.) Pushdown automata
(c.) Context free languages
(d.) Regular languages
24 Any given transition graph has an equivalent

(a.) regular
(b.) DFSM (Deterministic Finite State Machine)
(c.) NDFSM
(d.) All of them
25 The intersection of CFL and regular languages

(a.) is always regular
(b.) is always context-free
(c.) both option 1 and option 2 above
(d.) need not be regular

Leave a comment