1:the word “formal” in formal language means
(a)the symbols used have well-defined meaning (b) they are unnecessary, in reality (c) only the form of the string of symbols is significant (d)none of these
2:Let A={0,1}. The number of possible strings of length “n” that can be formed by the element of the set A is
(a)n! (2) n2 (c) nn (d) 2n
3: choose the correct statements.
(a)Moore and mealy machines are FSM with output capability.
(b) any given Moore machines has an equivalent Mealy machine .
(c)any give mealy machine has an equivalent Moore Machine .
(d) Moore machine is not an FSM.
4: the major difference between a Moore and a Mealy Machine is that
(a)the output of the former depend on the present state and current input
(b)the output of the former depend only on the present state
(c)the output of the former depend only on the current state
(d)none of the above
5:Choose the correct statements.
(a)A mealy machine generates no language as such.
(b)A moore machine generates no language as much
(c)a mealy machine has no terminal state
6:the recognizing capability of NDFSM and DFSM
(a)may be different (b)must be different (c)must be same (d)none of the above
7:FSM can recognize
(a)any grammar (b)only CFG (c) any unambiguous grammar (d)only regular grammar
8:pumping lemma is generally use for proving
(a)a given grammar is regular
(b)a given grammar is not regular
(c)whether two given regular expression are equivalent (d)none of the above
9:which of the following are not regular ?
(a)string of 0 is wholes length is perfect square.
(b)set of all palindromes made up of 0 and s.
(c)string of 0 is whose length is prime number .
(d)string of odd number of zeroes
10:which of the following pairs of regular expressions are equivalent ?
(a)1(01)* and (10)*1 (b) x(xx)* and (xx)* x (c) (ab)* and a*b* (d)x* and x*x*
12:pick the correct statements.
The logic of pumping lemma is good example of
(a)the pigeon hole principle (b)the divide and conquer technique
(c)recursion (d)iteration
13:the basic limitation of an FSM is that
(a)it can’t remember arbitrary large amount of information
(b)it sometimes recognized grammar that are not regular
(c)it sometimes fails to recognized grammars that are regular
(d)all of the above
14:palindromes can’t be recognized by any FSM because
(a)an FSM can’t remember arbitrary large amount of information
(b)an FSM can’t deterministically fix the mid point
(c)even if the midpoint is known an FSM can’t find whether the second half of the string matches the first half (d) none of these
16:TM is more powerful than FSM because
(a)the tape movement is confined to one direction (b) it has no finite state control
(c)it has the capability to remember arbitrary long sequence of input symbols.
(d) none of the above
19:the above machine
(a)complements a given bit pattern (b)generates all string of 0 and 1
(c)adds 1 to a given bit pattern (d)none of the above
20:the language of all words (made up of a’s and b’s)with at least two a’s can be describe by the regular expression
(a)(a+b)*a(a+b)*a(a+b)* (b) (a+b)*ab*a(a+b)*
(c)b*ab*a(a+b)* (d) a(a+b)* a(a+b)* (a+b)*
21:which of the following pairs of regular expression are not equivalent ?
(a)(ab)*a and a(ba)* (b) (a+b)* and (a*+b)*
(c)(a*+b)* and (a+b)* (d) none of the above
23:set of regular language over a given alphabets set, is not closed under
(a)union (b)complementation (c)intersection (d)none of the above
25:forwich of the following application regular expressions can’t be used?
(a)Designing compilers (b)Developing text editor
(c)simulating sequential circuits (d)Designing computers
27:any given transition graph has an equivalent
(a)regular expression (b) DFSM (c)NDFS (d)none of the above
32:the set {anbn |n=1,2,3……..}can be generated by the CFG
(a)s→ab |aSb (b)S→aaSbb | ab (c)S→ab |aSb (d)S→aaSb |ab|aabb
33:Choose the correct statement.
(a)all image can be generated by cfg
(b) any regular language has an equivalent cfg
(c) some none regular language can’t be generated by any cfg
(d) some regular language can’t be generated by any cfg
34: which of the following cfg can’t be simulated by an FSM?
(a)S→Sa| a (b)S→abX X→cY Y→d |aX
(c)S→aSb |ab (d) None of the above
35:CFG is not closed under
(a) union (B) kleene star (c)complementation (d)product
36: the set A = {an bn an|n=1,2,3….} is an example of the grammar that is
(a) regular (b) context free (c) not context free
(D) none of the above
38:L= {an bn an|n=1,2,3….} is an example of the language that is
(a) context-free (b) not context free (c) not context free but whose complement is CF
(d)context free but whose complement is not CF
39:The intersection of a CFL and a regular language
(a)need not be regular (b) need not be context free (c)is always regular (d)is always CF
40:A PDM behave like a FSM when the number of auxiliary memory is memory it has is
(a) zero (b) 1 (c) 2 or more (d) the none of the above
41: a EDM behave like a TM when the number of auxiliary memory it has is
(a) Zero (b) 1 0r more (c) 2 or more D none of the above
42: who is the correct statement (a) the power off the DFSM andNDFSM are the same (B) the power of the DFSM and NDFSM are different
(C) the power of the DPDM and NDPDM are difference (D)the power of the DPDM and NDPDM are the same
43: which of the following is accepted by NDSDM but not by a DPDM?
all strings in which a symbol is present at the least at least twice
even palindrome (c) strings ending with a particular terminal (d)the none of the above
44:CFG can be recognized by a
(a)FSM (b) DPDM (c)NDPDM (d) linearly bounded memory machine 46:choose the correct statement
(a) an FSM with 2 stack is as powerful as a TM
(b) FSM and NDFSM have the same power (c) A DFSM with 1 state and an SFSM with one state have the same power (d) ADFM with 2 Steak and an DSM DTU with 2 Steak have the same power
47: Bounded minimalization is a technique for
(a)proving whether a update primitive recursive function is turning computable (b) proving whether a primitive recursive function is a total function (C) generating the primitive recursive functions (d) generated up partial recursive function
48: which of the following is not primitive recursive but come but computable (a)carnot function (b)Riemann function (C) bounded function (d) Ackermann function
49: which of the following is not primitive
(a)carnot function (b)Riemann function (C) bounded function (d) Ackermann function
50:choose the correct statement
(a)total recursive function is also up or partial recursive function (b) a partial recursive function is also a total recursive function (c) a partial recursive function is also a primitive recursive function (d)a primitive recursive function is also referred shell partial recursive function
51: a language L for which there exist a TM,T, that accept every world in L and either reject or loops for every that is not in L is said to be
(a) recursively (b)recursively enumerable (c) NP-hard (d)none of the above
53: use the correct statement
(a) set of recursively enumerable is closed under (b)if a language and its complement or both regular, then the regular must be recursive (C) recursive language are closed under the complementation (d) none of the above
54: pick the correct answer
Universal TM launched influenced the concept of
(a)stored-program computer (b) interpretive implementation of the programming language (C) computable (d) none of the above
55: The number of internal state of ATM should be at least
(a)1 (b) 2 (c) 3 (d) 4
56: the number of the symbol necessary to simulate TM with m symbols and n statement is
(a) m + n (b) 8 m n + 4 m (C) mn (d) 4mn+m
57: any TM with m symbol and n state can be simulated by any other TM with just 2 symbol and less than
(a) 8mn state (b) 4 m n + 8 state (c) mn (d)mn + 4 state the MS state
59: if there exist a TM which when applied to any problem in the class terminated if the correct answer is yes and may or may not terminate otherwise is said to be
(a)stable (b) unsolvable (C) partially solvable (d) unstable
62: let p, q, and R be three language if p and r regular and if PQ= r, then
(a)Q has to be regular (b) Q cannot be regular (c) Q need not be regular (d) Q has to be a CFL
64: choose the correct statement a class of language that is closed under
(a) Union and complementation has to be closed under the intersection (b) intersection and the complementation has to be closed under union (c) Union and intersection has to be closed under complementation (d)the all of the above
70: an fsm can be used to add two given integer,this remarks is
(a) true (B) false (c) may be true (d) none of the above
71: A CFG is said to be in chomsky normal form (cfg) if all the production of the form X the number of production to be used is
(a) 2x -1 (b) 2 x (c)2 X + 1 (d) 2
