Limbaje Formale 3

Curs
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 12 în total
Cuvinte : 2673
Mărime: 202.64KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Andrei Grigoras
Limbaje si relatii de echivalenta ,modele de automate.

Extras din document

3.4 Definiţie. Fie x, y, z ∈ A* şi w = xyz . x se numeşte prefix al lui w, y se numeşte

factor al lui w, iar z se numeşte sufix al lui w.

În cazul în care unul dintre x,y,z este diferit de cuvântul vid, ε , la denumirea dată

mai sus i se ataşează adjectivul „propriu” ( de exemplu, pentru x,îl vom numi prefix

propriu). Orice scriere a unui w∈ A* ca şi concatenare de tipul n w u u ...u 1 2 = , unde

u A* i ∈ , va fi numită factorizare a lui w.

Este clar că, dat un alfabet A, semigrupul liber pe A, A+ are foarte multe cuvinte

( Ν ) A însă nu orice cuvânt poate avea o semnificaţie în întelegerea noastră. Să

exemplificăm:

3.2 Exemple.

10 În aritmetica elementară se utilizeaza

alfabetul A ={0,1,2...,9}∪{+,−,⋅,:, =}∪ {(,)}.

Cuvântul (+ ⋅)9 , de exemplu, nu are nici o semnificaţie în aritmetică. Mai mult,

împărţirea prin 0 nu este definită, deci un cuvânt de forma 9:0=1 nu poate apărea în

aritmetică. În schimb, 1+3=4, este un cuvânt în aritmetică.

20 Fie A alfabetul constituit din toate cuvintele limbii române. Cuvintele, pe post

de simboluri, pot fi alăturate pentru a obţine, de exemplu, propoziţii, care vor fi cuvinte

peste A. Însa nu orice alăturare de simboluri dau cuvinte coerente în limba română:

(Studiem, limbaje, formale, şi, teoria, automatelor) are sens, în schimb (formale,

şi, limbaje, studiem, automatelor, teoria) ?!! ☺

Aceste exemple fac naturală urmatoarea:

3.5 Definiţie. Fie A un alfabet. Se numeşte limbaj peste A o submulţime L din P(A*).

3.3 Exemple.

10 Fie A alfabetul din exemplul 3.2, 10. Putem considera L ca fiind limbajul

tuturor adunărilor corecte din aritmetică. Aşadar cuvântul 11+13=24 este în limbaj, in

timp ce 9:3=3, chiar dacă este corect din p.d.v. aritmetic, nu se află în limbajul L.

20 In informatică, mulţimea tuturor programelor corecte din punct de vedere

sintactic într-un anumit limbaj, cum ar fi Java, constitue un limbaj.

În cele ce urmează, vom introduce diferite operaţii cu limbaje - adică moduri în

care putem „combina” limbajele pentru obţinerea unora noi.

Dupa cum s-a definit notiunea de limbaj, este clar ca multimea tuturor limbajelor

pe alfabetul A este Ρ(A*). Aşadar putem vorbi de aşa numitele „operaţii Booleene”,

adică intersecţia, reuniunea, şi complementarierea. Astfel, dacă L şi M sunt limbaje peste

acelaşi alfabet A, avem:

L ∪M ={w∈ A* w∈ L sau w∈M} - reuniunea

L ∩M ={w∈ A* w∈ L si w∈M} - intersecţia

cL = A* L ={w∈ A* w∉ L} - complementul lui L

Pe lângă cele definite mai sus, mai avem şi L M = {w∈ A* w∈ L si w∉M} diferenţa

Preview document

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

Conținut arhivă zip

  • Limbaje Formale 3.pdf

Alții au mai descărcat și

Crearea unui Arhivator și a Unui Dezarhivator

Introducere „Un calculator, nu face ceea ce vrei tu sa faca, dar ceea ce îi spui sa faca” - Legea lui Murphy C/C++ sunt limbaje, si sunt...

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

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?