Introduction to finite deterministic automata

May 9, 2017

1 - Deterministic finite automaton

$chapter{Finite Automata Theory} section{Deterministic finite automaton} begin{definition} A deterministic finite automaton is a quintuplet $(Q,Sigma ,delta ,q_{0},F) $ where :newline $1)$ $Q$ Is a finite set of statesnewline $2)$ $Sigma $ Is a finite alphabet (set of input symbols)newline $3)$ $q_{0}$ Is the initial state (start state)newline $4)$ $F$ Is the set of final states newline $5)$ $delta :Qtimes Sigma longrightarrow Q$ Is the transition function end{definition} begin{remark} There are also non deterministic finite automata $[23]$ end{remark}$

2 - Language reconized by automaton

$section{Language recognized by automaton} Given a finite deterministic automaton $A_{Sigma }=(Q,Sigma ,delta ,q_{0},F)$ over an alphabet $Sigma $ and $m=m_{0}m_{1}...m_{n}$ a word of $% Sigma $. To know if the word $m$ is accepted or rejected by $A_{Sigma }$ we must at first, determine the terms of the sequence $p_{0},p_{1},...,p_{n}$ defined by :% begin{equation*} left{ begin{array}{l} p_{0}=q_{0} \ p_{i+1}=delta (p_{i},m_{i})text{ }0leq ileq n-1% end{array}% right. end{equation*} begin{definition} Under the same assumptions as above, if the last element $p_{n}$ of sequence $(p_{i})_{i}$ is final state ( ie $p_{n}in F),$ we said then that the word $% m=m_{0}m_{1}...m_{n}.$ is accepted by automaton $A_{Sigma },$ else we said that the word $m$ is not accepted or rejected by $A_{Sigma }.$ end{definition}$

$begin{example} Consider the automaton $A=(Q,Sigma ,delta ,I,F)$ definied by : newline $Sigma ={a,b}$newline $Q={1,2}$newline $I={1}$newline $F={2}$newline $delta :Qtimes Sigma rightarrow Q$ defined by :newline $delta (1,a)=1,$ $delta (1,b)=2,$ $delta (2,a)=1,$ $delta (2,b)=2$ This automaton can be represented in two different ways :newline $1)$ Using tablenewline begin{tabular}{|l|l|l|} hline & a & b \ hline $rightarrow 1$ & 1 & 2 \ hline $ast 2$ & 1 & 2 \ hline end{tabular}% newline $2)$ Using graph : begin{equation*} FRAME{itbpF}{3.6928in}{1.0652in}{0in}{}{}{automate1.png}{special{language "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display "USEDEF";valid_file "F";width 3.6928in;height 1.0652in;depth 0in;original-width 3.5359in;original-height 1.0004in;cropleft "0";croptop "1";cropright "1";cropbottom "0";filename 'imgmachine/automate1.PNG';file-properties "XNPEU";}} end{equation*} end{example}$

This automaton accepts the word $mathbf{abb}$ but it does not accept the word $mathbf{aba}$ begin{notation} The language reconized by automaton $A$ will be denoted $L(A)$ ( the set of words accepted by automaton $A)$ end{notation} begin{definition} A language $L$ is said to be reconizable if there exists an automaton $A$ such that $L=L(A)$ end{definition} begin{notation} The set of all reconizables languages will be denoted by $R$ end{notation}

3 - Word recognition algorithm by automaton

$section{Word recognition algorithm by automaton} Let $A=(Q,Sigma ,delta ,I,F)$ be a deterministic finite automaton , the recognition or rejection of a word $u=u_{0}u_{1}...u_{n}$ can be represented by an algorithm :$

Start Algorithm
q←q₀
i←1
While (i≤n-1) do
q←δ(q,u_{i})
i←i+1
End while
If q∈F then
Display "The word u is accepted"
Else
Display "The word u is rejected"
End If
End Algorithm

Younes Derfoufi

Post Views: 103