Multiple choice question for engineering
Set 1
1. The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
Answer
Answer: c [Reason:] The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.
2. Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Ennumerable Language
Answer
Answer: c [Reason:] Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.
3. 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 ennumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
Answer
Answer: d [Reason:] Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on.
4. The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
Answer
Answer: b [Reason:] G=(V, ∑, p, S), here V=Finite set of variables, ∑= set of terminals, p= finite productions, S= Starting Variable.
5. Which among the following cannot be accepted by a 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
Answer
Answer: d [Reason:] There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.
6. Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
Answer
Answer: c [Reason:] According to the definition, the starting variable can produce another variable or any terminal or a variable which leads to terminal.
7. For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
Answer
Answer: d [Reason:] L={e, 01, 0011, 000111, ……0n1n }. As epsilon is a part of the set, thus all the options are correct implying none of them to be wrong.
8. 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
Answer
Answer: c [Reason:] The grammar which produces a palindrome set can be written as:
S-> aSa | bSb | e | a | b
L={e, a, b, aba, abbbaabbba…..}
9. Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
Answer
Answer: a [Reason:] Regular grammar is a subset of context free grammar and thus all regular grammars are context free.
10. Are ambiguous grammar context free?
a) Yes
b) No
Answer
Answer: a [Reason:] A context free grammar G is ambiguous if there is atleast one string in L(G) which has two or more distinct leftmost derivations.
Set 2
1. What kind of expressions do we used for pattern matching?
a) Regular Expression
b) Rational Expression
c) Regular & Rational Expression
d) None of the mentioned
Answer
Answer: c [Reason:] In automata theory, Regular Expression(sometimes also called the Rational Expression ) is a sequence or set of characters that define a search pattern, mainly for the use in pattern matching with strings or string matching.
2. Which of the following do Regexps do not find their use in?
a) search engines
b) word processors
c) sed
d) none of the mentioned
Answer
Answer: d [Reason:] Regexp processors are found in several search engines, seach and replace mechanisms, and text processing utilities.
3. Which of the following languages have built in regexps support?
a) Perl
b) Java
c) Python
d) C++
Answer
Answer: a [Reason:] Many languages come with built in support of regexps like Perl, Javascript, Ruby etc. While some provide support using standard libraries like .NET, Java, Python, C++, C and POSIX.
4. The following is/are an approach to process a regexp:
a) Contruction of NFA and subsequently, a DFA.
b) Thompson’s Contruction Algorithm
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] A regexp processor translates the syntax into internal representation which can be executed and matched with a string and that internal representation can have several approaches like the ones mentioned.
5. Are the given two patterns equivalent?
(1) gray|grey
(2) gr(a|e)y
a) yes
b) no
Answer
Answer: a [Reason:] Paranthesis can be used to define the scope and precedence of operators. Thus, both the expression represents the same pattern.
6. Which of the following are not quantifiers?
a) Kleene plus +
b) Kleene star *
c) Question mark ?
d) None of the mentioned
Answer
Answer: d [Reason:] A quantifier after a token specifies how often the preceding element is allowed to occur. ?, *, +, {n}, {min, }, {min, max} are few quantifiers we use in regexps implementations.
7. Which of the following cannot be used to decide whether and how a given regexp matches a string:
a) NFA to DFA
b) Lazy DFA algorithm
c) Backtracking
d) None of the mentioned
Answer
Answer: d [Reason:] There are at least three algorithms which decides for us, whether and how a regexp matches a string which included the transformation of Non deterministic automaton to deterministic finite automaton, The lazy DFA algorithm where one simulates the NFA directly, building each DFA on demand and then discarding it at the next step and the process of backtracking whose running time is exponential.
8. What does the following segment of code output?
$string1 = "Hello Worldn"; if ($string1 =~ m/(H..).(l..)/) { print "We matched '$1' and '$2'.n"; }
a) We matched ‘Hel’ and ‘ld’
b) We matched ‘Hel’ and ‘lld’
c) We matched ‘Hel’ and ‘lo ‘
d) None of the mentioned
Answer
Answer: c [Reason:] () groups a series of pattern element to a single element.
When we use pattern in parenthesis, we can use any of ‘$1’, ‘$2’ later to refer to the previously matched pattern.
9. Given segment of code:
$string1 = "HellonWorldn"; if ($string1 =~ m/dnz/) { print "$string1 is a string "; print "that ends with 'dn'.n"; }
What does the symbol /z does?
a) changes line
b) matches the beginning of a string
c) matches the end of a string
d) none of the mentioned
Answer
Answer: c [Reason:] It matches the end of a string and not an internal line.The given segment of code outputs:
Hello
World
is a string that ends with ‘dn’
10. Conversion of a regular expression into its corresponding NFA :
a) Thompson’s Construction Algorithm
b) Powerset Construction
c) Kleene’s algorithm
d) None of the mentioned
Answer
Answer: a [Reason:] Thompson construction algorithm is an algorithm in automata theory used to convert a given regular expression into NFA. Similarly, Kleene algorithm is used to convert a finite automaton to a regular expression.
Set 3
1. The transition a Push down automaton makes is additionally dependent upon the:
a) stack
b) input tape
c) terminals
d) none of the mentioned
Answer
Answer: a [Reason:] A PDA is a finite machine which has an additional stack storage. Its transitions are based not only on input and the correct state but also on the stack.
2. A PDA machine configuration (p, w, y) can be correctly represented as:
a) (current state, unprocessed input, stack content)
b) (unprocessed input, stack content, current state)
c) (current state, stack content, unprocessed input)
d) none of the mentioned
Answer
Answer: a [Reason:] A machine configuration is an element of K×Σ*×Γ*.
(p,w,γ) = (current state, unprocessed input, stack content).
3. |-* is the __________ closure of |-
a) symmetric and reflexive
b) transitive and reflexive
c) symmetric and transitive
d) none of the mentioned
Answer
Answer: b [Reason:] A string w is accepted by a PDA if and only if (s,w, e) |-* (f, e, e)
4. With reference of a DPDA, which among the following do we perform from the start state with an empty stack?
a) process the whole string
b) end in final state
c) end with an empty stack
d) all of the mentioned
Answer
Answer: d [Reason:] The empty stack in the end is our requirement relative to finite state automatons.
5. A DPDA is a PDA in which:
a) No state p has two outgoing transitions
b) More than one state can have two or more outgoing transitions
c) Atleast one state has more than one transitions
d) None of the mentioned
Answer
Answer: a [Reason:] A Deterministic Push Down Automata is a Push Down Automata in which no state p has two or more transitions.
6. State true or false:
Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.
a) true
b) false
Answer
Answer: a [Reason:] There exists two lemma’s such that:
a) Given a grammar G, construct the PDA and show the equivalence
b) Given a PDA, construct a grammar and show the equivalence
7. If the PDA does not stop on an accepting state and the stack is not empty, the string is:
a) rejected
b) goes into loop forever
c) both (a) and (b)
d) none of the mentioned
Answer
Answer: a [Reason:] To accept a string, PDA needs to halt at an accepting state and with a stack empty, else it is called rejected. Given a PDA M, we can construct a PDA M’ that accepts the same language as M, by both acceptance criteria.
8. A language accepted by Deterministic Push down automata is closed under which of the following?
a) Complement
b) Union
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: a [Reason:] Deterministic Context free languages(one accepted by PDA by final state), are drastically different from the context free languages. For example they are closed under complementation and not union.
9. Which of the following is a simulator for non deterministic automata?
a) JFLAP
b) Gedit
c) FAUTO
d) None of the mentioned
Answer
Answer: a [Reason:] JFLAP is a software for experimenting with formal topics including NFA, NPDA, multi-tape turing machines and L-systems.
10. Finite-state acceptors for the nested words can be:
a) nested word automata
b) push down automata
c) ndfa
d) none of the mentioned
Answer
Answer: a [Reason:] The linear encodings of languages accepted by finite nested word automata gives the class of ‘visibly pushdown automata’.
Set 4
1. The password to the admins account=”administrator”. The total number of states required to make a password-pass system using DFA would be __________
a) 14 states
b) 13 states
c) 12 states
d) A password pass system cannot be created using DFA
Answer
Answer: a [Reason:] For a string of n characters with no repetitive substrings, the number of states required to pass the string is n+1.
2. Which of the following is the corresponding Language to the given DFA?
a) L= {x ϵ {0, 1} * | x ends in 1 and does not contain substring 01}
b) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 00}
c) L= {x ϵ {0,1} |x ends in 1 and does not contain substring 00}
d) L= {x ϵ {0,1} * |x ends in 1 and does not contain substring 11}
Answer
Answer: b [Reason:] The Language can be anonymously checked and thus the answer can be predicted. The language needs to be accepted by the automata (acceptance state) in order to prove its regularity.
3. Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:
a) {Hello, World, Input, Output, ε}
b) {Hello, World, ε}
c) {Input, Output, ε}
d) {}
Answer
Answer: d [Reason:] Union operation creates the universal set by combining all the elements of first and second set while intersection operation creates a set of common elements of the first and the second state.
4. Let the given DFA consist of x states. Find x-y such that y is the number of states on minimization of DFA?
a) 3
b) 2
c) 1
d) 4
Answer
Answer: b [Reason:] Use the equivalence theorem or Myphill Nerode theorem to minimize the DFA.
5. For a machine to surpass all the letters of alphabet excluding vowels, how many number of states in DFA would be required?
a) 3
b) 2
c) 22
d) 27
Answer
Answer: a [Reason:]
6. For the DFA given below compute the following:
Union of all possible combinations at state 7,8 and 9.
a) {aba, ac, cc, ca, cb, bc, bab, ca}
b) {bab, bc, ac, aba, ca, aac, ccb}
c) {cc, ca, cb, aba, bab, ac}
d) {aba, ac, cc, ca, cb, bc, bab, caa}
Answer
Answer: d [Reason:] The string a state receives is the combination of all input alphabets which lie across the path covered.
7. Given L= {Xϵ∑*= {a, b} |x has equal number of a, s and b’s}.
Which of the following property satisfy the regularity of the given language?
a) Regularity is dependent upon the length of the string
b) Regularity is not dependent upon the length of the string
c) Can’t be said for a particular string of a language
d) It may depend on the length of the string
Answer
Answer: b [Reason:] DFA can be made for infinite language with an infinite length. Thus, dependency over length is unfruitful.
8. Given:
L= {xϵ∑= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?
a) Yes
b) No
Answer
Answer: b [Reason:] It is not possible to have a count of equal number of 0 and 1 at any instant in DFA. Thus, It is not possible to build a DFA for the given Language.
9. δ(A,1) = B, δ(A,0) =A
Δ (B, (0,1)) =C
δ(C,0) = A (Initial state =A)
String=”011001” is transit at which of the states?
a) A
b) C
c) B
d) Invalid String
Answer
Answer: a [Reason:] It is east and simple to create the table and then the corresponding transition graph in order to get the result, at which state the given string would be accepted.
Set 5
1. Which of the following is same as the given DFA?
a) (0+1)*001(0+1)*
b) 1*001(0+1)*
c) (01)*(0+0+1)(01)*
d) None of the mentioned
Answer
Answer: a [Reason:] There needs to be 001 together in the string as an essential substring. Thus, the other components can be anything, 0 or 1 or e.
2. 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
Answer
Answer: b [Reason:] Using NFA with e moves, we can represent all the regular expressions as an automata. As regular expressions include e, we need to use e moves.
3. The total number of states required to automate the given regular expression
(00)*(11)*
a) 3
b) 4
c) 5
d) 6
Answer
Answer: c [Reason:] 
4. Which of the given regular expressions correspond to the automata shown?
a) (110+1)*0
b) (11+110)*1
c) (110+11)*0
d) (1+110)*1
Answer
Answer: c [Reason:] There is no state change for union operation, but has two different paths while for concatenation or dot operation, we have a state change for every element of the string.
5. Generate a regular expression for the following problem statement:
Password Validation: String should be 8-15 characters long. String must contain a number, an Uppercase letter and a Lower case letter.
a) ^(?=.*[a-z])(?=.*[A-Z])(?=.*d).{8,15}$
b) ^(?=.*[a-z])(?=.*[A-Z])(?=.*d).{9,16}$
c) ^(?=.[a-z])(?=.[A-Z])(?=.d).{8,15}$
d) None of the mentioned
Answer
Answer: a [Reason:] Passwords like abc123, 123XYZ, should not be accepted . If one also wants to include special characters as one of the constraint, one can use the following regular expression:
^(?=.*[a-z])(?=.*[A-Z])(?=.*d)(?=.*[^da-za-Z]).{8,15}$
6. Generate a regular expression for the following problem statement:
P(x): String of length 6 or less for å={0,1}*
a) (1+0+e)6
b) (10)6
c) (1+0)(1+0)(1+0)(1+0)(1+0)(1+0)
d) More than one of the mentioned is correct
Answer
Answer: a [Reason:] As the input variables are under Kleene Operation, we need to include e,thus option c is not correct,thereby option (a) is the right answer.
7. The minimum number of states required in a DFA (along with a dumping state) to check whether the 3rd bit is 1 or not for |n|>=3
a) 3
b) 4
c) 5
d) 1
Answer
Answer: c [Reason:] 
8. Which of the regular expressions corresponds to the given problem statement:
P(x): Express the identifiers in C Programming language
l=letters
d=digits
a) (l+_)(d+_)*
b) (l+d+_)*
c) (l+_)(l+d+_)*
d) (_+d)(l+d+_)*
Answer
Answer: c [Reason:] Identifiers in C Programming Language follows the following identifiers rule:
a) The name of the identifier should not begin with a digit.
b) It can only begin with a letter or a underscore.
c) It can be of length 1 or more.
9. Generate a regular expression for the given language:l
L(x): {xÎ{0,1}*| x ends with 1 nd does not contain a substring 01}
a) (0+01)*
b) (0+01)*1
c) (0+01)*(1+01)
d) All of the mentioned
Answer
Answer: c [Reason:] (a) and (b) are the general cases where we restrict the acceptance of a string witrh substring 00 but we ignore the case where the string needs to end with 1 which therby, does not allows the acceptance of e.
10. The minimum number of transitions to pass to reach the final state as per the following regular expression is:
{a,b}*{baaa}
a) 4
b) 5
c) 6
d) 3
Answer
Answer: a [Reason:] 
Total Views: 13
