MCQ Computer Science

Automata Theory Multiple Choice Question & Answers (MCQs) set-10

1. Which of the following is an utility of state elimination phenomenon?
a) DFA to NFA
b) NFA to DFA
c) DFA to Regular Expression
d) All of the mentioned

View Answer

Answer: c
Explanation: We use this algorithm to simplify a finite automaton to regular expression or vice versa. We eliminate states while converting a given finite automata to its corresponding regular expression.

2. Regular expression {0,1} is equivalent to
a) 0 U 1
b) 0 / 1
c) 0 + 1
d) All of the mentioned

View Answer

Answer : d
Explanation : All are equivalent to union operation.

3. A language is regular if and only if
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine

View Answer

Answer : a
Explanation : All of above machine can accept regular language but all string accepted by machine is regular only for DFA.

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

View Answer

Answer: c
Explanation: 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. What does grep do in UNIX?
a) It is an editor in UNIX
b) It searches for text patterns
c) Both (a) and (b)
d) None of the mentioned

View Answer

Answer: b
Explanation: The grep is a standard UNIX utility program that searches through a set of files in search of a text pattern,specified through a regular expression.

6. The output of the lexical and syntax analyzer can stated as:
a) parse stream, parse tree
b) token tree, parse tree
c) token stream, parse tree
d) all of the mentioned

View Answer

Answer: c
Explanation: The lexical analyzer outputs the stream of token which is taken up by syntax analyzer one by one against the production rule and parse tree is generated.

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

View Answer

Answer: a
Explanation: 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. Which of the following are related to tree automaton?
a) Myphill Nerode Theorem
b) State machine
c) Courcelle’s Theorem
d) All of the mentioned

View Answer

Answer: d
Explanation: The myphill nerode theorem can be generalized to trees and an application of tree automata prove an algorithmic meta theorem about graphs.

9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does these variables represent?
a) string count
b) string
c) both (a) and (b)
d) none of the mentioned

View Answer

Answer: a
Explanation: Given: w =xyz. Here, xyz individually represents strings or rather substrings which we compute over conditions to check the regularity of the language.

10. Which of the following is not an example of counting argument?
a) Pigeonhole principle
b) Dirichlet’s drawer principle
c) Dirichlet’s box principle
d) None of the mentioned

View Answer

Answer: d
Explanation: Pigeon hole principle or Dirichlet’s drawer principle or Dirichlet’s box principle is an example of counting argument whose field is called Combinatorics.

11. 8. Let h(0)=ab; h(1)=e
Let L={abab,baba}
h-1(L)= the language of two zeroes and any number of one’s.
The given example belongs to which of the following?
a) Homomorphism
b) Inverse Homomorphism
c) Both (a) and (b)
d) None of the mentioned

View Answer

Answer: b
Explanation: Let h be a homomorphism and L a language whose alphabet is the output language of h.
h-1(L) = {w | h(w) is in L}.

12. The computation of e-closure of n-states takes ______ time.
a) O(n2)
b) O(n3)
c) O(2n)
d) None of the mentioned

View Answer

Answer: b
Explanation: We must search from each of the n states along all arcs labelled e. If there are n states, there can be no more than n2 states.

13. Pick the odd one out of the given properties of a regular language:
a) Kleene
b) Reversal
c) Homomorphism
d) Membership

View Answer

Answer: d
Explanation: Membership is a decision property of language class while others mentioned like Kleene, Reversal and Homomorphism are Closure properties of language class.

14. Which of the theorem defines the existence of Parikhs theorem?
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned

View Answer

Answer: a
Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can only have ambiguous grammars.

15. Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n

View Answer

Answer: d
Explanation: There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button