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
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
Explanation : All are equivalent to union operation.
a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine
View Answer
Explanation : All of above machine can accept regular language but all string accepted by machine is regular only for DFA.
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
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
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
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.
State true or false?
a) True
b) False
View Answer
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
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
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
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.
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
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}.
a) O(n2)
b) O(n3)
c) O(2n)
d) None of the mentioned
View Answer
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.
a) Kleene
b) Reversal
c) Homomorphism
d) Membership
View Answer
Explanation: Membership is a decision property of language class while others mentioned like Kleene, Reversal and Homomorphism are Closure properties of language class.
a) Parikh’s theorem
b) Jacobi theorem
c) AF+BG theorem
d) None of the mentioned
View Answer
Explanation: Rohit Parikh in 1961 proved in his MIT research paper that some context free language can only have ambiguous grammars.
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
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.