img138

138

10. Metody ciągowe

iP₄: produkcje generujące D: (1), (2), (3), (4), (6), (7), (8) oraz

(15)    5₇ —* 4S₁₂,

(16)    5,₂ - 45,3,

(17) 5,3-^55,4,

(18)    5,4 - 65,,,

(19)    5,_s - $,

^ = ^iU<P₂U5P₃U^4,

En = {5,5;}, i = 1,2,..., 15,

Et = {$,0,2,3,4,5,6}.

Po skonstruowaniu gramatyki <5_r, zbudujemy deterministyczny automat 21 o skończonej liczbie stanów, rozpoznający poszczególne wzorce liter. Automat 21 określamy według następujących reguł:

21 = (Ey, Q, ń, 9o, F),

gdzie (1) Ej := Er,

(2)    Q := En,

(3)    to := S,

(4)    F := 0,

(5)    jeśli produkcja postaci A, —► aA₂ € V, A,,A₂ e En, a e Er, to ó(A,,o) := A₂,

(6)    jeśli produkcja postaci A, —> $ 6 ?P, $ 6 Et jest produkcją kończącą generację obrazu Lit, to ó(A,,$) := Lit oraz Q := Q U {Lit}, F -.= FU {Lit},

(7)    dla pozostałych par postaci (A,,a), które nie zostały rozpatrzone w punktach (5) i (6) ó(A,,a) := err, gdzie err jest stanem nierozpoznania obrazu (oczywiście Q := Q U {err}, F := F U {err}).

W naszym przykładzie mamy:

(1)    Ey = {$,0,2,3,4,5,6},

(2)    Q = {S,Si,I,P,R,D,err}, i = 1,2,..., 15,

(3)    go = S,