lfpc2om

7/25/2019 LFPC2OM

1/15

Ministerul Educaiei, Tineretului i Sportului al Republicii Moldova

Universitate Tehnic a Moldovei

Catedra Automatica i Tehnologii n!ormaionale

"isciplina# $%&%'%C%

Lucrarea de laborator nr.2

Tema:Automate (nite

)*+

A e!ectuat# st% gr% C***,Ma-nic

.norina

A veri(cat# T% S/rbu

asistent

universitar

Chiinu 01*0

7/25/2019 LFPC2OM

2/15

Lucrarea de laborator Nr_ 2

la disciplina Limbaje formale i automate

Tema : Automate finite

*% Repre-entai automatul sub !orm de gra!%

0% Construii gramatica regulat echivalent cu automatul dat%

2% Este sau nu automatul dat determinist3 "e ce3

4% "ac automatul este nedeterminist, construii automatul (nit determinist

echivalent

Repre-entai A&" /n !orm de gra!%

5% nventai un ir peste vocabularul care nu va ( acceptat de ctre

automat% Artai acest lucru scriind secvena 6secvenele7 de con(guraii

respectiv%

+% 'entru automatul (nit A&869, , , :1, &7 construii 5 iruri acceptate de

automat% $ungimea irurilor s nu (e mai mic dec;t n8uvB%

Varianta 16

A&869, , , :1, &7,

9 8 :1, :*, :0, :2D,

8 a, b D, & 8 :2D%

6:1, a 7 8 :* ,

6:*, b 7 8 :* ,

6:*, b 7 8 :0,

6:0, a 7 8 :0,

6:0, b 7 8 :2,

7/25/2019 LFPC2OM

3/15

6:1, b 7 8 :1 %

1) Reprezentm automatul sub form de graf:

a b b

b

b a

07Construcia gramatica regulat echivalent cu automatul dat:

( )SPVVGTN ,,,=

1)V 8 9 8 :1, :*, :0, :2D

2)VT 8 8a, bD

3)S8:1

1!:1 a :*

"!:* b :*

#! :*b:0

$!:0 a :0

%!:0 b :2

6!:1b :1

&!:0 b

6:1, a 7 8 :*

6:*, b 7 8 :*

6:*, b 7 8 :0

6:0, a 7 8 :0

6:0, b 7 8 :2

6:1, b 7 8 :1

q3q

2q1

q0

7/25/2019 LFPC2OM

4/15

2) 'ste sau nu automatul dat determinist( e ce(

Automatul dat este nedeterminist, deoarece din starea :* prin b sepoate trece /n 0 stri di!erite# :1 sau :*

6:*,b7 8,:*:0D,

$) ac automatul este nedeterminist* construii automatul +nit

determinist echivalent!

Reprezentai ,- .n form de graf!

,-/ 0 2* * 2* 34 * -2)*

/ 5a* b

a b

b a

b

a

a

:*:0:*:1

:2

:*:0:2

:0

a b:1 :* :1:* :* :0:* :0 :0 :* :0:2 :0 :0 :2:* :0:2 :0 :* :0:2:2

7/25/2019 LFPC2OM

7/15

"! > 8 bbabaaab

b b a b a a a b

v B

v8bb

A8abaaab

2% > 8 babbbbaab

b a b b b b

a b

v B

v8b

A8abbbbaab

4% H8abaaaaab

b a b a a a a

b

:2:0:0:0:*:0:*:1:1:1

:2:0:0:*:0:2:*:0:2:*:0:2:*:0:*:1:1

:0 :0 :0 :0 :0:*:0:* :2:1

7/25/2019 LFPC2OM

8/15

u v

A

u8aba

v8aaaaA8b

5%>8abbbbbaab

a b b b b b

a b

u v

A

u8abb

v8bbb

A8aab

9istengul programului :

Bincludeiostream!hD

Bincludeconio!hD

Bincludemath!hD

Bincludestdlib!hD

void main0)5

int n*i*E*nr*F/4*num*num'*=/#*G/"*r/4*cont/4H

char lI"%%JI"4J*l1I"%%J

I"4J*I144J*'I144J*cuvintI"%%J/KL4K*shirI"%%JH

char start*+nal*c/242H

clrscr0)H

cout K,vem automatul +nit ,-/0*'*(*34*-)K endlH

:0:*:0:2 :2:0:*:0:2:*:0:2:*:0:2:*:0:*:1

7/25/2019 LFPC2OM

9/15

cout KCite stari avem in multimea : KH

cin DD numH

cout Kati starile: LnKH for 0i/4HinumHi;;)5

cout K3KHcin DD IiJH

cout KCite elemente avem in multimea a: KH

cin DD num'H

cout Kati elementele: LnKH for 0i/4Hinum'Hi;;)cin DD 'IiJH

cout Kati starea +nalaK endlK3KH

cin DD +nalH

cout KCite functii de tranzitie avem: KH

cin DD n H

cout Kati functiile de tranzitie:K endlH

for 0i/4HinHi;;)5

cout i;1 K! eKH

cin DD l1IiJH

clrscr0)H

MN ,+sarea Oatricei ,- NM

for 0i/4HinumHi;;)5

goto=G0=;"Ni*1)H

cout i H

goto=G01*G;i)H

cout i H

7/25/2019 LFPC2OM

10/15

goto=G0=;"*G)H cout 'I4JH

goto=G0=;"*G;1)H cout 'I1JH

goto=G0=;$*G;1)H cout 'I1JH

goto=G0"N=;=*"NG)H cout 'I4JHgoto=G0=*"NG)H cout 'I1JH

goto=G0"N=;=*G;#)H cout 'I4JH

goto=G0=*#NG)H cout 'I4JH

getch0)H

clrscr0)H

MN Construirea gramaticii regulate echivalente lui ,- NM

for 0i/4HinHi;;)5

if 0l1IiJI@JP/+nal)5

lIiJI4J/l1IiJI"JH

lIiJI1J/l1IiJI$JH

lIiJI"J/l1IiJI@JH

if 0l1IiJI@J//+nal)5

lIiJI4J/l1IiJI"JH

lIiJI1J/l1IiJI$JH

lIiJI"J/2L=42H

cout KQau obtinut productiile:K endlH

for 0i/4HinHi;;)5

if 0lIiJI"JP/2L42)

cout i;1 K! 3K lIiJI4J KDK lIiJI1J

7/25/2019 LFPC2OM

11/15

K3K lIiJI"J endlH

if 0lIiJI"J//2L42)

cout i;1 K! 3K lIiJI4J KDK lIiJI1J

endlH

getch0)H

MN Senerarea unui cuvint NM

clrscr0)H

randomize0)H

shirI4J/242H

cout KLn3K cH

do5

nr/random0n)H

if0lInrJI4J//c)

5 if 0lInrJI"JP/2L=42)

cout KDK lInrJI1J K3K lInrJI"JH

if 0lInrJI"J//2L=42)

cout KDK lInrJI1J H

c/lInrJI"JH

cuvintIFJ/lInrJI1JH

shirIF;1J/lInrJI"JH

F;;H

if0c//2L42)

if0FD/num;") goto e=itnoAH

else

7/25/2019 LFPC2OM

12/15

5

F/4H

c/242H

coutKLnKK34KHH Ahile01)H

e=itnoA:H

cuvintIFJ/2L42H

shirIFJ/2L42H

cout KLnCuvintul format este: K cuvint endlH

c/242H

getch0)H

MN Qecventa de con+guratii pentru acceptarea sirului NM

clrscr0)H

cout K034*=)/KH

i/4H

do 5

cout K03K shirIiJ K*KH

for 0iHiFHi;;)

cout cuvintIiJH

cout K)UKH

i/;;rH

Ahile 0iF)H

cout K03#*i)KH

7/25/2019 LFPC2OM

13/15

getch0)H

MN 9ema de pompare =/uvA NM

clrscr0)H

start/shirI4JH

i/1H

do5

if 0shirIiJ//start)5

cont;;H

cout Kv/KH

for 0E/4HEiHE;;)

cout cuvintIEJH

cout KLnA/KH

for 0E/iHEFHE;;)

cout cuvintIEJH

i/F1H

i;;H

Ahile 0iF)H

if 0cont//4)5

start/shirI1JH

i/1H

do5

if 0shirIiJ//start)5

cont;;H

7/25/2019 LFPC2OM

14/15

cout Ku/K shirI4JH

cout Kv/KH

for 0E/1HEiHE;;)

cout cuvintIEJHcout KLnA/KH

for 0E/iHEFHE;;)

cout cuvintIEJH

i;;H

Ahile 0iF)H

getch0)H

Rezultatele obtinute:

7/25/2019 LFPC2OM

15/15

lfpc2om

Documents