Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-25
1. The number of elements in the set for the Language L={x?(?r) *|length if x is at most 2} and ?={0,1} is_________
a) 7
b) 6
c) 8
d) 5
View Answer
Answer: a
Explanation: ?r= {1,0} and a Kleene* operation would lead to the following set=COUNT{e,0,1,00,11,01,10} =7.
2. What is the output for the given language?
Language: A set of strings over ?= {a, b} is taken as input and it prints 1 as an output “for every occurrence of a, b as its substring. (INPUT: abaaab)
a) 0010001
b) 0101010
c) 0111010
d) 0010000
View Answer
Explanation: The outputs are as per the input, produced.
3. The major difference between Mealy and Moore machine is about:
a) Output Variations
b) Input Variations
c) Both
d) None of the mentioned
View Answer
Explanation: Mealy and Moore machine vary over how the outputs depends on prior one (transitions) and on the latter one(states).
4. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA?
a) yes
b) no
View Answer
Explanation: Yes, the language is preserved during the dteps of construction: L(N)=L(N1)=L(N2)=L(3).
5. Can a DFA recognize a palindrome number?
a) Yes
b) No
c) Yes, with input alphabet as ?*
d) Can’t be determined
View Answer
Explanation: Language to accept a palindrome number or string will be non-regular and thus, its DFA cannot be obtained. Though, PDA is possible.
6. Which of the following is not an example of finite state machine system?
a) Control Mechanism of an elevator
b) Combinational Locks
c) Traffic Lights
d) Digital Watches
View Answer
Explanation: Proper and sequential combination of events leads the machines to work in hand which includes The elevator, Combinational Locks, Traffic Lights, vending machine, etc. Other applications of Finite machine state system are Communication Protocol Design, Artificial Intelligence Research, A Turnstile, etc.
a) Op(t)=d(Op(t))
b) Op(t)=d(Op(t)i(t))
c) Op(t): ?
d) None of the mentioned
View Answer
Explanation: Op(t)=d(Op(t)) is the defined definition of how the output is received on giving a specific input to Moore machine.
a) d
b) ?
c) ?
d) None of the mentioned
View Answer
Explanation: Source-The tuple definition of Moore and mealy machine comprises one new member i.e. output alphabet as these are finite machines with output.
a) d (m, 1) =n
b) d (0, n) =m
c) d (m,0) =e
d) s: accept = false; cin >> char;
if char = “0” goto n;
View Answer
Answer: b
Explanation: d(QX?) = Q1 is the correct representation of change of state. Here, d is called the Transition function.
Statement 2: Moore machine has more circuit delays.
Choose the correct option:
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true but Statement 2 is false
c) Statement 1 is false and Statement 2 is true
d) None of the mentioned is true
View Answer
Explanation: Being an input dependent and output capable FSM, Mealy machine reacts faster to inputs.
11. ZPP is exactly equal to the ____________of the classes RP and co-RP.
a) Union
b) Intersection
c) Concatenation
d) Difference
View Answer
Explanation: To prove the following statement, we need to take in note that every problem in RP and co-RP has a Las-Vegas algorithm.
Which of the following property satisfy the regularity of the given language?
a) Regularity is dependent upon the length of the string
b) Regularity is not dependent upon the length of the string
c) Can’t be said for a particular string of a language
d) It may depend on the length of the string
View Answer
Explanation: DFA can be made for infinite language with an infinite length. Thus, dependency over length is unfruitful.
? (B, (0,1)) =C
d(C,0) = A (Initial state =A)
String=”011001” is transit at which of the states?
a) A
b) C
c) B
d) Invalid String
View Answer
Explanation: It is east and simple to create the table and then the corresponding transition graph in order to get the result, at which state the given string would be accepted.
a) String
b) Word
c) Alphabet
d) Grammar
View Answer
Explanation: It is not possible to define the complement of a language without defining the input alphabets. Example: A language which does not consist of substring ‘ab’ while the complement would be the language which does contain a substring ‘ab’.
a) Palindrome
b) Reverse
c) Factorial
d) L={ab}*
View Answer
Explanation: Factorial, here is the most appropriate non-infinite domain. Otherwise, palindrome and reverse have infinite domains.