Limbaje Formale, Automate si Compilatoareotto/LFAC2019-20/lfac6.pdfEliminarea redenumirilor din...

Limbaje Formale, Automate si Compilatoare

Curs 6

2019-20

LFAC (2019-20) Curs 6 1 / 37

Curs 6

1 Eliminarea redenumirilor din gramatici de tip 2

2 Forma normala Chomsky

3 Problema recunoasterii: algoritmul Cocke Younger Kasami

4 Automate pushdown

5 Legatura dintre automatele pushdown si limbajele de tip 2

6 Automate pushdown deterministe

LFAC (2019-20) Curs 6 2 / 37

Eliminarea redenumirilor din gramatici de tip 2

Curs 6




4 Automate pushdown



LFAC (2019-20) Curs 6 3 / 37


Eliminarea redenumirilor (A → B, A,B ∈ N)

Intrare: G = (N,T ,S,P)

Iesire: G′ = (N,T ,S,P′), L(G′) = L(G), P′ nu contine redenumiri

for(A ∈ N){

N0 = {A}; i = 0;

do{

i = i + 1;

Ni = Ni−1 ∪ {C|C ∈ N, ∃B → C ∈ P,B ∈ Ni−1};

} while Ni 6= Ni−1;

NA = Ni ; //NA = {X ∈ N|A ⇒∗ X}

}

P′ = {X → α ∈ P|α 6∈ N}

for(X → α1|α2| . . . |αn ∈ P′)

for(A ∈ N && X ∈ NA,X 6= A)

P′ = P′ ∪ {A → α1|α2| . . . |αn}

LFAC (2019-20) Curs 6 4 / 37


Exemplu

G = ({x , y , z}, {a, b, c}, x ,P), unde P:

x → y |ax |a

y → z|by |b

z → cz|c

Nx = {x , y , z}, Ny = {y , z}, Nz = {z}

Gramatica echivalenta fara redenumiri G′ = ({x , y , z}, {a, b, c}, x ,P ′)

unde P ′:

x → ax |a|by |b|cz|c

y → by |b|cz|c

z → cz|c

LFAC (2019-20) Curs 6 5 / 37

Forma normala Chomsky

Curs 6




4 Automate pushdown



LFAC (2019-20) Curs 6 6 / 37



Definitie 1

O gramatica este ın forma normala Chomsky daca regulile sale au

forma:

A → BC, A → a ( si eventual S → ǫ) (A,B,C ∈ N si a ∈ T).

Teorema 1

Orice limbaj independent de context poate fi generat de o gramatica ın

forma normala Chomsky.

LFAC (2019-20) Curs 6 7 / 37


Demonstratie

Se elimina regulile de stergere si redenumirile

LFAC (2019-20) Curs 6 8 / 37


Demonstratie


Se elemina regulile care nu sunt ın forma normala Chomsky:Daca A → x1x2 . . . xn, n > 1 este o astfel de regula atunci oınlocuim cu A → Y1Y2 . . .Yn unde:

Yi = xi , daca xi ∈ N (neterminalii raman la fel)Yi = xa daca xi = a ∈ T (xa este neterminal nou) si se adaugaregula xa → a

LFAC (2019-20) Curs 6 8 / 37


Demonstratie


Se elemina regulile care nu sunt ın forma normala Chomsky:Daca A → x1x2 . . . xn, n > 1 este o astfel de regula atunci oınlocuim cu A → Y1Y2 . . .Yn unde:

Yi = xi , daca xi ∈ N (neterminalii raman la fel)Yi = xa daca xi = a ∈ T (xa este neterminal nou) si se adaugaregula xa → a

O regula de forma A → Y1Y2 . . .Yn , daca n > 2, o ınlocuim cu:A → Y1Z1

Z1 → Y2Z2

. . . . . .

Zn−3 → Yn−2Zn−2

Zn−2 → Yn−1Yn,unde Z1,Z2, . . . ,Zn−2 sunt neterminali noi.

LFAC (2019-20) Curs 6 8 / 37


Exemplu

G = ({S,A}, {a, b, c},S,P), unde P:

S → aSb|cAc

A → cA|c

Gramatica echivalenta ın forma normala Chomsky

G = ({S,A, xa, xb,Z1,Z2}, {a, b, c},S,P ′), unde P ′:

S → xaZ1|xcZ2

Z1 → Sxb

Z2 → Axc

A → xcA|c

xa → a

xb → b

xc → cLFAC (2019-20) Curs 6 9 / 37

Problema recunoasterii: algoritmul Cocke Younger Kasami

Curs 6




4 Automate pushdown



LFAC (2019-20) Curs 6 10 / 37


Algoritmul Cocke Younger Kasami (CYK)

Problema recunoasterii ın gramatici de tip 2: data o gramatica de

tip 2 si un cuvant w, sa se decida daca w ∈ L(G)

Problema recunoasterii ın gramatici ın forma normala Chomsky se

poate rezolva cu algoritmul CYK ın timp O(n3).

Daca w = a1a2 . . . an atunci se constuiesc multimile

Vij = {A|A ⇒+ aiai+1 . . . ai+j−1}

inductiv pentru j = 1, . . . , n

w ∈ L(G) ⇔ S ∈ V1n

LFAC (2019-20) Curs 6 11 / 37


Algoritmul Cocke Younger Kasami

Pentru j = 1:

Vi1 = {A|A ⇒+ ai} = {A|∃A → ai ∈ P}

Pentru j > 1, Vij :

Daca A ⇒+ aiai+1 . . . ai+j−1:

A ⇒ BC ⇒+ aiai+1 . . . ai+j−1 si

B ⇒+ aiai+1 . . . ai+k−1 (B ∈ Vik )

C ⇒+ ai+k ai+k+1 . . . ai+j−1 (C ∈ Vi+k j−k )

unde 1 ≤ i ≤ n + 1 − j , 1 ≤ k ≤ j − 1

Vij =⋃j−1

k=1{A|A → BC ∈ P,B ∈ Vik ,C ∈ Vi+k j−k}

LFAC (2019-20) Curs 6 12 / 37



Notatie:

{A|A → BC ∈ P,B ∈ Vik ,C ∈ Vi+k j−k} = Vik ◦ Vi+k j−k

Atunci:

pentru 2 ≤ j ≤ n, 1 ≤ i ≤ n + 1 − j :

Vij =

j−1⋃

k=1

(Vik ◦ Vi+k j−k )

LFAC (2019-20) Curs 6 13 / 37



Intrare: G = (N,T ,S,P) ın forma normala Chomsky, w = a1a2 . . . an

Iesire: w ∈ L(G)?

for(i=1; i<=n; i++)

Vi1 = {A|∃A → ai ∈ P};

for(j=2; j<=n; j++)

for (i=1; i<=n+1-j; i++){

Vij = ∅;

for(k=1; k<=j-1; k++)

Vij = Vij ∪ (Vik ◦ Vi+k j−k );

}

if(S ∈ V1n) w ∈ L(G) else w 6∈ L(G)

LFAC (2019-20) Curs 6 14 / 37


Exemplu

G = ({S,X ,Y ,Z}, {a, b, c},S,P), unde P:

S → XY

X → XY |a

Y → YZ |a|b

Z → c

w = abc

LFAC (2019-20) Curs 6 15 / 37


Exemplu

G = ({S,X ,Y ,Z}, {a, b, c},S,P), unde P:

S → XY

X → XY |a

Y → YZ |a|b

Z → c

w = abc

V11 = {X ,Y} V12 = {S,X} V13 = {S,X}

V21 = {Y} V22 = {Y}

V31 = {Z}

S ∈ V13 ⇔ abc ∈ L(G)

LFAC (2019-20) Curs 6 15 / 37

Automate pushdown

Curs 6




4 Automate pushdown



LFAC (2019-20) Curs 6 16 / 37

Automate pushdown

Automate pushdown

Automat finit + memorie pushdown (stiva)

Model fizic:

LFAC (2019-20) Curs 6 17 / 37

Automate pushdown

Automate pushdown-definitie

Definitie 2

Un automat pushdown este un 7-uplu: M = (Q,Σ, Γ, δ, q0, z0,F ):

Q este multimea (finita) a starilor

Σ este alfabetul de intrare

Γ este alfabetul memoriei pushdown (stivei)

q0 ∈ Q este starea initiala

z0 ∈ Γ este simbolul initial din stiva

F ⊆ Q este multimea starilor finale

δ : Q × (Σ ∪ {ǫ})× Γ → 2Q×Γ∗

Modelul este nedeterminist

LFAC (2019-20) Curs 6 18 / 37

Automate pushdown

Configuratia unui automat pushdown

Configuratie: (q,w , γ) ∈ Q × Σ∗ × Γ∗

1 : γ (primul simbol din γ) reprezinta varful stivei

LFAC (2019-20) Curs 6 19 / 37

Automate pushdown

Automate pushdown

Configuratie initiala: (q0,w , z0) ∈ Q × Σ∗ × Γ∗

LFAC (2019-20) Curs 6 20 / 37

Automate pushdown

Relatia de tranzitie ıntre configuratii

Configuratia curenta (q, aw , zβ) si (q′, α) ∈ δ(q, a, z)

(q, q′ ∈ Q, a ∈ Σ ∪ {ǫ}, z ∈ Γ, α, β ∈ Γ∗)

LFAC (2019-20) Curs 6 21 / 37

Automate pushdown


(q, aw , zβ) ⊢ (q′,w , αβ)

LFAC (2019-20) Curs 6 22 / 37

Automate pushdown


Fie M = (Q,Σ, Γ, δ, q0, z0,F ) un automat pushdown.

Relatia de tranzitie ıntre configuratii:

(q, aw , zβ) ⊢ (q′,w , αβ) daca (q′, α) ∈ δ(q, a, z)

(q, q′ ∈ Q, a ∈ Σ ∪ {ǫ}, z ∈ Γ, α, β ∈ Γ∗)

Calcul: ınchiderea reflexiva si tranzitiva a relatiei de mai sus: daca

C1, . . . ,Cn configuratii astfel ıncat:

C1 ⊢ C2 ⊢ . . . ⊢ Cn

se scrie: C1 ⊢+ Cn daca n ≥ 2, C1 ⊢∗ Cn, daca n ≥ 1

LFAC (2019-20) Curs 6 23 / 37

Automate pushdown

Limbajul recunoscut

Prin stari finale (daca F 6= ∅)

L(M) = {w ∈ Σ∗|(q0,w , z0) ⊢∗ (q, ǫ, γ), q ∈ F , γ ∈ Γ∗}

Prin golirea stivei (daca F = ∅)

Lǫ(M) = {w ∈ Σ∗|(q0,w , z0) ⊢∗ (q, ǫ, ǫ), q ∈ Q}

LFAC (2019-20) Curs 6 24 / 37

Automate pushdown

Exemplu

Automat care recunoaste limbajul {anbn|n ≥ 1}:

M = ({q0, q1, q2}, {a, b}, {a, z}, δ, q0, z, {q2})

1 δ(q0, a, z) = {(q0, az)}

2 δ(q0, a, a) = {(q0, aa)}

3 δ(q0, b, a) = {(q1, ǫ)}

4 δ(q1, b, a) = {(q1, ǫ)}

5 δ(q1, ǫ, z) = {(q2, ǫ)}

LFAC (2019-20) Curs 6 25 / 37

Automate pushdown

Exemple

Un automat pushdown ce recunoaste limbajul {wawR |w ∈ {0, 1}∗}

LFAC (2019-20) Curs 6 26 / 37

Automate pushdown

Exemple


Fiecare 0 sau 1 citit se introduce ın stiva

a la intrare produce pregatirea scoaterii a cate un simbol din stiva daca el

coincide cu cel din intrare

LFAC (2019-20) Curs 6 26 / 37

Automate pushdown

Exemple





M = ({q0, q1, q2}, {0, 1, a}, {0, 1, z}, δ, q0, z, {q2})

1 δ(q0, i , z) = {(q0, iz)}, (i ∈ {0,1})2 δ(q0, i , j) = {(q0, ij)}, (i , j ∈ {0,1})3 δ(q0,a, i) = {(q1, i)}4 δ(q1, i , i) = {(q1, ǫ)}5 δ(q1, ǫ, z) = {(q2, ǫ)}

LFAC (2019-20) Curs 6 26 / 37

Automate pushdown

Exemple





M = ({q0, q1, q2}, {0, 1, a}, {0, 1, z}, δ, q0, z, {q2})


Un automat pushdown ce recunoaste limbajul {wwR |w ∈ {0, 1}∗} ?

LFAC (2019-20) Curs 6 26 / 37

Automate pushdown

Exemple





M = ({q0, q1, q2}, {0, 1, a}, {0, 1, z}, δ, q0, z, {q2})


Un automat pushdown ce recunoaste limbajul {wwR |w ∈ {0, 1}∗} ?

Un automat pushdown ce recunoaste limbajul {ww |w ∈ {0, 1}∗} ?

LFAC (2019-20) Curs 6 26 / 37

Automate pushdown

Echivalenta definitiilor privind recunoasterea

Teorema 2

Pentru orice automat pushdown M cu F = ∅, exista un automat

pushdown M ′ cu stari finale astfel ca L(M ′) = Lǫ(M).

LFAC (2019-20) Curs 6 27 / 37

Automate pushdown


Teorema 2



Daca M = (Q,Σ, Γ, δ, q0, z0, ∅), consideram

M ′ = (Q ∪ {qf , q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, {qf}) cu δ′:

LFAC (2019-20) Curs 6 27 / 37

Automate pushdown


Teorema 2




M ′ = (Q ∪ {qf , q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, {qf}) cu δ′:

1 δ′(q′0, ǫ, z

′0) = {(q0, z0z ′

0)} (fara sa citeasca niciun simbol, M ′ trece

ın configuratia initiala a lui M)

LFAC (2019-20) Curs 6 27 / 37

Automate pushdown


Teorema 2




M ′ = (Q ∪ {qf , q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, {qf}) cu δ′:

1 δ′(q′0, ǫ, z

′0) = {(q0, z0z ′



2 δ′(q, a, z) = δ(q, a, z), ∀q ∈ Q, a ∈ Σ ∪ {ǫ}, z ∈ Γ (M ′ face

aceleasi tranzitii ca si M)

LFAC (2019-20) Curs 6 27 / 37

Automate pushdown


Teorema 2




M ′ = (Q ∪ {qf , q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, {qf}) cu δ′:

1 δ′(q′0, ǫ, z

′0) = {(q0, z0z ′



2 δ′(q, a, z) = δ(q, a, z), ∀q ∈ Q, a ∈ Σ ∪ {ǫ}, z ∈ Γ (M ′ face

aceleasi tranzitii ca si M)

3 δ′(q, ǫ, z ′0) = {(qf , ǫ)}, ∀q ∈ Q (M ′ va trece ın starea finala doar

daca stiva lui M este vida)

LFAC (2019-20) Curs 6 27 / 37

Automate pushdown


Teorema 3

Pentru orice automat pushdown M cu F 6= ∅, exista un automat

pushdown M ′ cu F = ∅ astfel ca Lǫ(M ′) = L(M).

LFAC (2019-20) Curs 6 28 / 37

Automate pushdown


Teorema 3

Pentru orice automat pushdown M cu F 6= ∅, exista un automat

pushdown M ′ cu F = ∅ astfel ca Lǫ(M ′) = L(M).

Daca M = (Q,Σ, Γ, δ, q0, z0,F ), consideram

M ′ = (Q ∪ {qǫ, q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, ∅)

LFAC (2019-20) Curs 6 28 / 37

Automate pushdown

Demonstratie

M ′ = (Q ∪ {qǫ, q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, ∅), cu δ′:

LFAC (2019-20) Curs 6 29 / 37

Automate pushdown

Demonstratie

M ′ = (Q ∪ {qǫ, q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, ∅), cu δ′:

1 δ′(q′0, ǫ, z

′0) = {(q0, z0z ′



LFAC (2019-20) Curs 6 29 / 37

Automate pushdown

Demonstratie

M ′ = (Q ∪ {qǫ, q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, ∅), cu δ′:

1 δ′(q′0, ǫ, z

′0) = {(q0, z0z ′


ın configuratia initiala a lui M)2 a) δ′(q,a, z) = δ(q,a, z), ∀q ∈ Q, a ∈ Σ, z ∈ Γ (M ′ face aceleasi

tranzitii ca si M, pentru orice simbol ıntalnit)b) δ′(q, ǫ, z) = δ(q, ǫ, z), daca q ∈ Q \ F , z ∈ Γ (se fac aceleasi

ǫ-tranzitii ca ın M, daca starea nu este finala )c) δ′(q, ǫ, z) = δ(q, ǫ, z) ∪ {(qǫ, ǫ)}, q ∈ F , z ∈ Γ (daca M ajunge ıntr-o

stare finala, M ′ poate trece ıntr-o stare speciala )

LFAC (2019-20) Curs 6 29 / 37

Automate pushdown

Demonstratie

M ′ = (Q ∪ {qǫ, q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, ∅), cu δ′:

1 δ′(q′0, ǫ, z

′0) = {(q0, z0z ′






3 δ′(q, ǫ, z ′0) = {(qǫ, ǫ)}, daca q ∈ F ( cazul 2(c), ın situatia ın care ın

stiva este z ′0)

LFAC (2019-20) Curs 6 29 / 37

Automate pushdown

Demonstratie

M ′ = (Q ∪ {qǫ, q′0},Σ, Γ ∪ {z ′

0}, δ′, q′

0, z′0, ∅), cu δ′:

1 δ′(q′0, ǫ, z

′0) = {(q0, z0z ′






3 δ′(q, ǫ, z ′0) = {(qǫ, ǫ)}, daca q ∈ F ( cazul 2(c), ın situatia ın care ın

stiva este z ′0)

4 δ′(qǫ, ǫ, z) = {(qǫ, ǫ)}, daca z ∈ Γ ∪ {z ′0} ( M ′ ramane ın starea qǫ

si se extrage varful stivei)LFAC (2019-20) Curs 6 29 / 37

Legatura dintre automatele pushdown si limbajele de tip 2

Curs 6




4 Automate pushdown



LFAC (2019-20) Curs 6 30 / 37


Automatul pushdown echivalent cu o gramatica de tip

2

Teorema 4

Pentru orice gramatica G exista un automat pushdown M fara stari

finale astfel ıncat Lǫ(M) = L(G)

LFAC (2019-20) Curs 6 31 / 37


Automatul pushdown echivalent cu o gramatica de tip

2

Teorema 4

Pentru orice gramatica G exista un automat pushdown M fara stari

finale astfel ıncat Lǫ(M) = L(G)

Fie G = (N,T ,S,P)

Construim M = ({q},T ,N ∪ T , δ, q,S, ∅) unde:1 δ(q, ǫ,A) = {(q, β)|A → β ∈ P}, ∀A ∈ N2 δ(q,a,a) = {(q, ǫ)}, ∀a ∈ T3 δ(q, x , y) = ∅, ın restul cazurilor

w ∈ L(G) ⇔ S ⇒+ w ⇔ (q,w ,S) ⊢+ (q, ǫ, ǫ) ⇔ w ∈ Lǫ(M)

M simuleaza derivarile extrem stangi din G

LFAC (2019-20) Curs 6 31 / 37


Exemplu

G = ({x}, {a, b}, x , {x → axb, x → ab})

Automatul pushdown echivalent:

M = ({q}, {a, b}, {a, b, x}, δ, q, x , ∅)

1 δ(q, ǫ, x) = {(q,axb), (q,ab)}2 δ(q,a,a) = {(q, ǫ)}3 δ(q,b,b) = {(q, ǫ)}

LFAC (2019-20) Curs 6 32 / 37


Gramatica echivalenta cu un automat pushdown

Teorema 5

Pentru orice automat pushdown M exista o gramatica G astfel ıncat

L(G) = Lǫ(M)

LFAC (2019-20) Curs 6 33 / 37


Gramatica echivalenta cu un automat pushdown

Teorema 5

Pentru orice automat pushdown M exista o gramatica G astfel ıncat

L(G) = Lǫ(M)

Fie M = (Q,Σ, Γ, δ, q0, z0, ∅)

Construim G = (N,Σ,S,P) astfel:- N = {[qzp]|p,q ∈ Q, z ∈ Γ} ∪ {S}

- P contine toate regulile de forma:S → [q0z0q], ∀q ∈ Q

daca (p, ǫ) ∈ δ(q, a, z), atunci:

[qzp] → a

daca (p, z1z2 . . . zm) ∈ δ(q, a, z), atunci, pentru orice secventa de

stari q1, . . . , qm ∈ Q :

[qzqm] → a[pz1q1][q1z2q2] . . . [qm−1zmqm]

Are loc: [qzp] ⇒+ w ⇔ (q,w , z) ⊢+ (p, ǫ, ǫ)LFAC (2019-20) Curs 6 33 / 37

Automate pushdown deterministe

Curs 6




4 Automate pushdown



LFAC (2019-20) Curs 6 34 / 37



Definitie 3

Automatul pushdown M = (Q,Σ, Γ, δ, q0, z0,F ) este determinist daca

functia de tranzitie δ : Q × (Γ ∪ {ǫ})× Γ −→ 2Q×Γ∗ ındeplineste

conditiile:

1 |δ(q, a, z)| = 1, ∀a ∈ Σ ∪ {ǫ}, ∀q ∈ Q, ∀z ∈ Γ

2 Daca δ(q, ǫ, z) 6= ∅ atunci δ(q, a, z) = ∅, ∀a ∈ Σ

Un automat pushdown determinist poate avea ǫ-tranziii

LFAC (2019-20) Curs 6 35 / 37



Definitie 3

Automatul pushdown M = (Q,Σ, Γ, δ, q0, z0,F ) este determinist daca

functia de tranzitie δ : Q × (Γ ∪ {ǫ})× Γ −→ 2Q×Γ∗ ındeplineste

conditiile:

1 |δ(q, a, z)| = 1, ∀a ∈ Σ ∪ {ǫ}, ∀q ∈ Q, ∀z ∈ Γ

2 Daca δ(q, ǫ, z) 6= ∅ atunci δ(q, a, z) = ∅, ∀a ∈ Σ

Un automat pushdown determinist poate avea ǫ-tranziiiM = ({q0, q1, q2}, {0, 1, a}, {0, 1, z}, δ, q0, z, {q2})

1 δ(q0, i, z) = {(q0, iz)}, (i ∈ {0, 1})2 δ(q0, i, j) = {(q0, ij)}, (i, j ∈ {0, 1})3 δ(q0, a, i) = {(q1, i)}4 δ(q1, i, i) = {(q1, ǫ)}

5 δ(q1, ǫ, z) = {(q2, ǫ)}

L(M) = {wawR |w ∈ {0, 1}∗}LFAC (2019-20) Curs 6 35 / 37


L2DET - Limbaje de tip 2 deterministe

L2DET = {L|∃M automat pushdown determinist astfel ca L = L(M)}.

Clasa L2DET este o clasa proprie a clasei de limbaje L2

(L2DET ⊂ L2).

{wwR|w ∈ {0, 1}∗} ∈ L2 \ L2DET

LFAC (2019-20) Curs 6 36 / 37



L2DET = {L|∃M automat pushdown determinist astfel ca L = L(M)}.

Clasa L2DET este o clasa proprie a clasei de limbaje L2

(L2DET ⊂ L2).

{wwR|w ∈ {0, 1}∗} ∈ L2 \ L2DETM = ({q0, q1, q2}, {0, 1}, {0, 1, z}, δ, q0, z, {q2})

1 δ(q0, i, z) = {(q0, iz)}, (i ∈ {0, 1})2 δ(q0, i, j) = {(q0, ij)}, (i, j ∈ {0, 1}, i 6= j)3 δ(q0, i, i) = {(q0, ii), (q1, ǫ)}

4 δ(q1, i, i) = {(q1, ǫ)}

5 δ(q1, ǫ, z) = {(q2, ǫ)}

LFAC (2019-20) Curs 6 36 / 37



Definitie 4

O gramatica G este determinista daca:

Orice regula este de forma A → aα, unde a ∈ T iar α ∈ (N ∪ T )∗

Pentru orice A ∈ N, daca A → aα , A → bα′ sunt reguli, atunci

a 6= b

Pentru orice gramatica determinista G exista un automat pushdown

determinist M astfel ca L(G) = L(M)

LFAC (2019-20) Curs 6 37 / 37

Limbaje Formale, Automate si Compilatoareotto/LFAC2019-20/lfac6.pdfEliminarea redenumirilor din...

Documents

Transcript of Limbaje Formale, Automate si Compilatoareotto/LFAC2019-20/lfac6.pdfEliminarea redenumirilor din...