Finite Automata
COS2601 - Theoretical Computer Science II · Automata Theory
Finite Automata
A finite automaton (FA) is a theoretical model used in computer science to represent and manipulate a set of states based on input symbols. It is a crucial concept in automata theory and is fundamental to understanding how machines process information.
Definition of Finite Automaton
A finite automaton consists of three main components:
- A finite set of states, with one state designated as the initial state (or start state) and some states designated as final states (or accepting states).
- An alphabet, which is a finite set of symbols that the automaton can read as input.
- A finite set of transitions, which define how the automaton moves between states based on the input symbols.
The formal definition can be summarized as:
- Q = {q_0, q_1, ..., q_n} is a finite set of states.
- q_0 is the start state.
- F is a subset of Q that contains the final states.
- Σ is the input alphabet.
- δ: Q × Σ → Q is the transition function that maps each state and input symbol to a subsequent state.
Remember: The transition function δ determines how the automaton changes state based on the current state and the input symbol.
Example of a Finite Automaton
Consider an FA with the following components:
- States: Q = {x, y, z}
- Start state: x
- Final state: z
- Input alphabet: Σ = {a, b}
The transition rules are defined as follows:
- From state x, on input a, go to state y.
- From state x, on input b, go to state z.
- From state y, on input a, go to state x.
- From state y, on input b, go to state z.
- From state z, on any input, stay in state z.
This setup means that:
- Starting in state x, if the input is 'a', the automaton moves to state y.
- If the input is 'b', it moves to state z, which is a final state.
Processing Input Strings
The FA processes an input string by reading each symbol in sequence, starting from the leftmost symbol. The automaton transitions between states according to the defined rules. Let’s consider how this FA processes various input strings:
Input String: aaa
1. Start at state x.
2. Read 'a': transition to state y.
3. Read 'a': transition back to state x.
4. Read 'a': transition to state y.
5. End in state y (not a final state), so the input string 'aaa' is rejected.
Input String: ab
1. Start at state x.
2. Read 'a': transition to state y.
3. Read 'b': transition to state z.
4. End in state z (a final state), so the input string 'ab' is accepted.
Transition Table
| State | a | b |
|---|---|---|
| x | y | z |
| y | x | z |
| z | z | z |
Transition Diagrams
A transition diagram visually represents the states and transitions of a finite automaton. In this diagram:
- Each state is represented by a circle.
- The start state has an incoming arrow, and final states are marked with a double circle.
- Arrows (edges) indicate transitions, labelled with the corresponding input symbols.
Diagram: Farisori, CC BY-SA 4.0, via Wikimedia Commons
Accepting Languages
The language accepted by a finite automaton is the set of all input strings that lead to a final state. For the given FA, the language can be expressed using a regular expression. In this case, the language accepted consists of all strings containing at least one 'b'.
Tip: To determine the language of an FA, trace various input strings and identify which lead to final states.
Common Mistakes
Watch out: When tracing input strings, ensure you follow the transition rules correctly and keep track of the current state accurately.
Constructing Finite Automata
To construct a finite automaton for a specific language, start by defining the language's characteristics. For example, if you want to accept strings that start with 'a' and end with 'b', you can create states that reflect these conditions:
- State 1: Start state (waiting for 'a').
- State 2: After reading 'a' (waiting for 'b').
- State 3: Final state (after reading 'b').
Transitions would be defined to lead from state 1 to state 2 on input 'a', and from state 2 to state 3 on input 'b'.
Self-Check Questions
- What are the three components of a finite automaton?
- How does a finite automaton process an input string?
- What is a transition table and how is it used?
- How can you construct a finite automaton for a specific language?