# 1.1 finite automata

## finite automata = finite state machine

computational model: idealized computer

patterns of data

## Formal Def of a Finite Automation

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

• Q is a finite set called the states
• $\Sigma$ is a finite set called the alphabet
• $\delta : Q \times \Sigma \rightarrow Q$ is the transition function
• $q_0 \in Q$ is the start state
• $F \subseteq Q$ is the set of accept states

language of machine M: L(M)=A

If $A=\{w|M accepts w\}$, then M recognizes A

## Formal Def of Computation

Let M=($Q, \Sigma , \delta , q_0 , F$) be a finite automation and $w=w_1 w_2 \cdots w_n$ be a string over alphabet $\Sigma$. Then M accepts w if a sequence of states $r_0 r_1 \cdots r_n$ exists in Q with the following three conditions:

• $r_0 = q_0$
• $\delta (r_i , w_{i+1}) = r_{i+1}$, for $i = 0, \cdots , n-1$
• $r_n \in F$

A language is called a regular language if some finite automation recognizes it.

## The Regular Operations

i.e. the properties of finite automata & regular languages Let A and B be languages. Define regular operations as follows:

• Union: $A \cup B = \{x | x \in A \text{ or } x \in B\}$
• Concatenation: $A \circ B = \{xy | x \in A \text{ and } y \in B \}$
• Star: $A^* = \{ x_1 x_2 \cdots x_k | k \geq 0 \text{ and each } x_i \in A\}$

The class of regular languages is closed under these operation. (It will be easier for us to prove after learning nondeterminism.)