What Is a Finite State Machine and How Does a DFA Work?

TL;DR

A deterministic finite automaton is formally defined by five tuples: Q (the set of all states), Sigma (the inputs), q0 (the start state), F (the set of final states), and delta (a transition function mapping Q cross Sigma to Q). In a state diagram, circles are states, edge labels are inputs, an arrow from nowhere marks the start state, and a double circle marks a final state.

Transcript

hello everyone welcome to the next lecture in theory of computation and in this lecture we will be studying about finite State machines all right so let's get started so finite State machines it is also known as finite automata and this finite automata is divided into two broad categories the first one being finite automata with output and the seco... Read More

Key Insights

• Finite automata is another name for finite state machines, and the family divides into two broad categories: finite automata with output and finite automata without output. This top-level split organizes every machine type discussed in the lecture.
• Finite automata with output has two categories, the Moore machine and the Mealy machine, while finite automata without output has three: deterministic finite automata (DFA), non-deterministic finite automata (NFA), and Epsilon non-deterministic finite automata (Epsilon NFA).
• The finite state machine is the simplest model of computation, and it has very limited memory. These are the two properties the lecture says to always remember before studying anything related to finite state machines, and they are stated before DFA is introduced.
• In a DFA diagram, the circles labeled a, b, c, and d are the states, the arrows between circles are the transitions, and the labels on those edges, such as 0 and 1, are the inputs the machine reads.
• The start state of a DFA is identified by an arrow that comes from nowhere and points to it. In the lecture's example diagram, that arrow points to state a, making a the initial state, also called the start state.
• The final or terminating state of a DFA is drawn with a double circle around it, unlike every other state which has a single circle. In the example, state d carries the double circle, so d is the final state.
• Every DFA can be defined using five tuples: Q, Sigma, q0, F, and delta. Q is the set of all states, Sigma is the inputs, q0 is the start state, F is the set of final states, and delta is the transition function.
• F is written as a set of final states rather than a single state because a DFA can have more than one final state, even though the example diagram in this lecture has only one, state d.
• The transition function delta maps Q cross Sigma to Q, meaning it takes a current state and an input symbol and returns the next state. It is commonly written out as a table with inputs across the top and states down the side.

Questions & Answers

Q: What is a finite state machine?

A finite state machine, also known as finite automata, is a model of computation studied in theory of computation. Two properties should always be remembered about it: it is the simplest model of computation, and it has very limited memory. Structurally it consists of states, inputs, and transitions between states, where reading a particular input in a particular state moves the machine to another state. It is divided into finite automata with output and finite automata without output.

Q: What are the types of finite automata?

Finite automata is divided into two broad categories. The first is finite automata with output, which has two categories, the Moore machine and the Mealy machine. The second is finite automata without output, which has three categories: deterministic finite automata (DFA), non-deterministic finite automata (NFA), and Epsilon non-deterministic finite automata (Epsilon NFA). The lecture focuses mainly on deterministic finite automata, and later lectures in the course take up examples that make DFA clearer.

Q: What are the five tuples that define a DFA?

Every DFA can be defined using five tuples: Q, Sigma, q0, F, and delta. Q is the set of all states in the machine. Sigma is the inputs. q0 is the start state, also called the initial state. F is the set of final states, written as a set because a DFA can have more than one final state. Delta is the transition function that maps Q cross Sigma to Q, taking a state and an input and giving the resulting state.

Q: How do you identify the start state in a DFA diagram?

The start state is identified by an arrow that comes from nowhere and points to that state. Unlike the other arrows in the diagram, which run between two states and represent transitions, this arrow has no source state. Whenever you see an arrow coming from nowhere pointing to a state, that state is the initial or start state of the DFA. In the lecture's example diagram, this arrow points to state a, so a is q0.

Q: How is the final state shown in a DFA state diagram?

The final state, also called the terminating state, is drawn with a double circle around it. Every other state in the diagram is drawn with a single circle, so the double circle is what distinguishes it. In the lecture's example, state d has two circles around it, which makes d the final state of that DFA. Because a DFA may have more than one such state, the formal definition writes F as a set of final states.

Q: What do the labels on the edges of a DFA diagram mean?

The labels on the edges are the inputs. The circles are the states and the edges connecting them are the transitions, so a labeled edge says what input causes a move from one state to another. For example, in state a with input 1, the machine goes from a to b, and in state a with input 0, it goes from a to c. From state c with input 1 it goes to d, and from d with input 0 it goes to b.

Q: How do you write the transition function of a DFA as a table?

You draw a table with the inputs across the top and the states down the side, then fill in the destination state for each state and input pair. In the lecture's example, the inputs are 0 and 1 and the states are a, b, c, and d. From a: input 0 goes to c, input 1 goes to b. From b: input 0 goes to d, input 1 goes to a. From c: input 0 goes to a, input 1 goes to d. From d: input 0 goes to b, input 1 goes to c.

Q: What does it mean that the transition function maps Q cross Sigma to Q?

It means the transition function delta takes a pair consisting of a state from Q and an input from Sigma and returns a state in Q. That is exactly what the transition table expresses: each row is a current state, each column is an input, and each cell is the resulting state. For instance, the pair (state c, input 1) maps to state d, and the pair (state d, input 0) maps to state b in the lecture's example DFA.

Summary & Key Takeaways

• Finite state machines, also called finite automata, split into two broad categories: finite automata with output and finite automata without output. With output covers Moore machines and Mealy machines. Without output covers deterministic finite automata (DFA), non-deterministic finite automata (NFA), and Epsilon non-deterministic finite automata (Epsilon NFA). This lecture focuses on DFA.

• Two properties should always be kept in mind before studying anything related to finite state machines: the finite state machine is the simplest model of computation, and it has very limited memory. These two points frame everything else covered about finite automata and are stated before the DFA discussion begins.

• In a DFA state diagram, circles labeled a, b, c, and d are states, and the arrows between them are transitions. The labels on the edges, such as 0 and 1, are the inputs. An arrow coming from nowhere pointing at a state marks the start state, and a double circle marks the final or terminating state.

• Every DFA is defined using five tuples: Q, Sigma, q0, F, and delta. Q is the set of all states, Sigma is the inputs, q0 is the start or initial state, F is the set of final states (written as a set because there can be more than one), and delta is the transition function mapping Q cross Sigma to Q.

• For the example diagram, Q is {a, b, c, d}, Sigma is {0, 1}, q0 is a, and F is {d}. The transition function is written as a table with inputs 0 and 1 across the top and states a, b, c, d down the side, filling in the destination state for each state and input pair.