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

Memorii RAM și ROM

Capitolul I – Generalitati I.1. Introducere Memoria este absolut necesara pentru functionarea microprocesorului si a PC-ului. Mai mult, memoria...

Algoritmica Grafurilor

Curs 1 1.Notatii.Definitii Multiset – S multime finita, S!=VID R=(S,r) r:S->N³0, r=functie multiplicitate r:S->{0,1} => def partilor lui S (R)...

Subiecte și Probleme IP

1. Într-o aplicatie trebuie sa se tina evidenta persoanelor dintr-o colectivitate, a locului de munca si a adreselor de e-mail. a. Sa se...

Programare în Limbaj de Asamblare

Bitii din registrul Flag sunt indicatori de stare care se pozitioneaza functie de rezultatul ultimei operatii aritmetice sau logice si se testeaza...

Retele de Calculatoare

Capitolul 1: Notiuni generale În acest capitol va veti familiariza cu rolul pe care îl joaca calculatorul în cadrul unei retele. Cu cît stiti mai...

Microprocesoare

Stiinta calculatoarelor se caracterizeaza printr-o deosebita dinamicitate. Desi foarte scurta, de aproximativ 60 de ani, istoria stiintei...

Partitionarea si Formatarea HDD

In aceasta sectiune vor fi prezentate pe scurt citeva date despre functionarea hardiscului, ca si despre pregatirea acestuia pentru stocarea de...

Microprocesoare

Z80 contine în plus fata de 8080, ca si componente structurale specifice, registrele de 8 biti A’, F’, B’, C’, D’, E’, H’, L’ numite secundare,...

Ai nevoie de altceva?