MCQ Computer Science

# Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-30

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

2. If we have more than one accepting states or an accepting state with an outdegree, which of the following actions will be taken?
b) removal of a state
c) make the newly added state as final
d) more than one option is correct

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.

3. Which of the following languages have built in regexps support?
a) Perl
b) Java
c) Python
d) C++

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

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

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

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

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

Explanation: A program which performs lexical analysis is called lexer, scanner or lexer. Nowadays, lexer is combined with a parser which allows syntactic analysis.

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

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.

10. Myphill Nerode does the following:
a) Minimization of DFA
b) Tells us exactly when a language is regular
c) Both (a) and (b)
d) None of the mentioned

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.

11. Which of the following can refer a language to be non regular?
a) Pumping Lemma
b) Myphill Nerode
c) Both (a) and (b)
d) None of the mentioned

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.

12. While proving Inverse Homomorphism, which of the following steps are needed?
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

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

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

Answer: The language is surely finite if it is limited to string of length n or less. This is because there are atleast n+1 states along the path while traversing w(string).

15. A->aA| a| b
The number of steps to form aab:
a) 2
b) 3
c) 4
d) 5