Extras din curs
Automate Mealy
Până acum am studiat “masinile” fără nici o referire în ceea ce priveşte rezultatele
“muncii“ ei, adică “ieşirile“ maşinii.
Fie M = (S,Σ,δ ) un semiautomat şi să presupunem că, în plus, avem o altă
mulţime nevidă Ω, şi o funcţie γ : S ×Σ → P * (Ω) (funcţie de ieşire sau răspuns).
Un 5-uplu Mˆ = (S,Σ ,Ω ,δ ,γ ) este numit automat Mealy (introdus de G. Mealy
în 1955).
Putem vorbi, ca şi în cazul semiautomatelor, despre diferitele posibilităţi pe care
le avem în abordare, relativ la funcţia de ieşire. În acest caz, vom spune căMˆ este
determinist dacă . , ) ( 1 | ) , ( | | ) , ( | Σ ∈ ∈ ∀ ≤ = a S s a s a s γ δ În caz contrar, spunem că Mˆ este
nedeterminist.
Să descriem modul de lucru al maşinilor Mealy.
Presupunem că maşina se află în starea s şi se “aplică“ un simbol de intrare a. În
acest moment, automatul se deplasează în starea δ (s, a) = δ a (s) şi produce o ieşire
γ (s, a) ∈Ω . . Se obţine, în acest fel, şi o aplicaţie : S , (s) (s,a). a a γ → Ω γ = γ
Pentru a urmări ce se întâmplă atunci când maşinii i se aplică un cuvânt
... * ,
1 2 = ∈Σ n w a a a în starea s, putem privi automatul ca fiind o “cutie neagră“ înzestrată
cu două benzi, una de intrare pe care sunt scrise simbolurile lui w şi una de ieşire. Odată
ce maşina citeşte un simbol, de pe banda de intrare, ea îşi schimbă starea, şi, în acelaşi
moment, imprimă un simbol din Ω pe banda de ieşire. Reprezentăm, în figura
următoare, modul de lucru:
Starea finală, după introducerea cuvântului ... , este ( ) 1 2 w a a a s n ω = δ şi
cuvântul imprimat este *
1 2 ... ∈Ω n b b b , unde
( ), ( ( )),..., ( ... )( )). 1 1 2 2 1 1 1 b s b s b s a a a n an an a
γ γ δ γ δ o oδ
−
= = =
Din cele descrise mai înainte, este clar că un automat Mealy este o mulţime de
“traducători“, câte unul pentru fiecare stare internă a lui Mˆ şi fiecare “traduce“ un
cuvânt w∈Σ * de lungime n, într-un cuvânt de lungime n din Ω *.Aceasta ne conduce la
a spune că un traducător nu este altceva decât un caz special de morfism de semigrupuri.
Dacă Mˆ = (S,Σ ,Ω ,δ ,γ) este un automat Mealy, semiautomatul M = (S,Σ ,δ )
se numeşte semiautomatul ataşat automatului Mˆ . Din definiţie, este clar că
semiautomatul ataşat este unic determinat de automat. În plus, dat un semiautomat, el se
poate extinde la un automat, însă extinderea nu este unică.
În cele ce urmează, vom descrie câteva modalităţi de a obţine automate noi, prin
conectarea a două (sau mai multe) automate. Pentru a realiza aceasta, putem privi un
Preview document
Conținut arhivă zip
- Limbaje Formale 5.pdf