Automata Theory Multiple Choice Questions on “Converting Regular Expressions to Automata”.
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: c
Clarification: 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: d
Clarification: 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: a
Clarification: 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: c
Clarification: 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: a
Clarification: 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: d
Clarification: 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: d
Clarification: 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: c
Clarification: () 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 'd\n'.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: c
Clarification: 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: a
Clarification: 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.