1.Language recognized by finite automata is:
(a) Type 0
(b) Type 1
(c) Type 2
(d) Type 3
Answer:
Option (d)2.Finite automata require minimum _______ number of stack.
(a) 0
(b) 1
(c) 2
(d) 3
Answer:
Option (a)3.Which of the following are an application of Finite Automaton?
(a) Compiler Design
(b) Grammar Parsers
(c) Text Search
(d) All of the mentioned
Answer:
Option (d)4.FA has _______
(a) Unlimited Memory
(b) No memory at all
(c) Limited memory
(d) None
Answer:
Option (c)5.Limitations of finite state machine (FA) can overcome by:
(a) Push down automata
(b) Turing machine
(c) Both A and B
(d) None of these
Answer:
Option (c)6.A finite automata accepts:
(a) Any Language
(b) Regular Language
(c) Context Free Language
(d) Context Sensitive Language
Answer:
Option (b)7.A language is regular if and only if it is accepted by finite automata:
(a) The given statement is true
(b) Given statement is false
(c) Statement is partially true
(d) None of the mentioned
Answer:
Option (a)8.Which of the following is a not a part of 5-tuple finite automata?
(a) Input alphabet
(b) Transition function
(c) Output Alphabet
(d) Initial State
Answer:
Option (c)9.Regular grammar is a subset of __________ grammar
(a) Type 0
(b) Type 1
(c) Type 2
(d) Type 0,1,2
Answer:
Option (d)10.Statement: Any regular language can be accepted by a finite automaton is:
(a) Arden’s Theorem
(b) Kleene’s Theorem
(c) Rice Theorem
(d) None of these
Answer:
Option (b)11. If ∑ = a t h e n ∑ * =
(a) {^, a, aa,…..}
(b) {^ , a , aa}
(c) {^}
(d) {a, aa,…..}
Answer:
Option (a)12.Which of the following regular expression identity is true?
(a) (r+s)*=r*
(b) (r+s)*= r*+s*
(c) (r*s*)*=(r+s)*
(d) r* s*= r *+s*
Answer:
Option (c)13.Regular expression for all strings starts with ab and ends with bba is.
(a) aba*b*bba
(b) ab(a+b)*bba
(c) ab(ab)*bba
(d) All of the mentioned
Answer:
Option (b)14.Given the language L = {ab, aa, baa}, which of the following strings are in L*?
(a) abaabaaabaa
(b) aaaabaaaa
(c) baaaaabaa
(d) All of these
Answer:
Option (d)15. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
(a) The set of all strings containing the substring 00
(b) The set of all strings containing at most two 0’s.
(c) The set of all strings containing at least two 0’s
(d) The set of all strings that begin and end with either 0 or 1.
Answer:
Option (c)16.Regular expression for even length string:
(a) (0|1)(0|1)*
(b) (0|1)*
(c) (0|1)(0|1)(0|1)*
(d) (00|11|10|01)*
Answer:
Option (d)17.Reverse of (0+1)* will be
(a) Null
(b) (0+1)
(c) (0+1)*
(d) (0+1)(0+1)*
Answer:
Option (c)18.Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1's?
(a) 0 * 10 * 10 *
(b) 0 * 110 *
(c) (0 + 1) * 11(0 + 1) *
(d) (0 + 1) * 1(0 + 1) * 1 (0 + 1) *
Answer:
Option (a)19.The string 1101 does not belong to the set represented by
(a) 110* (0+1)
(b) (00+(11)*0)*
(c) 1(0+1)* 101
(d) (11)* (01)* (00+11)*
Answer:
Option (b)20.Regular expression for all binary string with at least 3 characters and 3rd character should be zero
(a) (0|1) (0|1)0(0|1)
(b) (0|1) (0|1)0(0|1)*
(c) (0|1)* (0|1)(0|1)0
(d) (0|1) (0|1)0*
Answer:
Option (b)21.What is the language generated by this regular expression? a(a+b)*a
(a) Always starts with b
(b) Can have any number of ba and ab
(c) Cannot have 2 b's together.
(d) Starts and end with same symbol
Answer:
Option (d)22.In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?
(a) (L + D) *
(b) (L.D) *
(c) L(L + D) *
(d) L(L.D) *
Answer:
Option (c)23.The regular expression corresponding to the language L where L = { x ϵ {0, 1}*|x ends with 1 and does not contain substring 00 } is:
(a) (1 + 01) * (1 + 01)
(b) (1 + 01) * 01
(c) (1 + 01) * (10 + 01)
(d) (10 + 01) * 01
Answer:
Option (a)24.(a + b*c) most correctly represents:
(a) (a +b) *c
(b) (a + (b*)).c
(c) (a)+((b)*.c)
(d) a+ ((b*).c)
Answer:
Option (b)25.If r and s are two regular expression then expression r+s is:
(a) Regular expression
(b) Regular language
(c) Union
(d) None of these
Answer:
Option (a)26.The finite automata is called NFA when there exists________ for a specific input from current state to next state
(a) Single path
(b) Multiple paths
(c) Only two paths
(d) None
Answer:
Option (b)27.Number of states require to accept string ends with 10
(a) 1
(b) 2
(c) 3
(d) Can’t be represented
Answer:
Option (c)28.There are ________ tuples in finite state machine (FA).
(a) 4
(b) 5
(c) 6
(d) Unlimited
Answer:
Option (b)29.Extended transition function is:
(a) `Q * ∑^* rightarrow Q`
(b) `Q * ∑ rightarrow Q`
(c) `Q * *∑^* rightarrow ∑`
(d) `Q * ∑^* rightarrow ∑`
Answer:
Option (a)30. Transition function of FA maps:
(a) `∑ * Q rightarrow ∑`
(b) `Q * Q rightarrow ∑`
(c) `∑ * ∑ rightarrow Q`
(d) `Q * ∑ rightarrow Q`
Answer:
Option (d)31.The transitional function of a NFA is
(a) `Q X ∑ rightarrow Q`
(b) `Q X ∑ rightarrow 2^Q`
(c) `Q X ∑ rightarrow 2^n`
(d) `Q X ∑ rightarrow Qn`
Answer:
Option (b)32.`delta*(q,ya)` is equivalent to:
(a) `delta`((q,y),a)
(b) `delta`(q,ya)
(c) `delta`(*(q,y),a)
(d) independent from notation
Answer:
Option (c)33.String X is accepted by finite automata if :
(a) `delta*(q,x) varepsilon A`
(b) `delta(q,x) varepsilon A`
(c) `delta(Q_0,x) varepsilon A`
(d) `delta*(Q_0,x) varepsilon A`
Answer:
Option (d)34.`Phi` in minimal finite automata need _____________ no. of final states
(a) 1
(b) 2
(c) 3
(d) None
Answer:
Option (d)35.What is the relation between DFA and NFA on the basis of computational power?
(a) DFA > NFA
(b) NFA > DFA
(c) Equal
(d) Can’t be said
Answer:
Option (c)36. Subset Construction method used for:
(a) Conversion of NFA to DFA
(b) DFA minimization
(c) Eliminating Null references
(d) ε-NFA to NFA
Answer:
Option (a)37.Which method is useful to convert from regular expression to NFA?
(a) Subset Construction Method
(b) Power Set Construction Method
(c) Thompson's Rule
(d) Scott Construction Method
Answer:
Option (c)38.Every NFA accepts a:
(a) String
(b) Regular language
(c) Function
(d) Context-free language
Answer:
Option (b)39.An NFA’s transition function returns
(a) A state
(b) A Boolean value
(c) An edge
(d) A set of states
Answer:
Option (d)40.The relation between NFA-accepted languages and DFA accepted languages is
(a) >
(b) <
(c) =
(d) <=
Answer:
Option (c)41.Which is true for Dead State?
(a) If control enters no way to come out from the state
(b) There is no necessity of the state
(c) It cannot be reached anytime
(d) If control enters FA dead
Answer:
Option (a)42.Both NFA and ^-NFA recognize exactly the same languages.
(a) True
(b) False
(c) May be
(d) Can't say
Answer:
Option (a)43.Which of the following conversion is not feasible?
(a) Regular expression to automaton conversion
(b) Automaton to Regular Expression Conversion
(c) NFA to DFA
(d) None of the mentioned
Answer:
Option (d)44.It is less complex to prove the closure properties over regular languages using:
(a) NFA
(b) DFA
(c) PDA
(d) Can’t be said
Answer:
Option (a)45.A Language for which no DFA exist is a______
(a) Regular Language
(b) Non-Regular Language
(c) May be regular
(d) Can’t decide
Answer:
Option (b)46.A DFA can be represented in the following format
(a) Transition graph
(b) Transition Table
(c) C code
(d) All of the mentioned
Answer:
Option (d)47.Can a DFA recognize a palindrome number?
(a) Yes
(b) No
(c) Yes, with input alphabet as ∑*
(d) Can’t be determined
Answer:
Option (b)48.L = { x ϵ ∑ = ( 0 , 1 ) | x = `0^ n 1^ n` f o r n > = 1 }
Can there be a DFA possible for the language?
(a) Yes
(b) No
(c) May be
(d) Can’t be determined
Answer:
Option (b)49.Two finite state machines are said to be equivalent if they:
(a) Have the same number of edges
(b) Have the same number of states
(c) Recognize the same set of tokens
(d) Have the same number of states and edges
Answer:
Option (c)50.In Mealy Machine O/P is associated with
(a) Present state
(b) Transition
(c) Next state
(d) None of the above
Answer:
Option (b)51.In Moore Machine O/P is associated with
(a) Present state
(b) Input
(c) Next state
(d) None of the above
Answer:
Option (a)52.Moore Machine is an application of:
(a) Finite automata without input
(b) Non- Finite automata with output
(c) Finite automata with output
(d) None of the mentioned
Answer:
Option (c)53.For a give Moore Machine, Given Input=’101010’, thus the output would be of length:
(a) |Input|+1
(b) |Input-1|
(c) |Input|
(d) Cannot be predicted
Answer:
Option (a)54.Null string is accepted in Moore Machine:
(a) Yes
(b) No
(c) Can’t say
(d) May be
Answer:
Option (a)55.The output alphabet can be represented as:
(a) `delta`
(b) `∑`
(c) `triangle`
(d) None of the mentioned
Answer:
Option (c)56. The major difference between Mealy and Moore machine is about:
(a) Input Variations
(b) Output Variations
(c) Both
(d) None of the mentioned
Answer:
Option (b)57.The appropriate precedence order of operations over a Regular Language is
(a) Kleene, Union, Concatenate
(b) Kleene, Star, Union
(c) Kleene, Concatenate, Union
(d) Star, Union, Dot
Answer:
Option (c)58.Which of the technique can be used to prove that a language is non regular?
(a) Pumping Lemma
(b) Arden’s theorem
(c) Ogden’s Lemma
(d) Thompson's rule
Answer:
Option (a)59.While applying Pumping lemma over a language, we consider a string x that belong to L and fragment it into _________ parts.
(a) 2
(b) 5
(c) 3
(d) 6
Answer:
Option (c)60.If we select a string w such that x∈L, and x= x=uvw. Which of the following portions cannot be an empty string?
(a) u
(b) v
(c) w
(d) all of the mentioned
Answer:
Option (b)61.There exists a language L. We define a string w such that x∈L and x=uvw and |x| >=n for some constant integer n. What can be the maximum length of the substring uv i.e. |uv|<=?
(a) n
(b) |v|
(c) |u|
(d) none of the mentioned
Answer:
Option (a)62.Answer in accordance to the third and last statement in pumping lemma: For all _______ `x y^ i z ∈ L`
(a) i>0
(b) i<0
(c) i<=0
(d) i>=0
Answer:
Option (d)63.NFA is not closed under:
(a) Union
(b) Intersection
(c) Concatenation
(d) None of the mentioned
Answer:
Option (d)64.If L1′ and L2′ are regular languages, then L1.L2 is:
(a) Regular
(b) May be regular
(c) Non regular
(d) Context free
Answer:
Option (a)65.Which of following is regular?
(a) String of 0’s whose length is a perfect square
(b) Strings of 0’s, whose length is prime number.
(c) Set of all palindromes made up of 0’s and 1’s.
(d) Strings of odd number of zeros.
