Finite Automaton

Aka. FA. A machine with:

• A finite number of states
• Has one or more starting states
• Transitions based on input symbols
• Optionally has some accepting states

For each state and input symbol, exactly one transition exists.

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

Where:

• $Q$ is a finite set of states
• $\Sigma$ is a finite input alphabet
• $q_0 \in Q$ is the start state
• $A \subseteq Q$ is the set of accepting states
• $\delta : Q \times \Sigma → Q$ is the transition function

FA with Outputs

Traditionally FAs are concerned with accepting or rejecting strings. But they can also generate outputs from an output alphabet. Will be covered in Moore Machines and later.

Used when systems must generate outputs while processing input sequences. Common in digital circuits, controllers, and reactive systems.

Transition Function

Denoted by $\delta$. It maps a state and an input symbol to the next state.

Extended Transition Function

Denoted by $\delta^*$. Handles strings instead of each symbol. $\delta^*(q, x)$ is the state reached after reading string $x$ starting from state $q$.

Acceptance by an FA

A string is accepted iff the machine ends in an accepting state after reading it.

The language accepted by $M$ is $L(M) = \set{ x \in Σ^* | x\;\text{is accepted by}\;M }$

Representations of FA

Transition Diagram

FA is represented as a directed graph with labelled edges.

• Vertices are states
• Labeled edges are transitions
• Start state is marked
• Accepting states are double-circled

Transition Table

Rows represent current states. Columns represent input symbols. Entries give next states.

Conversion with Regular Expressions

To a Regular Expression

• Start by analyzing the FA’s structure.
• Identify paths and loops to construct the RE.
• This process can be complex for larger FAs.

From a Regular Expression

• Identify repititive elements.
• Identify components such as union, concatenation, and Kleene star.
• Create states to represent these components and transitions based on the structure of the RE.

Kleene’s Theorem

A language $L \subseteq \Sigma^*$ is regular iff there exists a finite automaton that accepts $L$.

Every FA has an equivalent regular expression. And vice versa.

Other Important Thoerems

Theorem 1

If a language has $n$ distinguishable strings, the FA must have at least $n$ states.

Theorem 2

Language of palindromes over any alphabet $\Sigma$ is not regular because a FA has fixed number of states and it’s not enough to check for palindromes.

Set Operations on FA

Suppose $M_1 = (Q_1, \Sigma, q_1, A, \delta_1)$ and $M_2=(Q_2, \Sigma, q_2, A, \delta_2)$ are FAs accepting languages $L_1$ and $L_2$ respectively.

Let $M=(Q_1 \times Q_2, \Sigma, (q_1, q_2), A_1, \delta)$. Here $\delta((p,q), a) = (\delta_1(p, a), \delta_2(q, a))$. Based on how $A_1$ is defined, $M$ can accept different languages: $L_1 \cup L_2$ or $L_1 \cap L_2$ or $L_1 - L_2$.

Distinguishing Strings

Two strings $x$ and $y$ are distinguishable with respect to a language $L$ if their language quotients (with respect to $L$) are different.

2 strings $x$ and $y$ are distinguishable with respect to $L$ iff $L/x \neq L/y$. Any string in one of these sets but not the other is said to distinguish $x$ and $y$ with respect to $L$.

A string $z$ is an extension of $x$ with respect to $L$ if exactly one of $xz$ and $yz$ belongs to $L$.