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
View Answer
Explanation: 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.
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned
View Answer
Explaination : None.
a) / */
b) /bl
c) /^?/
d) /^$/
View Answer
Explanation: There are few expressions which provide the utility of matching metacharacters including /^$/ for blank lines, / */ for matching one or more spaces, /^.*$/ for matching an entire line whatever it is.
4. State true or false:
Statement: A lexical analyzer reads the source code line by line.
a) True
b) False
View Answer
Explanation: A lexical analyzer reads the source code letter by letter and when it encounters a space or an operator or any special character, it decides that the word is completed.
a) Non regular
b) DFA-regular
c) Non-finite
d) None of the mentioned
View Answer
Explanation: This is a simple example of a closure property: a property saying that the set of DFA-regular languages is closed under certain operations.
a) 0
b) 1
c) 100
d) 22/7
View Answer
Explanation: An annihilator for an operator is a value such that when the operator is applied to the annihilator and some other value, the result is the annihilator.
For all _______ xyiz ?L
a) i>0
b) i<0
c) i<=0
d) i>=0
View Answer
Explanation: Suppose L is a regular language . Then there is an integer n so that for any x?L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ?L.
8. Which of the following is not an application of Pumping Lemma?
a) {0i1i|i>=0}
b) {0ix|i>=0, x?{0, 1}* and |x|<=i}
c) {0n| n is prime}
d) None of the mentioned
View Answer
Explanation: None of the mentioned are regular language and are an application to the technique Pumping Lemma. Each one of the mentioned can be proved non regular using the steps in Pumping lemma.
9. If L is a regular language, then (((L’)r)’)* is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer
Explanation: If L is regular so is its complement, if L’ is regular so is its reverse, if (L’)r is regular so is its Kleene.
10. Which of the following is a correct statement?
a) Moore machine has no accepting states
b) Mealy machine has accepting states
c) We can convert Mealy to Moore but not vice versa
d) All of the mentioned
View Answer
Explanation: Statement a and b is correct while c is false. Finite machines with output have no accepting states and can be converted within each other.
A mealy machine
a) produces a language
b) produces a grammar
c) can be converted to NFA
d) has less circuit delays
View Answer
Explanation: It does not produce a language or a grammar or can be converted to a NFA.
12. 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
View Answer
Explanation: The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0, this condition needs to be fulfilled to check the conclusion condition.
13. Pigeonhole principle can be applied in the following computer science algorithms:
a) hashing algorithm
b) lossless compression algorithm
c) both (a) and (b)
d) none of the mentioned
View Answer
Explanation: Collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array.
a) Union
b) Intersection
c) Complement
d) All of the mentioned
View Answer
Explanation: Regular languages are closed under the following operations:
a) Regular expression operations
b) Boolean operations
c) Homomorphism
d) Inverse Homomorphism
a) Lr
b) L’
c) L*
d) All of the mentioned
View Answer
Explanation: Lr, L’, L* i.e. reversal, complementation and kleene all are the closure properties of regular language.
