Cuprins
- Cuprins
- 1 Ierarhia lui Chomsky. Generari de limbaje 3
- 1.1 Introducere 3
- 1.2 Generari de limbaje 5
- 1.3 Exercitii propuse spre rezolvare 24
- 2 Automate nite 38
- 2.1 Introducere 38
- 2.2 Sumatorul binar 41
- 2.3 Relatiile A;s0 si L 44
- 2.4 Constructia automatului minimal 54
- 2.5 Legatura dintre automate nite deterministe si cele nite nedeterministe 61
- 2.6 Legatura dintre limbaje regulate si automate nite 65
- 2.7 Lema de pompare Bar-Hillel 71
- 2.8 Sisteme tranzitionale 74
- 2.8.1 Un algoritm e cient pentru conversia dintre un sistem tranzitional
- si un automat nit nedeterminist 76
- 2.9 Expresii regulate 80
- 2.10 Exercitii propuse spre rezolvare 95
- 3 Limbaje independente de context 104
- 3.1 Automate pushdown nedeterministe 104
- 3.1.1 Un algoritm e cient pentru conversia dintre un automat push-
- down nedeterminist si o gramatica de tip 2 112
- 3.2 Lema de pompare pentru limbaje de tip 2 116
- 3.3 Forma normala Chomsky 124
- 3.4 Forma normala Greibach 127
- 3.5 Forma normala operator 132
- 3.5.1 Un algoritm e cient pentru conversia dintre o gramatica ^n
- forma normala Chomsky si o gramatica^n forma normala operator134
- 3.6 Limbaje independente de context deterministe 136
- 3.7 Probleme decidabile ^n clasa L2 138
- 3.7.1 Un algoritm e cient de analiza sintactica pentru gramatici ^n
- forma normala Chomsky 145
- 1
- 2
- 3.8 Problema echivalentei a doua gramatici independente de context 152
- 3.9 Exercitii propuse spre rezolvare 156
- 4 Masini Turing si automate liniar marginite 163
- 4.1 Masini Turing 163
- 4.2 Automate liniar marginite 178
- 4.3 Legatura dintre gramaticile dependente de context si gramaticile mono-
- tone 180
- 4.4 Exercitii propuse spre rezolvare 186
Extras din curs
Capitolul 1
Ierarhia lui Chomsky.
Generari de limbaje
1.1 Introducere
Termenul de gramatica a fost atribuit sistemelor generative din respect pentru lingvis-
tul si losoful Noam Chomsky1. Domnia sa este primul care a folosit aceste sisteme
generative pentru de nirea unei gramatici sintactice" pentru limba engleza. Printre
alte rezultate referitoare la gramaticile formale, ^n anul 1956, acesta le clasi ca pe
tipuri, clasi care care ^i poarta numele.
De nitia 1.1.1 Numim alfabet o multime nita si nevida (elementele sale le numim
simboluri). Vom numi cuv^ant peste V o aplicatie p : f1; 2; :::; ng ! V; numarul
n = jpj numindu-se lungimea cuv^antului p:
Notatia 1.1.1 Prin V
n = fp=p : f1; 2; :::; ng ! V g ^ntelegem multimea cuvintelor
de lungime n: Notam cu V - = S n0
V
n si cu V
+ = S n1
V
n
:
De nitia 1.1.2 Se numeste gramatica (sau sistem generativ) un 4-uplu G =
(VN; VT ; x0; P), unde:
- VN este o multime nita si nevida, numita multimea neterminalilor (vari-
abilelor);
- VT este o multime nita si nevida, numita multimea terminalilor, astfel
^nc^at:
{ VN VT = ;;
{ V = VN [ VT se numeste alfabetul gramaticii G;
1Profesor la Departamentul de lingvistica si loso e, Massachusetts Institute of Technology, Cam-
bridge, U.S.A.
3
Introducere 4
- x0 2 VN este simbolul de start al gramaticii G;
- P - V - VN V - V - este multimea regulilor de generare (productiilor).
Notatia 1.1.2 Pentru o gramatica G; o regula din P se noteaza cu (u; v) sau u ! v:
De nitia 1.1.3 Fie G = (VN; VT ; x0; P) o gramatica arbitrara. Se numeste
derivare directa (derivare ^ntr-un pas) relatia binara =)
G
- V
- V
- de nita astfel:
( ; ) 2=)
G
daca 9 u ! v 2 P astfel ^nc^at = 1u 2; = 1v 2:
Notatia 1.1.3 Pentru ( ; ) 2=)
G
se utilizeaza de obicei notatia =)
G
:
De nitia 1.1.4 ^Inchiderea re
exiva si tranzitiva a relatiei de derivare directa se
numeste derivare. Mai precis, vom spune ca se deriveaza din ^n G; notatie
- =)
G
, daca
- = sau
- 9 n 1 si 9 u1; u2; :::; un astfel ^nc^at = u1; = un si ui =)
G
ui+1; 8 i =
1; n
Preview document
Conținut arhivă zip
- Limbaje Formale si Translatoare.pdf
Alții au mai descărcat și
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...
1.1 Scopul cursului Cursul se adreseaza angajatilor care au un nivel elementar de cunostinte Excel, pentru a ajunge la nivelul mediu pentru ca mai...
Bitii din registrul Flag sunt indicatori de stare care se pozitioneaza functie de rezultatul ultimei operatii aritmetice sau logice si se testeaza...
Metode add (MenuItem) Adds the specified item to this menu. add(String) Adds an item with with the specified label to this menu....
Clasa ObjectInputStream Constructor public ObjectInputStream( java.io.InputStream in ) throws java.io.IOException,...
Functii de intrare / iesire relative la siruri de caractere. Pentru a citi un sir de caractere de la intrarea standard se foloseste functia gets()...
Te-ar putea interesa și
Smart Choice UML este o lucrare de cercetare care are ca scop analiza instrumentelor UML disponibile pentru proiectarea sistemelor informatice de...
I. EXPRESII REGULATE 1. Introducere Ce este o expresie regulată- O expresie regulată, pe scurt denumită şi RegEx sau RegExp, este un şir de...
1. Cercetarea de marketing international În conditiile complexe ale pietei internationale, cercetarea de marketing devine vitala pentru...
I. 1. Descrierea Programului Programul reprezinta o aplicatie a unit-ului graph, un joc simplu de strategie (gen TBS, daca ar fi sa-l incadram in...
CAPITOLUL1 METODOLOGII MODERNE DE REALIZARE A SISTEMELOR INFORMATICE 1.1. Concepte de bază ale paradigmei obiectuale Aplicată mai întâi în...
INTRODUCERE Obiectul disciplinei: limbajele de programare Obiective: · Studiul conceptelor fundamentale care stau la baza proiectării...
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...
Fazele dezvoltării unui produs software 1 Ce este ingineria programării? 2. Fazele ingineriei programării 2.1. Faza de analiză 2.2. Faza de...