Limbaje Formale 4

Curs
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 8 în total
Cuvinte : 1544
Mărime: 175.16KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Andrei Grigoras
Descrierea tabelara diagrama grafului de tranzitie si exemple .

Extras din document

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

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

Conținut arhivă zip

  • Limbaje Formale 4.pdf

Alții au mai descărcat și

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ă....

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...

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?