Social Icons

Tuesday, May 9, 2017

Introduction to finite deterministic automata

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}

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{ }0\leq i\leq 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 :Q\times \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 table\newline \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

No comments:

Post a Comment

Python Exercises With Solutions

  1. Exercises on Python Strings
  2. Exercises on Python lists
  3. OOP Exercices with solutions
  4. Exercises on Python File I/O
  5. Python Dictionary Exercises
  6. Python Sets Exercises
  1. Python Arithmetic Exercises
  2. Equations & System Of Equations
  3. Polynomials and Functions
  4. Python Arithmetic Exercises 
  5. Numpy, Matplolib, Sympy , Scipy - Exercises
  6. Python Arithmetic Exercises
  1. Python GUI Tkinter Exercises



Younes Derfoufi

Category Of Mobile Courses

Actualités (644) Adsense (1) Affiliation (1) Algebraic Topology (2) Algorithmic (1) all-news (30) Android (5) Android App (8) Android app without code (4) Android Apps (256) Android Development (4) Android download (2) Android OS (3) AngularJS (1) Automata theory and formal language (5) Bootstrap CSS (1) C programming (5) Category and Functor (8) CMS (3) Computer Glossary (18) Create Mobile App With Ionic Framework (2) CSS (2) CSS-Cascading-Style-Sheets (4) Developpement Java (13) Differential Geometry (1) Django-Python-Framework (9) dropshiping (26) Earn Money by Internet (4) Emplois (23) Framework php (2) Fraud (2) HTML (7) Java For Beginners (10) Javascript (12) Kotlin Programming Language (8) Kotlin For Mobile Android (1) Linux Download (2) Marketing (5) Mobile (3) Mobile Courses (4) Mobile Marketing (4) MoneyGram (1) News (721) Node.js (5) Open Source (1) Photoshop (1) Protect Computer (1) Python (35) Python BeautifulSoup (1) Python For Data Science (2) Python PyQt (4) Python Reference (1) Python-Books (6) Python-DVD-Training (1) Python-Exercises (263) Python-Framework (1) Python-IDE (1) Python-Kivy-Framework (2) Python-Modules (1) Python-pdf (2) Python-pyQt (1) Référencement (2) Script PHP (2) Security (6) SEO (1) Snipping Tool: Faq (1) Social Networks (1) Source Code (1) Statistics With SPSS (2) Surveillance Software (1) Travail à domicile (6) Tutoriels php en vidéos (2) Tutoriels-MySql (6) tutoriels-php (19) Utilitaires (1) VPS (1) Web Hosting (1) Webcam (1) Webmarketing (11) Western Union (1) Windows 10 (1) Windows 7 (4) Windows 7 Faq (2) Windows 8 (1) Windows Accessories (1) Windows Download (8) Windows Drivers (1) Windows Fonts (1) Windows Power Shell (2) Windows Registry (2) Windows Security (18) Windows Software (2) Windows Spyware (2) Windows utilities (3) Windows Virus (2) Windows Vista (3) Windows Wireless (1) Windows xp (1) Wordpress (1)
 

Sample text

Sample Text

 
Blogger Templates