INTERVIEW QUS ON AUTOMATA

 

                             

.

	INTERVIEW QUS ON AUTOMATA
1	There are ________ tuples in the finite state machine.
	a)4	b)5
	c)6	d)Unlimited
2	Transition function maps.
	a)Σ * Q → Σ	b)Q * Q→Σ
	c)Σ * Σ → Q	d)Q * Σ → Q
3	Number of states required to accept string ends with 10.
	a)3	b)2
	c)1	d)Can’t be determined
4	δ*(q,ya) is equivalent to .
	a)δ((q,y),a)	b)δ(δ*(q,y),a)
	c)δ(q,ya)	d)independent from δ notation
5	An automaton that presents output based on previous state or current input is called
	a)Acceptor	b)Classifier
	c)Transducer	d)None of the mentioned
6	If NFA of 6 states excluding the initial state is converted into DFA, the maximum possible number of states for the DFA is
	a)62	b)32
	c)128	d)127
7	NFA, in its name has ’non-deterministic’ because of :
	a)The result is undetermined	b)The choice of path is non-deterministic
	c)The state to be transited next is non-deterministic	d)All of the mentioned
8	Which of the following is the correct proposition? Statement 1: Non determinism is a generalization of Determinism. Statement 2: Every DFA is automatically an NFA
	a)Statement 1 is correct because Statement 2 is correct	b)Statement 2 is correct because Statement 2 is correct
	c)Statement 2 is false and Statement 1 is false	d)Statement 1 is false because Statement 2 is false
9	Given Language L= {xϵ {a, b}*|x contains aba as its substring}Find the difference of transitions made in constructing a DFA and an equivalent NFA?
	a)2	b)3
	c)4	d)Cannot be determined.
10	If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?
	a)1/m2	b)2m
	c)1/m	d)log m
11	Which of the following statement is correct?
	a)NFA is slower to process and its representation uses more memory than DFA	b)DFA is faster to process and its representation uses less memory than NFA
	c)NFA is slower to process and its representation uses less memory than DFA	d)DFA is slower to process and its representation uses less memory than
12	Which among the following is not notated as infinite language?
	a)Palindrome	b)Reverse
	c)Factorial	d)L={ab}*
13	Moore Machine is an application of:
	a)Finite automata without input	b)Finite automata with output
	c)Non- Finite automata with output	d)None of the mentioned
14	Which of the given statement are correct?
	a)Moore machine has 6-tuples	b)Mealy machine has 6-tuples
	c)Both Mealy and Moore has 6-tuples	d)None of the mentioned
15	The major difference between Mealy and Moore machine is about:
	a)Output Variations	b)Input Variations
	c)Both Output Variations and Input Variations	d)None of the mentioned
16	Which of the following does not represent the given language? Language: {0,01}
	a)0+01	b){0} U {01}
	c){0} U {0}{1}	d){0} ^ {01}
17	Which among the following looks similar to the given expression? ((0+1). (0+1)) *
	a){xϵ {0,1} *|x is all binary number with even length}	b){xϵ {0,1} |x is all binary number with even length}
	c){xϵ {0,1} *|x is all binary number with odd length}	d){xϵ {0,1} |x is all binary number with odd length}
18	Concatenation Operation refers to which of the following set operations:
	a)Union	b)Dot
	c)Kleene	d)Two of the options are correct
19	RR* can be expressed in which of the forms:
	a)R+	b)R-
	c)R+ U R-	d)R
20	Which of the following statements is not true?
	a)Every language defined by any of the automata is also defined by a regular expression	b)Every language defined by a regular expression can be represented using a DFA
	c)Every language defined by a regular expression can be represented using NFA with e moves	d)Regular expression is just another representation for any automata definition
21	The minimum number of transitions to pass to reach the final state as per the following regular expression : {a,b}*{baaa} is:
	a)4	b)5
	c)6	d)9
22	If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?
	a)x	b)y
	c)z	d)all of the mentioned
23	Which of the following is a utility of state elimination phenomenon?
	a)DFA to NFA	b)NFA to DFA
	c)DFA to Regular Expression	d)All of the mentioned
24	A language is regular if and only if(Probable duplicate)
	a)accepted by DFA	b)accepted by PDA
	c)accepted by LBA	d)accepted by Turing machine
25	The behaviour of NFA can be simulated using DFA.
	a)always	b)never
	c)sometimes	d)none of the mentioned
26	Regular grammar is
	a)context free grammar	b)non context free grammar
	c)english grammar	d)None of these
27	Which of the following is not a regular expression?
	a)[(a+b)*-(aa+bb)]*	b)[(0+1)-(0b+a1)*(a+b)]*
	c)(01+11+10)*	d)(1+2+0)*(1+2)*
28	Regular expression are
	a)Type 0 language	b)Type 1 language
	c)Type 2 language	d)Type 3 language
29	Which of the following statement is false?
	a)Context free language is the subset of context sensitive language	b)Regular language is the subset of context sensitive language
	c)Recursively enumerable language is the super set of regular language	d)Context sensitive language is a subset of context free language
30	Which among the following cannot be accepted by regular grammar?
	a)L is a set of numbers divisible by 2	b)L is a set of binary complement
	c)L is a set of string with odd number of 0	d)L is a set of 0n1n
31	The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
	a)3	b)7
	c)5	d)6
32	The language accepted by Push down Automaton:
	a)Recursive Language	b)Context free language
	c)Linearly Bounded language	d)All of the mentioned
33	Which of the following are distinct to parse trees?
	a)abstract parse trees	b)sentence diagrams
	c)both abstract parse trees and sentence diagrams	d)none of the mentioned
34	A CFG is not closed under
	a)Dot operation	b)Union Operation
	c)Concatenation	d)Iteration
35	A push down automaton employs ________ data structure.
	a)Queue	b)Linked List
	c)Hash Table	d)Stack
36	A non-deterministic two way, nested stack automaton has n-tuple definition. State the value of n.
	a)5	b)8
	c)4	d)10
37	Which among the following is not a part of the Context free grammar tuple?(Probable duplicate)
	a)End symbol	b)Start symbol
	c)Variable	d)Production
38	Which of the following automata takes stack as auxiliary storage?
	a)Finite automata	b)Push down automata
	c)Turing machine	d)None of these
39	Halting states are of two types. They are:
	a)Accept and Reject	b)Reject and Allow
	c)Start and Reject	d)None of these
40	Every grammar in Chomsky Normal Form is:
	a)regular	b)context sensitive
	c)context free	d)all of the mentioned
41	Which of the functions are not performed by the turing machine after reading a symbol?
	a)writes the symbol	b)moves the tape one cell left/right
	c)proceeds with next instruction or halts	d)none of the mentioned
42	The value of n if turing machine is defined using n-tuples:
	a)6	b)7
	c)8	d)5
43	RASP stands for:
	a)Random access storage program	b)Random access stored program
	c)Randomly accessed stored program	d)Random access storage programming
44	A turing machine that is able to simulate other turing machines:
	a)Nested Turing machines	b)Universal Turing machine
	c)Counter machine	d)None of these
45	A turing machine with several tapes in known as:
	a)Multi-tape turing machine	b)Poly-tape turing machine
	c)Universal turing machine	d)All of these
46	Which of the following is not a Non deterministic turing machine?
	a)Alternating Turing machine	b)Probabilistic Turing machine
	c)Read-only turing machine	d)None of these
47	Finite languages trivially satisfy the pumping lemma by having n = ________, where p is the maximum string length in L.
	a)p*1	b)p+1
	c)p-1	d)None of the mentioned
48	Which of the following is not a step to eliminate state procedure?
	a)Unifying all the final states into one using e-transitions	b)Unify single transitions to multi transitions that contains union of input
	c)Remove states until there is only starting and accepting states	d)Get the resulting regular expression by direct calculation
49	The entity which generates language called-
	a)Automata	b)Tokens
	c)Grammar	d)Data
50	Which of the following is/are most suitable approaches for inference?
	a)Recursive Inference	b)Derivations
	c)Both Recursive Inference and Derivations	d)None of the mentioned

.