Discrete Mathematics

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain exactly three 0s.

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 5 states as follows: S0, the initial state S1 is the state when the automata read exactly one 0 S2 is the state when the automata read exactly two 0s S3 is the state when the automata read exactly three …

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain exactly three 0s. Read More »

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that do not contain three consecutive 0s.

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 4 states as follows: S0, the initial state S1 is the state when the automata read a 0 S2 is the state when the automata read a sequence of two 0s S3 is the state when the automata read a …

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that do not contain three consecutive 0s. Read More »

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain the string 101

We will follow a similar approach to previous exercises to solve this exercise. Let’s define 4 states as follows: S0, the initial state S1 is the state when the automata read a 1 S2 is the state when the automata read a 0 after a 1 S3 is the state when the automata read a …

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that contain the string 101 Read More »

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10

This exercise is a bit more difficult than the previous one. To solve this exercise, let’s use the following strategy: define states in which the automaton can be if it just reads a 1 or a 0. – We can have a state S1 which means the automaton read 0s. Therefore, from the state S0 …

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10 Read More »

Construct a deterministic finite-state automaton that recognizes the set of all bit strings beginning with 01

To solve this exercise, we have to options. We can answer using a state table or state diagram. First, we need to consider that to be in the final state, we need first to start from S0, and recognize a 0, and then a 1. This tells us that we should have at least three …

Construct a deterministic finite-state automaton that recognizes the set of all bit strings beginning with 01 Read More »

Show that p → q and ¬q → ¬p are logically equivalent

The solution to this exercise is straightforward by constructing the truth table. By looking at the truth table for the two compound propositions p → q and ¬q → ¬p, we can conclude that they are logically equivalent because they have the same truth values (check the columns corresponding to the two compound propositions) Related …

Show that p → q and ¬q → ¬p are logically equivalent Read More »

What are propositional equivalences in Discrete Mathematics?

Propositional equivalences are used extensively in the construction of mathematical arguments. By using these equivalences, we can substitute propositions with other propositions with the same truth value. This proves to be very useful in different types of situations. Two compound propositions p and q are logically equivalent if p ↔ q is a tautology. The …

What are propositional equivalences in Discrete Mathematics? Read More »