Limbaje Formale Automate si Compilatoare
-
Upload
vlad-andrei-tabacariu -
Category
Documents
-
view
174 -
download
16
description
Transcript of Limbaje Formale Automate si Compilatoare
Limbaje Formale, Automate si Compilatoare
Curs 1
LFAC (2013-14) Curs 1 1 / 34
Limbaje Formale, Automate si Compilatoare
Curs:
O.Captarencu: [email protected],
http://www.infoiasi.ro/ ˜ otto/lfac.html
Gh. Grigoras: [email protected]
Laboratoare:
O.Captarencu
A. Moruz: [email protected]
C. Lita: [email protected]
Pagina cursului:
http://www.infoiasi.ro/ ˜ otto/lfac.html
LFAC (2013-14) Curs 1 2 / 34
Evaluare
7 seminarii, 6 laboratoare;
AS = activitatea la seminar (max 10 puncte);
AL = activitatea la laborator (max 10 puncte);
T1,T2 teste scrise ın saptamanile 8, respectiv ın sesiune;
Punctajul final se obtine astfel:
P = 3 ∗ AS + 3 ∗ AL + 2 ∗ T 1 + 2 ∗ T 2
Conditii miminale de promovare: AS ≥ 5, AL ≥ 5;
Punctaj minim pentru promovare: P ≥ 50;
Nota finala se va stabili conform criteriilor ECTS;
LFAC (2013-14) Curs 1 3 / 34
Evaluare
AS = activitatea la seminar (max 10 puncte)
8 puncte din 2 teste scrise2 puncte activitatea la seminar
AL = activitatea la laborator (max 10 puncte)
1 test scris, 2 teme laborator (note de la 0 la 10)
AL = media celor 3 note
LFAC (2013-14) Curs 1 4 / 34
Tematica cursului I
Limbaje si gramatici
Limbaje regulate; gramatici, automate , expresii regulate
Limbaje independente de context; gramatici, automate pushdown
Masini Turing
LFAC (2013-14) Curs 1 5 / 34
Tematica cursului II
Limbaje de programare: proiectare si implementare
Analiza lexicala
Analiza sintactica
Traducere ın cod intermediar
LFAC (2013-14) Curs 1 6 / 34
Tematica seminarului
Exemple de limbaje si gramatici
Automate finite deterministe, nedeterministe, cu epsilon-tranzitii -
Exemple
Expresii regulate
Gramatici independente de context, arbori de derivare, eliminarea
simbolurilor inutile, eliminarea regulilor de stergere, a
redenumirilor
Forma normala Chomsky, algoritmul CYK
Automate pushdown - exemple
LFAC (2013-14) Curs 1 7 / 34
Tematica laboratorului
Analiza lexicala folosind instrumente de tip LEX
Analiza sintactica folosind instrumente de tip YACC
Interpretor construit cu LEX si YACC
LFAC (2013-14) Curs 1 8 / 34
Bibliografie
Grigoras, Gh. Constructia compilatoarelor - Algoritmi fundamentali, Ed.
Universitatii Al. I. ”Cuza Iasi”, ISBN 973-703-084-2, 274 pg., 2005
Jucan Toader - Limbaje formale si automate, Editura Matrix Rom, Bucuresti,
1999, 162 p.
Jucan Toader, Stefan Andrei Limbaje formale si teoria automatelor. Teorie si
practica, Editura Universitatii Al. I. Cuza, Iasi, 2002, 327p.
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006).Introduction to
Automata Theory, Languages, and Computation(3rd ed.). Addison-Wesley
Stoughton Alley, Formal Language Theory, Kansas State University, Draft of Fall
2007.
Manual LEX, Manual FLEX, Manual YACC, Manual Bison,
Compiler Construction using Flex and Bison
LFAC (2013-14) Curs 1 9 / 34
Limbaje formale
Curs 1
1 Limbaje formale
2 Gramatici
3 Ierarhia lui Chomsky
4 Gramatici si limbaje de tip 3 (regulate)
Proprietati de ınchidere
LFAC (2013-14) Curs 1 10 / 34
Limbaje formale
Alfabet, cuvant, multime de cuvinte
Alfabet: V o multime finita (elemente lui V = simboluri )
Simbolurile le vom nota a, b, etc.
LFAC (2013-14) Curs 1 11 / 34
Limbaje formale
Alfabet, cuvant, multime de cuvinte
Alfabet: V o multime finita (elemente lui V = simboluri )
Simbolurile le vom nota a, b, etc.
Cuvant: sir finit de simboluri
cuvintele le vom nota u, v , w ...
cuvantul nul notat ǫ sau λ
LFAC (2013-14) Curs 1 11 / 34
Limbaje formale
Alfabet, cuvant, multime de cuvinte
Alfabet: V o multime finita (elemente lui V = simboluri )
Simbolurile le vom nota a, b, etc.
Cuvant: sir finit de simboluri
cuvintele le vom nota u, v , w ...
cuvantul nul notat ǫ sau λ
Lungimea unui cuvant u: numarul simbolurilor sale. Notatie: |u|
|ǫ| = 0
LFAC (2013-14) Curs 1 11 / 34
Limbaje formale
Alfabet, cuvant, multime de cuvinte
Alfabet: V o multime finita (elemente lui V = simboluri )
Simbolurile le vom nota a, b, etc.
Cuvant: sir finit de simboluri
cuvintele le vom nota u, v , w ...
cuvantul nul notat ǫ sau λ
Lungimea unui cuvant u: numarul simbolurilor sale. Notatie: |u|
|ǫ| = 0
V ∗ - multimea tuturor cuvintelor peste alfabetul V , inclusiv ǫ
{0, 1}∗ = {ǫ, 0, 1, 00, 01, 10, 11, 000, 001, ...}
LFAC (2013-14) Curs 1 11 / 34
Limbaje formale
Alfabet, cuvant, multime de cuvinte
Alfabet: V o multime finita (elemente lui V = simboluri )
Simbolurile le vom nota a, b, etc.
Cuvant: sir finit de simboluri
cuvintele le vom nota u, v , w ...
cuvantul nul notat ǫ sau λ
Lungimea unui cuvant u: numarul simbolurilor sale. Notatie: |u|
|ǫ| = 0
V ∗ - multimea tuturor cuvintelor peste alfabetul V , inclusiv ǫ
{0, 1}∗ = {ǫ, 0, 1, 00, 01, 10, 11, 000, 001, ...}
V+ - multimea tuturor cuvintelor nenule peste alfabetul V
{0, 1}+ = {0, 1, 00, 01, 10, 11, 000, 001, ...}
LFAC (2013-14) Curs 1 11 / 34
Limbaje formale
Concatenarea a doua cuvinte x , y : cuvantul x · y obtinut dinsimbolurile lui x , ın ordinea ın care apar, urmate de cele ale lui yde asemenea ın ordinea ın care apar:
x = 0100, y = 100, x · y = 0100100
x = 000, y = ǫ, x · y = 000
LFAC (2013-14) Curs 1 12 / 34
Limbaje formale
Concatenarea a doua cuvinte x , y : cuvantul x · y obtinut dinsimbolurile lui x , ın ordinea ın care apar, urmate de cele ale lui yde asemenea ın ordinea ın care apar:
x = 0100, y = 100, x · y = 0100100
x = 000, y = ǫ, x · y = 000
Concatenarea este asociativa
ǫ este element neutru
LFAC (2013-14) Curs 1 12 / 34
Limbaje formale
Concatenarea a doua cuvinte x , y : cuvantul x · y obtinut dinsimbolurile lui x , ın ordinea ın care apar, urmate de cele ale lui yde asemenea ın ordinea ın care apar:
x = 0100, y = 100, x · y = 0100100
x = 000, y = ǫ, x · y = 000
Concatenarea este asociativa
ǫ este element neutru
(V ∗, ·) este monoid, se numeste monoidul liber generat de V
LFAC (2013-14) Curs 1 12 / 34
Limbaje formale
Concatenarea a doua cuvinte x , y : cuvantul x · y obtinut dinsimbolurile lui x , ın ordinea ın care apar, urmate de cele ale lui yde asemenea ın ordinea ın care apar:
x = 0100, y = 100, x · y = 0100100
x = 000, y = ǫ, x · y = 000
Concatenarea este asociativa
ǫ este element neutru
(V ∗, ·) este monoid, se numeste monoidul liber generat de V
Cuvantul v este un prefix al cuvantului u daca ∃w ∈ V ∗,u = vw ;
daca w ∈ V+ , atunci v este un prefix propriu
LFAC (2013-14) Curs 1 12 / 34
Limbaje formale
Concatenarea a doua cuvinte x , y : cuvantul x · y obtinut dinsimbolurile lui x , ın ordinea ın care apar, urmate de cele ale lui yde asemenea ın ordinea ın care apar:
x = 0100, y = 100, x · y = 0100100
x = 000, y = ǫ, x · y = 000
Concatenarea este asociativa
ǫ este element neutru
(V ∗, ·) este monoid, se numeste monoidul liber generat de V
Cuvantul v este un prefix al cuvantului u daca ∃w ∈ V ∗,u = vw ;
daca w ∈ V+ , atunci v este un prefix propriu
Cuvantul v este un sufix al cuvantului u daca ∃w ∈ V ∗,u = wv ;
daca w ∈ V+, atunci v este un sufix propriu
LFAC (2013-14) Curs 1 12 / 34
Limbaje formale
Limbaj formal
Fie V un alfabet. O submultime L ⊆ V ∗ este un limbaj (formal)
peste alfabetul V (sau V-limbaj) daca L are o descriere finita.
O descriere poate fi:
LFAC (2013-14) Curs 1 13 / 34
Limbaje formale
Limbaj formal
Fie V un alfabet. O submultime L ⊆ V ∗ este un limbaj (formal)
peste alfabetul V (sau V-limbaj) daca L are o descriere finita.
O descriere poate fi:- neformala (ın limbaj natural):
multimea cuvintelor peste alfabetul {0, 1} care contin un numar par
de 0 .
L = {x ∈ V+ : |x |este par}.
{anbn|n ∈ N}.
{w ∈ {0, 1}∗|w se termina in 00}.
LFAC (2013-14) Curs 1 13 / 34
Limbaje formale
Limbaj formal
Fie V un alfabet. O submultime L ⊆ V ∗ este un limbaj (formal)
peste alfabetul V (sau V-limbaj) daca L are o descriere finita.
O descriere poate fi:- neformala (ın limbaj natural):
multimea cuvintelor peste alfabetul {0, 1} care contin un numar par
de 0 .
L = {x ∈ V+ : |x |este par}.
{anbn|n ∈ N}.
{w ∈ {0, 1}∗|w se termina in 00}.
- formala (descriere matematica):
o descriere inductiva a cuvintelor
o descriere generativa a cuvintelor (gramatica generativa)
o descriere a unei metode de recunoastere a cuvintelor din limbaj
(automat finit, automat pushdown, etc.)
LFAC (2013-14) Curs 1 13 / 34
Limbaje formale
Operatii cu limbaje
Operatiile cu multimi (reuniune, intersetie etc)
Produs de limbaje: L1 · L2 = {uv |u ∈ L1, v ∈ L2}
Iteratia (produsul Kleene): L∗ =⋃
n≥0 Ln, unde:
L0 = {ǫ}
Ln+1 = LnL
LR = {wR |w ∈ L}; daca w = a1a2 . . . an, atunci wR = an . . . a2a1
LFAC (2013-14) Curs 1 14 / 34
Gramatici
Curs 1
1 Limbaje formale
2 Gramatici
3 Ierarhia lui Chomsky
4 Gramatici si limbaje de tip 3 (regulate)
Proprietati de ınchidere
LFAC (2013-14) Curs 1 15 / 34
Gramatici
Gramatici
Definitie 1
O gramatica este un sistem G = (N,T ,S,P), unde:1 N si T sunt doua alfabete disjuncte
N este multimea neterminalilor
T este multimea terminalilor
2 S ∈ N este simbolul de start (neterminalul initial)
3 P este o multine finita de reguli (productii) de forma x → y, unde
x , y ∈ (N ∪ T )∗ si x contine cel putin un neterminal.
LFAC (2013-14) Curs 1 16 / 34
Gramatici
Derivare
Fie G = (N,T ,S,P) o gramatica si u, v ∈ (N ∪ T )∗.
Spunem ca v este derivat direct (ıntr-un pas) de la u prin aplicarea
regulii x → y , si notam u ⇒ v , daca ∃p,q ∈ (N ∪ T )∗ astfel ıncat
u = pxq si v = pyq
LFAC (2013-14) Curs 1 17 / 34
Gramatici
Derivare
Fie G = (N,T ,S,P) o gramatica si u, v ∈ (N ∪ T )∗.
Spunem ca v este derivat direct (ıntr-un pas) de la u prin aplicarea
regulii x → y , si notam u ⇒ v , daca ∃p,q ∈ (N ∪ T )∗ astfel ıncat
u = pxq si v = pyq
Daca u1 ⇒ u2 . . . ⇒ un, n > 1, spunem ca un este derivat din u1 ın
G si notam u1 ⇒+ un.
LFAC (2013-14) Curs 1 17 / 34
Gramatici
Derivare
Fie G = (N,T ,S,P) o gramatica si u, v ∈ (N ∪ T )∗.
Spunem ca v este derivat direct (ıntr-un pas) de la u prin aplicarea
regulii x → y , si notam u ⇒ v , daca ∃p,q ∈ (N ∪ T )∗ astfel ıncat
u = pxq si v = pyq
Daca u1 ⇒ u2 . . . ⇒ un, n > 1, spunem ca un este derivat din u1 ın
G si notam u1 ⇒+ un.
Scriem u ⇒∗ v daca u ⇒+ v sau u = v .
LFAC (2013-14) Curs 1 17 / 34
Gramatici
Limbaj generat
Definitie 2
Limbajul generat de gramatica G este:
L(G) = {w ∈ T ∗|S ⇒+ w}
LFAC (2013-14) Curs 1 18 / 34
Gramatici
Limbaj generat
Definitie 2
Limbajul generat de gramatica G este:
L(G) = {w ∈ T ∗|S ⇒+ w}
Definitie 3
Doua gramatici G1 si G2 sunt echivalente daca L(G1) = L(G2)
LFAC (2013-14) Curs 1 18 / 34
Gramatici
Exemplu
L = {anbn|n ≥ 1}
Definitia inductiva:
- ab ∈ L- Daca X ∈ L, atunci aXb ∈ L
- Nici un alt cuvant nu face parte din L
LFAC (2013-14) Curs 1 19 / 34
Gramatici
Exemplu
L = {anbn|n ≥ 1}
Definitia inductiva:
- ab ∈ L- Daca X ∈ L, atunci aXb ∈ L
- Nici un alt cuvant nu face parte din L
Definitia generativa:
- G = ({X}, {a, b},X ,P), unde P = {X → aXb,X → ab}- Derivarea cuvantului a3b3:
X ⇒ aXb ⇒ aaXbb ⇒ aaabbb
LFAC (2013-14) Curs 1 19 / 34
Gramatici
Exemplu
L = {anbncn|n ≥ 1}
G = (N,T ,S,P), N = {S,X}, T = {a,b, c}, P consta din:
- (1) S → abc
- (2) S → aSXc- (3) cX → Xc
- (4) bX → bb
Derivarea cuvantului a3b3c3: S ⇒(2) aSXc ⇒(2) aaSXcXc ⇒(1)
aaabcXcXc ⇒(3) aaabXccXc ⇒(4) aaabbccXc ⇒(3)
aaabbcXcc ⇒(3) aaabbXccc ⇒(4) aaabbbccc = a3b3c3
LFAC (2013-14) Curs 1 20 / 34
Ierarhia lui Chomsky
Curs 1
1 Limbaje formale
2 Gramatici
3 Ierarhia lui Chomsky
4 Gramatici si limbaje de tip 3 (regulate)
Proprietati de ınchidere
LFAC (2013-14) Curs 1 21 / 34
Ierarhia lui Chomsky
Clasificarea gramaticilor
1 Gramatici de tip 0 (generale)
Nu exista restrictii asupra regulilor
LFAC (2013-14) Curs 1 22 / 34
Ierarhia lui Chomsky
Clasificarea gramaticilor
1 Gramatici de tip 0 (generale)
Nu exista restrictii asupra regulilor
2 Gramatici de tip 1 (dependente de context)
reguli de forma pxq → pyq unde x ∈ N, y 6= ǫ, p, q ∈ (N ∪ T )∗
S → ǫ, caz ın care S nu apare ın dreapta productiilor
LFAC (2013-14) Curs 1 22 / 34
Ierarhia lui Chomsky
Clasificarea gramaticilor
1 Gramatici de tip 0 (generale)
Nu exista restrictii asupra regulilor
2 Gramatici de tip 1 (dependente de context)
reguli de forma pxq → pyq unde x ∈ N, y 6= ǫ, p, q ∈ (N ∪ T )∗
S → ǫ, caz ın care S nu apare ın dreapta productiilor
3 Gramatici de tip 2 (independente de context)
reguli de forma A → y unde A ∈ N si y ∈ (N ∪ T )∗
LFAC (2013-14) Curs 1 22 / 34
Ierarhia lui Chomsky
Clasificarea gramaticilor
1 Gramatici de tip 0 (generale)
Nu exista restrictii asupra regulilor
2 Gramatici de tip 1 (dependente de context)
reguli de forma pxq → pyq unde x ∈ N, y 6= ǫ, p, q ∈ (N ∪ T )∗
S → ǫ, caz ın care S nu apare ın dreapta productiilor
3 Gramatici de tip 2 (independente de context)
reguli de forma A → y unde A ∈ N si y ∈ (N ∪ T )∗
4 Gramatici de tip 3 (regulate)
A → u sau A → uB unde A,B ∈ N si u ∈ T ∗.
LFAC (2013-14) Curs 1 22 / 34
Ierarhia lui Chomsky
Exemple
Ce tip au urmatoarele gramatici?
G = (N,T ,S,P), N = {S,A,B}, T = {a,b, c}, P:
(1)S → aaAc
(2)aAc → aAbBc
(3)bB → bBc
(4)Bc → Abc
(5)A → a
G = (N,T ,S,P), N = {S,X}, T = {a,b, c}, P:
(1)S → abc
(2)S → aSXc
(3)cX → Xc
(4)bX → bb
LFAC (2013-14) Curs 1 23 / 34
Ierarhia lui Chomsky
Exemple
FieG = ({E}, {a,+,−, (, )},E , {E → a,E → (E +E),E → (E −E)}).
Ce tip are gramatica G ?Construiti derivari din E pentru cuvintele (a + a) si ((a + a)− a)
Cuvantul (a + a − a) poate fi derivat din E?Descrieti limbajul L(G)
Fie G = ({A,B}, {a,b},A, {A → aA,A → B,B → bB,B → ǫ})
Ce tip are gramatica G ?Descrieti limbajul L(G)
LFAC (2013-14) Curs 1 24 / 34
Ierarhia lui Chomsky
Ierarhia lui Chomsky
Un limbaj L este de tipul j daca exista o gramatica G de tipul j
astfel ıncat L(G) = L, unde j ∈ {0,1,2,3}.
Vom nota cu Lj clasa limbajelor de tipul j , unde j ∈ {0,1,2,3}.
Ierarhia lui Chomsky: L3 ⊂ L2 ⊂ L1 ⊂ L0
Incluziunile sunt stricte:
orice limbaj de tip j + 1 este si de tip j ∈ {0, 1, 2}exista limbaje de tip j care nu sunt de tip j + 1, j ∈ {0, 1, 2}
LFAC (2013-14) Curs 1 25 / 34
Ierarhia lui Chomsky
Proprietati
Fiecare din familiile Lj cu 0 ≤ j ≤ 3 contine toate limbajele finite.
Fiecare din familiile Lj cu 0 ≤ j ≤ 3 este ınchisa la operatia de
reuniune:
L1,L2 ∈ Lj =⇒ L1 ∪ L2 ∈ Lj ,
∀j : 0 ≤ j ≤ 3
LFAC (2013-14) Curs 1 26 / 34
Gramatici si limbaje de tip 3 (regulate)
Curs 1
1 Limbaje formale
2 Gramatici
3 Ierarhia lui Chomsky
4 Gramatici si limbaje de tip 3 (regulate)
Proprietati de ınchidere
LFAC (2013-14) Curs 1 27 / 34
Gramatici si limbaje de tip 3 (regulate)
Gramatici de tip 3
O gramatica G = (N,T ,S,P) este de tip 3, daca regulile sale sunt
de forma A → u sau A → uB unde A,B ∈ N si u ∈ T ∗.
Exemplu: G = ({D}, {0,1, . . . ,9},D,P)
Unde P este:
D → 0D|1D|2D| . . . |9D
D → 0|1| . . . |9
LFAC (2013-14) Curs 1 28 / 34
Gramatici si limbaje de tip 3 (regulate)
Exemple
Fie gramatica G = ({A,B}, {l ,d},A,P)
unde P este:
A → lB, B → lB|dB|ǫ (l = litera, d = cifra)
LFAC (2013-14) Curs 1 29 / 34
Gramatici si limbaje de tip 3 (regulate)
Exemple
Fie gramatica G = ({A,B}, {l ,d},A,P)
unde P este:
A → lB, B → lB|dB|ǫ (l = litera, d = cifra)
L(G): multimea identificatorilor
LFAC (2013-14) Curs 1 29 / 34
Gramatici si limbaje de tip 3 (regulate)
Exemple
Fie gramatica G = ({A,B}, {l ,d},A,P)
unde P este:
A → lB, B → lB|dB|ǫ (l = litera, d = cifra)
L(G): multimea identificatorilor
Fie gramatica G = ({A,B}, {+,−,d},A,P)
unde P este:
A → +dB| − dB|dB, B → dB|ǫ (d = cifra)
LFAC (2013-14) Curs 1 29 / 34
Gramatici si limbaje de tip 3 (regulate)
Exemple
Fie gramatica G = ({A,B}, {l ,d},A,P)
unde P este:
A → lB, B → lB|dB|ǫ (l = litera, d = cifra)
L(G): multimea identificatorilor
Fie gramatica G = ({A,B}, {+,−,d},A,P)
unde P este:
A → +dB| − dB|dB, B → dB|ǫ (d = cifra)
L(G): multimea constantelor ıntregi
LFAC (2013-14) Curs 1 29 / 34
Gramatici si limbaje de tip 3 (regulate)
Forma normala
O gramatica de tip 3 este ın forma normala daca regulile sale sunt
de forma A → a sau A → aB, unde a ∈ T , si eventual S → ǫ ( caz
ın care S nu apare ın dreapta regulilor).
Pentru orice gramtica de tip 3 exista o gramatica echivalenta ın
forma normala
Se poate arata ca pot fi eliminate regulile de forma A → B (redenumiri) si cele de
forma A → ǫ (reguli de stergere), cu exceptia, eventual a regulii S → ǫ
Orice regula de forma A → a1a2 . . . an se ınlocuieste cu A → a1B1, B1 → a2B2,...,
Bn−2 → an−1Bn−1, Bn−1 → an n > 1, B1, . . . ,Bn−1 fiind neterminali noi
Orice regula de forma A → a1a2 . . . anB se ınlocuieste cu A → a1B1,
B1 → a2B2,...,Bn−2 → an−1Bn−1, Bn−1 → anB, n > 1, B1, . . . ,Bn−1 fiind
neterminali noi
Transformarile care se fac nu modifica limbajul generat de gramatica
LFAC (2013-14) Curs 1 30 / 34
Gramatici si limbaje de tip 3 (regulate) Proprietati de ınchidere
Fie L,L1,L2 limbaje regulate: exista gramaticile G,G1,G2 de tip 3
astfel ca L = L(G),L1 = L(G1) si L2 = L(G2).
Atunci, urmatoarele limbaje sunt de asemenea regulate:
1 L1 ∪ L2
2 L1 · L2
3 L∗
4 LR
5 L1 ∩ L2
6 L1 \ L2
LFAC (2013-14) Curs 1 31 / 34
Gramatici si limbaje de tip 3 (regulate) Proprietati de ınchidere
Inchiderea la reuniune
Fie G1 = (N1,T1,S1,P1) si G2 = (N2,T2,S2,P2) gramatici de tip 3 cu
L1 = L(G1), L2 = L(G2).
Presupunem N1 ∩ N2 = ∅ si gramaticile ın forma normala
Inchiderea la reuniune: se arata ca L1 ∪ L2 ∈ L3:
Gramatica G = (N1 ∪N2 ∪{S},T1 ∪T2,S,P1 ∪P2 ∪{S → S1,S → S2})
este de tip 3 si genereaza limbajul L1 ∪ L2
LFAC (2013-14) Curs 1 32 / 34
Gramatici si limbaje de tip 3 (regulate) Proprietati de ınchidere
Inchiderea la produs
Gramatica G = (N1 ∪ N2,T1 ∪ T2,S1,P) unde P consta din:
regulile de forma A → aB din P1
reguli A → aS2 pentru orice regula A → a din P1
toate regulile din P2
este de tip 3 si genereaza limbajul L1L2
LFAC (2013-14) Curs 1 33 / 34
Gramatici si limbaje de tip 3 (regulate) Proprietati de ınchidere
Inchiderea la iteratie
Fie G = (N,T ,S,P) de tip 3 care genereaza L (L = L(G)).
Presupunem ca simbolul de start S nu apare ın partea dreapta a
vreunei reguli.
Gramatica G′ = (N,T ,S,P ′) unde P ′ consta din
reguli A → aB din P
reguli A → aS, pentru orice regula A → a din P
regula S → ǫ
este de tip 3 si genereaza L∗
LFAC (2013-14) Curs 1 34 / 34