Exemplu N1 LFC

7/25/2019 Exemplu N1 LFC

http://slidepdf.com/reader/full/exemplu-n1-lfc 1/4

Lucrarea de laborator N1 la disciplina LFPC

Sarcina lucrării:

1. Pentru gramatica formală G = (VN, VT, P, S) construiţi 5 şiruri, care aparţin limbajuluiL(G) generat de această gramatică. Lungimea şirului trebuie să fie nu mai mică, dect

numărul de caractere din alfabet ! "#$.$. Pentru fiecare şir să se construiască arborii de deri%are.&. 'esenaţi automatul finit eci%alent acestei gramatici.. La ce clasă al gramaticilor după *oms+ aparţine gramatica dată-

! " /0, , 2, 34, ! /a, b, c, e, n, f, m4,P/

1. 06a$. 6b2

&. 6f. 26n25. 26c07. 6e3 8. 36m3 9. 6e:. 36m4

!ectuarea lucrării:

1) *onstruim 5 şiruri ce aparţin limbajului L(G) generat de această gramatică;

1. 0<=a<=ab2<=abn2<=abnc0<=abnca<=abncae>

$. 0<=a<=af<=afb2<=afbc0<=afbca<=afbcae3<=afbcaem>

&. 0<=a<=af<=afb2<=afbc0<=afbca<=afbcae>

. 0<=a<=ab2<=abn2<=abnc0<=abnca<=abncae>

5. 0<=a<=af<=afb2<=afbn2<=afbnc0<=afbnca<=afbncae3<=afbncaem.



$) Pentru fiecare şir construim arborii de deri%are;

1.

0 ?@

a ?@ b 2 ?@ n 2 ?@ c 0 ?@ a

? e

$.

0 ?@

a ?@ f ?@ b 2 ?@ c 0 ?@ a

?@ e 3

? m

&.

0 ?@

a ?@ f ?@ b 2 ?@ c 0 ?@ a

? e

.

0 ?@

a ?@ b 2 ?@ n 2 ?@ c 0 ?@ a

? e

5.

0 ?@

a ?@ f ?@ b 2 ?@ n 2 ?@ c 0

?@ a ?@ e 3 ? m

&) *onstruim AB(automatul finit) eci%alent acestei gramatici;

"F=(#, , , $%, F), unde

# & 'uli'ea de stări

*ocabular

!uncia de tran+iie

$% & starea iniială

F & 'uli'ea stărilor !inale

"lorit'ul de construire "F:

1. C ! "∪/D4/0, , 2, 3 , D4

$. Σ!/a, b, c e, n, f, m 4

&. EF0. B/D4

5. Pentru toate producţiile definim ;

niţial toate mulţimile δ(A, b); F1. 0 →a



δ(0, a); δ (0, a)∪/4/4

$. → b2

δ(, b); δ (, b)∪/24/24

&. →f

δ(, f); δ (, f)∪/4/4

. 2 →n2

δ(2, n); δ (2, n)∪/24/24 5. 2 →c0

δ(2, c); δ (2, c)∪/04/04

7. →e3

δ(, e); δ (, e)∪/34/34

8. 3 →m3

δ(3, m); δ (3, m)∪/34/34

9. →e

δ(, e);

δ (, e)

∪/D4/3, D4

:. 3 →m

δ(3, m); δ (3, m)∪/D4/3, D4

epreHentarea grafică a AB;

&) Gramatica dată după *oms+ aparţine tipului &, deoarece toate producţiiledate sunt de forma;

a) A→a

b) A→ bI

Jnde T V ba ∈, şi N V B A ∈,

2

3

D

0

a

b

f

n

e

m

e

mc

Exemplu N1 LFC

Documents

Transcript of Exemplu N1 LFC