# 100+MCQS of Automata theory with Answers | NTS | PTS |CTSCSS 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

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 