1.Which of the following is a tautology?
a) p ∧ (¬p)
b) p ∨ (¬p)
c) p → (¬p)
d) ¬p → p
Answer: b) p ∨ (¬p)
Explanation: The statement “p ∨ (¬p)” is a tautology known as the Law of Excluded Middle, as it is always true, regardless of the truth value of p.
2.Which type of logic operation is equivalent to “if-then”?
a) Conjunction
b) Disjunction
c) Negation
d) Implication
Answer: d) Implication
Explanation: The logical implication (→) corresponds to the “if-then” relationship, where if the antecedent is true, then the consequent must also be true.
3.What is a finite state machine?
a) A machine with an infinite number of states
b) A machine that recognizes regular languages
c) A machine that can perform infinite computations
d) A machine that operates on real numbers
Answer: b) A machine that recognizes regular languages
Explanation: A finite state machine (FSM) is a computational model used to recognize patterns or sequences in strings, often associated with regular languages.
4.In a finite state machine, what are the states?
a) Representations of numbers
b) Inputs provided to the machine
c) Possible configurations of the machine
d) Operations performed by the machine
Answer: c) Possible configurations of the machine
Explanation: States in a finite state machine represent different configurations or conditions that the machine can be in at any given time.
5.What is the purpose of an equivalence machine?
a) To recognize patterns in strings
b) To determine if two finite state machines are equivalent
c) To compare two sets for equivalence
d) To generate regular languages
Answer: b) To determine if two finite state machines are equivalent
Explanation: An equivalence machine is used to determine if two finite state machines recognize the same language, i.e., if they are equivalent in terms of their language recognition capabilities.
6.In propositional logic, what is the negation of the statement “p ∧ q”?
a) ¬p ∨ ¬q
b) ¬p ∧ ¬q
c) ¬(p ∧ q)
d) ¬p → ¬q
Answer: b) ¬p ∧ ¬q
Explanation: The negation of “p ∧ q” is logically equivalent to “¬p ∨ ¬q” according to De Morgan’s Law.
7.Which of the following logical operations corresponds to the “if-then” relationship?
a) Conjunction (AND)
b) Disjunction (OR)
c) Negation (NOT)
d) Implication (→)
Answer: d) Implication (→)
Explanation: The logical operation “→” corresponds to the “if-then” relationship. It states that if the antecedent is true, then the consequent must also be true.
8.What is the truth value of the proposition “p → q” when p is true and q is false?
a) True
b) False
c) Cannot be determined
d) Both true and false
Answer: b) False
Explanation: The proposition “p → q” is false only when p is true and q is false; otherwise, it is true.
9.In propositional logic, what is the logical equivalence of “p → q”?
a) ¬p ∧ ¬q
b) ¬p → ¬q
c) ¬(p ∧ q)
d) ¬q → ¬p
Answer: d) ¬q → ¬p
Explanation: The logical equivalence of “p → q” is “¬q → ¬p” according to the contrapositive property.
10.What is the purpose of a finite state machine?
a) To perform arithmetic calculations
b) To recognize patterns in strings
c) To execute complex algorithms
d) To generate random numbers
Answer: b) To recognize patterns in strings
Explanation: A finite state machine is a computational model used to recognize patterns or sequences in strings, making it useful in various applications such as lexical analysis and parsing.
11.Which component of a finite state machine stores the current state?
a) Transition function
b) Output function
c) Input alphabet
d) State register
Answer: d) State register
Explanation: The state register of a finite state machine stores the current state during its operation.
12.What does the transition function of a finite state machine define?
a) The input symbols accepted by the machine
b) The output produced by the machine
c) The next state based on the current state and input symbol
d) The final state of the machine
Answer: c) The next state based on the current state and input symbol
Explanation: The transition function of a finite state machine defines the next state of the machine based on its current state and the input symbol received.
13.Which type of finite state machine can remember past inputs and produce output based on both current and past inputs?
a) Moore machine
b) Mealy machine
c) Deterministic finite automaton
d) Non-deterministic finite automaton
Answer: b) Mealy machine
Explanation: In a Mealy machine, output is produced based on both the current state and the current input, allowing it to remember past inputs and produce output accordingly.
14.What is the number of states required for a finite state machine to recognize a language with n distinct strings?
a) n
b) n!
c) 2^n
d) 2n
Answer: c) 2^n
Explanation: In the worst case, a finite state machine may need to remember whether each of the n distinct strings has occurred or not, requiring 2^n states.
15.What is the primary advantage of using finite state machines in language recognition tasks?
a) They can recognize any language
b) They are faster than other models
c) They provide optimal solutions
d) They are easy to implement and understand
Answer: d) They are easy to implement and understand
Explanation: Finite state machines are relatively simple to implement and understand, making them advantageous for tasks such as language recognition, where the problem can be represented as a finite set of states and transitions.