Extras din curs
Reamintim
1.1 Definiţie. Se numeşte semiautomat un triplet M = (S,Σ ,δ ) , unde :
- S este o mulţime finită numită mulţimea stărilor;
- Σ este o mulţime finită numită alfabet de intrare;
- δ : S ×Σ → P (S) este o funcţie parţială numită funcţie de tranziţie.
În cazul în care |δ (s,a) |≤ 1, (∀)(s,a), M se numeşte semiautomat determinist. Dacă
există (s,a) ∈ S ×Σ astfel încât |δ (s,a) |< 1, M se numeşte semiautomat incomplet şi
dacă avem |δ (s,a) |= 1(∀)(s,a) ∈ S ×Σ , M se numeşte semiautomat complet. În toate
celelalte cazuri, M se numeşte semiautomat nedeterminist.
În cele ce urmează ne vom ocupa doar de semiautomatele deterministe, iar δ o
vom considera ca o funcţie parţială de la S ×Σ la S .
Pentru descrierea unui semiautomat avem două posibilităţi: prima ar fi descrierea
funcţiei de tranziţie în mod tabelar (sau matriceal) iar cea de a doua ar fi cu ajutorul unui
graf orientat etichetat. Să prezentăm aceste două variante:
Descrierea tabelară.
Se utilizează o matrice, de dimensiune | S | × | Σ |; Pe locul etichetat (s,a) din
matrice se pune valoarea funcţiei de tranziţie în (s,a) adică δ (s, a):
δ L a L
M
s
M
M
Lδ (s, a) L
M
În cazul unui semiautomat incomplet (adică δ este o funcţie partială), dacă δ (s,a) = φ
vom pune în matrice, pe locul (s,a), multimea vidă.
Diagrama (Graful) de tranziţie.
Fie M = (S, Σ,δ) semiautomat. Fie G = (S, E) graful orientat care are drept mulţime de
noduri, mulţimea stărilor semiautomatului M, S, iar ca mulţime de arce mulţimea
{( , ) /( ) : ( , ) }. i j i j E = s s ∃ a ∈Σ δ s a = s Acestui graf orientat îi asociem o funcţie de
etichetare, α , definită astfel:
Fie e ∈ E; rezultă că s s S i j (∃) , ∈ astfel încât e = (si, sj). Vom asocia lui e, prin
α , toate intrările cu ( , ) ,i j a ∈Σ δ s a = s adică ( ) { ; ( , ) }.i j α e = a ∈Σ δ s a = s Aşadar,
funcţia de etichetare este de la E la P (Σ ,)α : E → P (Σ ).
1.1 Exemple. (continuare din cursul precedent)
3) Fie S ={0,1, 2},Σ ={a,b} şi δ descrisă prin tabelul:
În acest
Preview document
Conținut arhivă zip
- Limbaje Formale 4.pdf