Automata Theory Multiple Choice Questions on “Finding Patterns in Text,Algebric Laws and Derivatives”.
1. The minimum length of a string {0,1}* not in the language corresponding to the given regular expression:
(0*+1*)(0*+1*)(0*+1*)
a) 3
b) 4
c) 5
d) 6
Answer: b
Clarification: 0101 or 1010 the strings with minimum length on {0,1}* which does not belong to the language of the given regular expression.Other strings like 111, 000, 1101, etc are accepted by the language .
2. Which of the following regular expression is equivalent to R(1,0)?
R(1,0)={111*}*
a) (11+111)*
b) (111+1111)*
c) (111+11*)*
d) All of the mentioned
Answer: a
Clarification: What we observe from the question is that, it includes e and 11 and any number of 1’s then. Therefore, its simplifies when we write the same reg. Expression as (11+111)*.
3. The minimum number of 1’s to be used in a regular expression of the given language:
R(x): The language of all strings containing exactly 2 zeroes.
a) 2
b) 3
c) 0
d) 1
Answer: b
Clarification: It is not required to automate the question if asked theoretically.The number of zeroes fixed is 2. Therefore, we can represent the regular expression as 1*01*01*.
4. The given regular language corresponds to which of the given regular language
e+1+(1+0)*0+(0+1)*11
a) The language of all strings that end with 11 or 00
b) The language of all strings that end with 0 or 1
c) The language of all strings which does not end with 01
d) None of the mentioned
Answer: c
Clarification: According to the given regular expression, e is accepted by its language and it does not end with 00 or 11 or 0 or 1. Thus option a and b are eliminated. Further, the regular expression is valid for the third option.
5. Statement: If we take the union of two identical expression, we can replace them by one copy of the expression.
Which of the following is a correct option for the given statement?
a) Absorption Law
b) Idempotent Law
c) Closure Law
d) Commutative Law
Answer: b
Clarification: Idempotent Law states that if we take the union of two like expression, we can use a copy of the expression instead i.e. L+L=L. The common arithmetic operators are not idempotent.
6. Which among the following can be an annihilator for multiplication operation?
a) 0
b) 1
c) 100
d) 22/7
Answer: a
Clarification: 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.
7. Statement: A digit, when used in the CFG notation, will always be used as a terminal.
State true or false?
a) True
b) False
Answer: a
Clarification: Lowercase letters near the beginning of an alphabet, a, b and so on are terminal symbols. We shall also assume that digits and other characters such as + or parenthesis are terminals.
8. Choose the incorrect process to check whether the string belongs to the language of certain variable or not?
a) recursive inference
b) derivations
c) head to body method
d) All of the mentioned
Answer: d
Clarification: There are two approaches to infer that certain string are in the language of a certain variable. The most conventional way is to use the rules from body to head, recursive inference. The second approach is expanding the starting variable using one of its productions whose head is tart symbol and derive a string consisting entirely of terminals(head to body or derivations).
9. Statement: Left most derivations are lengthy as compared to Right most derivations.
Choose the correct option:
a) correct statement
b) incorrect statement
c) may or may not be correct
d) depends on the language of the grammar
Answer: c
Clarification: It completely depends on the person who develops the grammar of any language, how to make use of the tools i.e. leftmost and rightmost derivations.
10. A->aAa|bAb|a|b|e
Which among the following is the correct option for the given production?
a) Left most derivation
b) Right most derivation
c) Recursive Inference
d) None of the mentioned
Answer: a