Finite Automata

Definition

A finite automaton is a $5$-tuple $M=(Q,\Sigma ,\delta ,q_0,F)$, where:

1. $Q$ is a finite set called the states
2. $\Sigma$ is a finite set called the alphabet
3. $\delta :Q\times \Sigma \to Q$ is the transition function
4. $q_0\in Q$ is the start state
5. $F\subseteq Q$ is the set of accept states

Informal Description

A finite automaton (also called a finite state machine) is an idealized model of a computer with a fixed, limited amount of memory.

Components

• States: The machine is always in one of a finite number of states.
  • Start State is indicated by arrow pointing at it from nowhere
  • Accept State is indicated by double circle
  • Transition: The machine moves from one state to another based on an input symbol it receives.
• Output:
  • Either accept or reject

Processing

1. Begins in $M_1$‘s start state
2. Automaton receives symbols from the input string one-by-one from left to right
3. After reading each symbol $a$, $M_1$ moves from one state to another along the transition that has the symbol $a$ as its label
4. When the automaton reads last symbol, $M_1$ produces its output
   • accept if $M_1$ is now in an accept state
   • reject if $M_1$ is not in an accept state

Example

Input: $1101$

1. Start in state $q_1$.
2. Read $1$, follow transition from $q_1$ to $q_2$.
3. Read $1$, follow transition from $q_2$ to $q_2$.
4. Read $0$, follow transition from $q_2$ to $q_3$.
5. Read $1$, follow transition from $q_3$ to $q_2$.
6. Accept because $M_1$ is in an accept state $q_2$ at the end of the input.

How it Computes (Deterministic Computation)

1. Start: The process begins in the start state $q_0$​.
2. Read: The machine reads the input string symbols one by one from left to right.
3. Move: After reading a symbol, it follows the transition $\delta$ to a new state.
4. Output: After the last symbol is read, the machine accepts the string if it is in an accept state; otherwise, it rejects it.

Key Terminology

• State Diagrams: A visual representation of the automaton where circles represent states and arrows represent transitions.
• Transition Table: A tabular representation of the transition function $\delta$, showing the next state for every combination of current state and input symbol.
• Language of a Machine ($L(M)$): The set of all strings that the machine $M$ accepts.
• Recognize: A machine recognizes a language if it accepts every string in that language and rejects all others. Note that while a machine may accept many strings, it recognizes exactly one language.

Regular Operations

The power of finite automata is often discussed in the context of three “regular operations” used to manipulate languages.

• Union: takes all the strings in both $A$ and $B$, lumps them into one language

• Concatenation: Attaching strings from one language to strings of another.

• Star: Repeating strings from a language any number of times.
  • “any number” includes $0$, so the empty string $ϵ$ is always a member of $A^{\ast }$

Theorem

The Class of Regular Languages is Closed Under the Union Operation ($\cup$)

Proof by Construction

Assume:
$M_1$ recognize $A_1$ where $M_1=(Q_1,\Sigma ,{\delta }_1,q_1,F_1)$
$M_2$ recognize $A_2$ where $M_2=(Q_2,\Sigma ,{\delta }_2,q_2,F_2)$

Construct $M$ to recognize $A_1\cup A_2$, where $M=(Q,\Sigma ,\delta ,q_0,F)$

1. $Q=\{(r_1,r_2)|r_1\in Q_1\text{ and }{r}_2\in Q_2\}$
   This set is the Cartesian Product of sets $Q_1$ and $Q_2$ and is written $Q_1\times Q_2$
   It is the set of all pairs of states, the first from $Q_1$ and the second from $Q_2$
2. $\Sigma$ is the same as in $M_1$ and $M_2$
3. $\delta$, the transition function, is defined as follows:
   For each $(r_1,r_2)\in Q$ and each $a\in \Sigma$, let

Hence $\delta$ gets a state of $M$ (which actually is a pair of states from $M_{1}$ and $M_{2}$), together with an input symbol and returns $M$'s next state

4. $q_0$ is the pair $(q_1,q_2)$
5. $F$ is the set of pairs in which either member is an accept state of $M_1$ or $M_2$, written as

This expression is the same as $F=(F_{1} \times Q_{2}) \cup (Q_{1} \times F_{2})$
Note that is it *not* the same as $F = F_{1} \times F_{2}$