Automaton

automata-theory

Definition

Automaton

An automaton is a formal mathematical model of a computational system, typically defined as a quintuple:

$$\mathcal{A}=(Q,\Sigma ,\delta ,I,F)$$

where:

• $Q$ is a set of states,
• $\Sigma$ is the input alphabet,
• $\delta$: is the transition function,
• $I\subseteq Q$ is the set of initial states, and
• $F\subseteq Q$ is the set of accepting (final) states (subset of $Q$).

It processes input symbols (or strings) by transitioning between states according to $\delta$ and determines acceptance based on whether the final state is in $F$.

Example:

Note that the example is a deterministic finite automata.

Transition Function

Transition Function

The transition function $\delta :Q\times \Sigma \to Q$ is a function that takes a state $q\in Q$ and an input symbol $x\in \Sigma$ and returns the next state $q^{\prime }\in Q$.

Extended Transition Function

Extended Transition Function

The extended transition function ${\delta }^{\ast }:Q\times {\Sigma }^{\ast }\to Q$ is a function that takes a state $q\in Q$ and an input string $x\in {\Sigma }^{\ast }$ and returns the next state $q^{\prime }\in Q$.

$${\delta }^{\ast }(q,a_0{a}_1\dots a_k):=\{\begin{array}{ll}\delta (q,a_0)& \text{if }k=0\\ {\delta }^{\ast }(\delta (q,a_0),a_1\dots a_k)& \text{if }k>0\end{array}$$

Empty Word

Empty Word

The empty word is the empty string $\epsilon$.

All strings contain an infinite number of empty words, for example:

$$a=\epsilon a=a\epsilon a=a\epsilon =\dots$$

Language

Language

The language of an automaton $\mathcal{A}$ is the set of all strings $x\in {\Sigma }^{\ast }$ such that ${\delta }^{\ast }(q_0,x)\in F$.

An input $x$ is called a valid string if ${\delta }^{\ast }(q_0,x)\in F$, meaning that the string is part of the language of the automata $\mathcal{A}$.

Equivalence

Equivalence of Automata

Two automata $\mathcal{A}$ and $\mathcal{B}$ are equivalent if they accept the same language.

Types

There are different types of automata:

Deterministic Finite Automaton

Definition

Deterministic Finite Automaton

A deterministic finite automaton (DFA) is a automaton that has a finite number of states and the transition function $\delta$ is deterministic.

$$\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$$

where:

• $Q$ is a finite set of states,
• $\Sigma$ is the input alphabet,
• $\delta :Q\times \Sigma \to Q$ is the transition function
• $q_0\in Q$ is the initial state, and
• $F\subseteq Q$ is the set of accepting (final) states (subset of $Q$).

It processes input symbols (or strings) by transitioning between states according to $\delta$ and determines acceptance based on whether the final state is in $F$.

All deterministic finite automata are Nondeterministic Finite Automaton.

Link to original

Nondeterministic Finite Automaton

Definition

Nondeterministic Finite Automaton

A Nondeterministic Finite Automaton (NFA) is a finite automaton that has a nondeterministic transition function.

A nondeterministic transition function is a function that takes a state and an input symbol and returns a set of possible next states.

$$\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$$

where:

• $Q$ is a finite set of states,
• $\Sigma$ is the input alphabet,
• $\delta :Q\times \Sigma \to \mathcal{P}(Q)$ is the transition function (power set of $Q$)
• $q_0\in Q$ is the initial state, and
• $F\subseteq Q$ is the set of accepting (final) states (subset of $Q$).

It processes input symbols (or strings) by transitioning between states according to $\delta$ and determines acceptance based on whether the final state is in $F$.

Link to original

Transducer

Definition

Transducer

A transducer is an automaton that processes input strings and produces corresponding output strings, effectively mapping one sequence to another.

Formally, a finite-state transducer can be defined as a tuple:

$$\mathcal{T}=(Q,\Sigma ,\Gamma ,\delta ,\lambda ,q_0,F)$$

where:

• $Q$ is a set of states
• $\Sigma$ is the input alphabet
• $\Gamma$ is the output alphabet
• $\delta :Q\times \Sigma \to Q$: is the transition function
• $\lambda :Q\times \Sigma \to \Gamma$: is the output function
• $I\subseteq Q$ is the set of initial states
• $F\subseteq Q$ is the set of accepting (final) states.

For each input symbol in a state, a next state, using the transition function $\delta$, and an output symbol, using the output function $\lambda$, are produced by the transducer.

Link to original