MCQ Computer Science

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

Answer: a
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

Answer: a
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

Answer: a
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

Answer: b
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

Answer: d
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.
7. The O/P of Moore machine can be represented in the following format:
a) Op(t)=d(Op(t))
b) Op(t)=d(Op(t)i(t))
c) Op(t): ?
d) None of the mentioned

View Answer

Answer: a
Explanation: Op(t)=d(Op(t)) is the defined definition of how the output is received on giving a specific input to Moore machine.

8. The output alphabet can be represented as:
a) d
b) ?
c) ?
d) None of the mentioned

View Answer

Answer: b
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.

9. For the following change of state in FA, which of the following codes is an incorrect option?
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.

10. Statement 1: Mealy machine reacts faster to inputs.
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

Answer: a
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

Answer: b
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.

12. Given L= {X??*= {a, b} |x has equal number of a, s and b’s}.
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

Answer: b
Explanation: DFA can be made for infinite language with an infinite length. Thus, dependency over length is unfruitful.

13. d(A,1) = B, d(A,0) =A
? (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

Answer: a
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.

14.The complement of a language will only be defined when and only when the __________ over the language is defined.
a) String
b) Word
c) Alphabet
d) Grammar

View Answer

Answer: c
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’.

15.Which among the following is not notated as infinite language?
a) Palindrome
b) Reverse
c) Factorial
d) L={ab}*

View Answer

Answer: Factorial
Explanation: Factorial, here is the most appropriate non-infinite domain. Otherwise, palindrome and reverse have infinite domains.

Related Articles

Leave a Reply

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

Back to top button