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.