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

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?