MCQ Computer Science

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

1. Which of the following does not belong to input alphabet if S={a, b}* for any language?
a) a
b) b
c) e
d) none of the mentioned

View Answer

Answer: c
Explanation: The automaton may be allowed to change its state without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.
2. Which of the given are correct?
a) Moore machine has 6-tuples
b) Mealy machine has 6-tuples
c) Both Mealy and Moore has 6-tuples
d) None of the mentioned

View Answer

Answer: c
Explanation: Finite Automaton with Output has a common definition for both the categories.
3. Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:
a) {Hello, World, Input, Output, ε}
b) {Hello, World, ε}
c) {Input, Output, ε}
d) {}

View Answer

Answer: d
Explanation: Union operation creates the universal set by combining all the elements of first and second set while intersection operation creates a set of common elements of the first and the second state.
4. Which of the following option is correct?
A= {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
c) ε may not belong to A
d) abca ₵ A

View Answer

Answer: b
Explanation: As the question has dot operation, ε will not be a part of the concatenated set. Had it been a union operation, ε would be a part of the operated set.
5. NFA, in its name has ’non-deterministic’ because of :
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the mentioned

View Answer

Answer: b
Explanation: Non deterministic or deterministic depends upon the definite path defined for the transition from one state to another or undefined(multiple paths).
6. In NFA, this very state is like dead-end non final state:
a) ACCEPT
b) REJECT
c) DISTINCT
d) START

View Answer

Answer: b
Explanation: REJECT state will be like a halting state which rejects a particular invalid input.
7. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned

View Answer

Answer: d
Explanation: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State charts, etc.
8. Which among the following is false?
ε-closure of a subset S of Q is:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)
d) None of the mentioned

View Answer

Answer: d
Explanation: All the mentioned are the closure properties of ε and encircles all the elements if it satisfies the following options:
a) Every element of S ϵ Q
b) For any q ϵ ε(S), every element of δ (q, ε) is in ε(S)
c) No other element is in ε(S)
9. Homomorphism of a regular set is _______
a) Universal set
b) Null set
c) Regular set
d) Non regular set

View Answer

Answer:c
Explanation: Regular set are closed under homomorphism.
10. RR* can be expressed in which of the forms:
a) R+
b) R-
c) R+ U R-
d) R

View Answer

Answer: a
Explanation: RR*=R+ as R+ means the occurrence to be at least once.
11. Which among the following is not a UNIX command for regular expressions?
a) ed
b) sed
c) vi
d) none of the mentioned

View Answer

Answer: d
Explanation: Regular expressions are used by different commands in Unix like ed, sed, grep, awk, vi, etc. Sed stands for stream editor which is exclusively used for executing scripts.
12. If the lexical analyser finds a lexeme with the same name as that of a reserved word,it _________
a) overwrites the word
b) overwrites the functionality
c) generates an error
d) something else

View Answer

Answer: c
Explanation: Reserved words are known as keywords and they are specific and reserved with its functionality to a language. Thus, getting an input with the same name by the analyzer will generate an error.
13. Which of the following language regular?
a) {aibi|i>=0}
b) {aibi|0<i<5}
c) {aibi|i>=1}
d) None of the mentioned

View Answer

Answer: b
Explanation: Here, i has limits i.e. the language is finite, contains few elements and can be graphed using a deterministic finite automata. Thus, it is regular. Others can be proved non regular using Pumping lemma.
14. If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned

View Answer

Answer: a
Explanation: If L1 is regular, so is L1′ and if L1′ and L2′ are regular so is L1′ U L2′. Further, regular languages are also closed under intersection operation.
15. Simplify the following identity:
E=01*+10*
ER=?
a) (1*0+0*1)
b) (01*10*)R
c) (0*1+10*)
d) All of the mentioned

View Answer

” state=”close”] Answer: a
Explanation: 01*+10*
ER=(01*)R+(10*)R=>(1*)R0R+(0*)R1R=>1*0+0*1

Related Articles

Leave a Reply

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

Back to top button