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 states\newline $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 :Q\times \Sigma \longrightarrow Q$ Is the transition function \end{definition} \begin{remark} There are also non deterministic finite automata $[23]$ \end{remark}](https://2.bp.blogspot.com/-TLtSgk8RAf4/WRIGhYuW45I/AAAAAAAAAcI/yCcntYeQx44eytyWJQeOrUOT3_A_UTE6QCLcB/s1600/15-deterministic-finite-automaton.png "deterministic-finite-automaton")
2 - Language reconized by automaton
3 - Word recognition algorithm by automaton
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
No comments:
Post a Comment