1. The minimum number of states required to automate the following Regular Expression:
(1) *(01+10) (1) *
a) 4
b) 3
c) 2
d) 5
View Answer
a) addition of new state
b) removal of a state
c) make the newly added state as final
d) more than one option is correct
View Answer
Explanation: If there is more than one accepting state or if the single accepting state as an out degree , add a new accepting state, make all other states non accepting, and hold an e-transitions from each former accepting state to the new accepting state.
a) Perl
b) Java
c) Python
d) C++
View Answer
Explanation: 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. Regular expression F* is equivalent to
a) ?
b) F
c) 0
d) 1
View Answer
Explanation : None.
5. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
a) L1<L2
b) L1>=L2
c) L1 U L2 = .*
d) L1=L2
View Answer
Explanation : Finite state machine and regular expression have same power to express a language.
6. Which of the following are not quantifiers?
a) Kleene plus +
b) Kleene star *
c) Question mark ?
d) None of the mentioned
View Answer
Explanation: 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 among the following is not a tool to construct lexical analyzer from a regular expression?
a) lex
b) flex
c) jflex
d) none of the mentioned
View Answer
Explanation: Lexical analysis is done using few tools such as lex, flex and jflex. Jflex is a computer program that generates lexical analyzers (also known as lexers or scanners) and works apparently like lex and flex. Lex is commonly used with yacc parser generator.
8. A program that performs lexical analysis is termed as:
a) scanner
b) lexer
c) tokenizer
d) all of the mentioned
View Answer
Explanation: A program which performs lexical analysis is called lexer, scanner or lexer. Nowadays, lexer is combined with a parser which allows syntactic analysis.
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
View Answer
Explanation: 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.
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: In automata theory, the Myphill Nerode theorem provides a necessary and sufficient condition for a language to be regular. The Myphill Nerode theorem can be used to show a language L is regular by proving that the number of equivalence classes of RL(relation) is finite.
a) Pumping Lemma
b) Myphill Nerode
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: On the contrary, the typical way to prove that a language is to construct either a finite state machine or a regular expression for the language.
a) Start with a DFA Ain L
b) Construct a DFA B for h-1(L)
c) The set of states, initial and final states should be same.
d) All of the mentioned
View Answer
Explanation: While constructing DFA B, we need to take care of the following:
a) The same set of states
b) The same start state
c) The same final state
d) Input alphabet = the symbols to which homomorphism h applies.
13. Is the following statement correct?
Statement: Thompson construction is used to convert Regular expression to finite automata.
a) Yes
b) No
View Answer
Explanation: Thompson’s Construction is used to find out a Finite Automaton from a Regular Expression. We will reduce the regular expression into smallest regular expressions and convert them to NFA and finally to DFA.
14. If a DFA has n states and the language contains any string of length n or more, the language is termed as:
a) Infinite
b) Empty
c) Non regular
d) None of the mentioned
View Answer
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5
View Answer
Explanation: A->aA=>aaA=>aab
