Limbaje Formale 5

Curs
6.5/10 (2 voturi)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 11 în total
Cuvinte : 1783
Mărime: 283.18KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Andrei Grigoras
Automate Mealy definitii si exemple.

Extras din document

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

Limbaje Formale 5 - Pagina 1
Limbaje Formale 5 - Pagina 2
Limbaje Formale 5 - Pagina 3
Limbaje Formale 5 - Pagina 4
Limbaje Formale 5 - Pagina 5
Limbaje Formale 5 - Pagina 6
Limbaje Formale 5 - Pagina 7
Limbaje Formale 5 - Pagina 8
Limbaje Formale 5 - Pagina 9
Limbaje Formale 5 - Pagina 10
Limbaje Formale 5 - Pagina 11

Conținut arhivă zip

  • Limbaje Formale 5.pdf

Alții au mai descărcat și

AutoCad

APERTURE - controleazã mãrimea cursorului selector, caracteristic modului object snap. ARC - traseazã un arc de cerc de orice dimensiune. A -...

Biblioteca de Șabloane Standard

Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...

Clase Derivate

1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...

Clase în Java

Clase pentru miniaplicatii Miniaplicatiile constituie extensii ale unei clase deja existente java.applet.Applet. Structura clasei unui applet...

Clase

1. Programare procedurala –Programare orientata pe obiecte. Limbajul C, ca si Pascal, utilizeaza modelul programarii structurate procedurale, care...

Comunicații internet

2.1. Stilurile caracterelor {n sfirsit pagina dvs. contine ceva, chiar daca este vorba numai de un nume. Vom analiza in continuare elementele de...

Crearea unei aplicații independente în Java

Toate aplicatiile Java contin o metoda main(), spre deosebire de miniaplicatii. class FirstApp { public static void main( String argsst) {...

Curs Excel

Deplasarea prin foi Deplasarea dintr-o foaie in alta se face cu clic cu mouse-ul pe eticheta foii dorite. Deplasarea prin celule Va puteti...

Te-ar putea interesa și

Limbaje Formale

1. Reprezentaţi automatul sub formă de graf. 2. Construiţi gramatica regulată echivalentă cu automatul dat. 3. Este sau nu automatul dat...

Limbaje Formale și Automate

#include <iostream.h> #include <conio.h> #include <string.h> #include "afd.h" #include "afdc.h" #define L 100 void main(){ clrscr(); AFD a;...

Limbaje formale și proiectarea compilatoarelor

Scopul lucrării: 1.Pentru gramatica formală G=(VN, VT, P, S) construiţi 5 şiruri care aparţin limbajului L(G) generat de această gramatică....

Lucrări de laborator Limbaje formale și automate

Lucrarea practică № 1 1. Pentru gramatica formală G=(VN, VT, P, S) construiți 5 șiruri care aparțin limbajului L(G) generat de această gramatică....

Limbaje Formale și Translatoare

1. Introducere Curs1 LFT Limbajele de nivel înalt au o serie de avantaje în raport cu limbajele de asamblare. Pentru a putea însă folosi limbaje...

Raport limbaje formale și automate 1

Scopul lucrării: - Construirea unei gramatici regulate; - De construit 11 producții și 5 cuvinte cu arborii lor de derivare pe baza gramaticii de...

Limbaje Formale - Curs 1

1. Introducere in limbaje formale. Definitii 2. Operatii pe limbaje 3. Expresii regulate 1. Introducere in limbaje formale. Definitii....

Limbaje Formale și Translatoare

Capitolul 1 Ierarhia lui Chomsky. Generari de limbaje 1.1 Introducere Termenul de gramatica a fost atribuit sistemelor generative din respect...

Ai nevoie de altceva?