Limbaje Formale

Curs
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 10 în total
Cuvinte : 2103
Mărime: 184.51KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Andrei Grigoras
Limbaje formale si automate. Despre semigrupusi si monoizi, relatii de echivalenta pe un singur semigrup , produsul semidirect, limbaje si semigrupuri .

Extras din document

Fie ρ ≤ A2 o relaţie oarecare.

În cele ce urmează vom incerca să determinăm cea mai mică (in sensul incluziunii

de mulţimi) relaţie de echivalenţă pe A care conţine ρ , adică relaţia de echivalenţă

generată de ρ . Dacă o vom nota, pentru moment, prin < ρ > , este clar că

< ρ > = I{τ ⊆ A2 |τ echivalenta, ρ ⊆τ }.

Această definiţie nu este foarte utilă din punct de vedere practic, ea este însă

folositoare atunci când este vorba de minimalitatea ei. Putem insă să o construim efectiv:

1.10 Definiţie. Relaţia = = ∪ ( )∪ ( )∪ ...

ρ Uρ ρ ρ o ρ ρ o ρ o ρ

n N

t n se numeşte închiderea

tranzitivă a relaţiei ρ .

Să observăm că ρ t este o relaţie tranzitivă şi, în plus, este inclusă in orice relaţie

tranzitivă ce conţine ρ .

Fie A ρ~ = ρ ∪ ρ −1 ∪ Δ . Această relaţie este, evident, reflexivă şi simetrică, şi este

cea mai mică (in sensul incluziunii) relaţie cu aceste proprietăţi ce include ρ .

Din acest moment este clar că avem:

1.1 Propoziţie. Relaţia de echivalenţă generată de ρ este t ρ ~ (inchiderea tranzitivă a lui

ρ ~

). În plus, b a b a t = ⇔ ρ ~ sau există şirul de elemente din A a c c c b n , = , ,....., = 1 2 astfel

incât ~ , ( ) 1, 1

1 = − + c c i n i i ρ (sau, echivalent, ( ) 1 1, 1, + ∀ = − i i i n c ρ c sau i i c ρ c +1 ).■

1.11 Definiţie. Fie A o mulţime, α ⊆ A× A o relaţie de echivalenţă peste A. O

submulţime B a lui A se numeste α - saturată dacă U[ ]

b B

B b

= α .

1.2 Propoziţie. În ipotezele precedente, B este α - saturată dacă şi numai dacă pentru

orice b B [b] ⊆ B α , .

Demonstraţie. "⇒:" este evidentă.

":" Deoarece [ ]α b b rezultă că U[ ]

b B

B b

α . Din ipoteză,

(∀)b B [b] ⊆ B α , , deci [b] B

b B

U

α , deci avem egalitatea cerută.■

2. Semigrupuri şi Monoizi

În general, mulţimilor intâlnite in matematică li se asociază şi o structură

algebrică, în sensul că suntem in măsură să adunăm sau să înmulţim elementele lor.

Dacă S este o mulţime nevidă, o operaţie binară pe S este o funcţie ϕ : S × S → S ,

valoarea lui ϕ intr-o pereche (x, y) din S2 fiind, în fond, valoarea obţinută prin aplicarea

operaţiei perechii (x, y); ϕ(x, y) se notează, pentru o scriere mai uşoară, prin x × y , x ⋅ y ,

x + y , ...

2.1 Definiţie.

Preview document

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

Conținut arhivă zip

  • Limbaje Formale.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?