UNIVERSITATEA TEHNICĂ A MOLDOVEI

CATEDRA : TEHNOLOGII INFORMAŢIONALE

DAREA DE SEAMĂ

Lucrarea de laborator № 2 la disciplina “Limbaje

formale şi automate”
Tema : „Automate finite”

(Varianta nr.1)

ELABORAT:
Studentul gr. TI-113 Onica Dinu

VERIFICAT:
Profesorul: Duca L.

Chişinău 2012

1
1. Reprezentaţi automatul sub formă de graf.
2. Construiţi gramatica regulată echivalentă cu automatul dat.
3. Este sau nu automatul dat determinist? De ce?
4. Dacă automatul este nedeterminist, construiţi automatul finit determinist echivalent
Reprezentaţi AFD în formă de graf.
5. Inventaţi un şir peste vocabularul  care nu va fi acceptat de către automat. Arătaţi acest lucru
scriind secvenţa (secvenţele) de configuraţii respectivă.
6. Pentru automatul finit AF=(Q, , , q0, F) construiţi 5 şiruri acceptate de automat. Lungimea
şirurilor să nu fie mai mică decât n+2, unde n este numărul de stări din Q.
7. Pentru fiecare şir x scrieţi secvenţa de configuraţii pentru acceptarea şirului, adică (q0, x) — (qi1, x1)
— (qi2, x2) — … — (qf, ), unde qf  F.
8. Petru toate cele 5 şiruri obţinute construiţi aplicând lema de pompare descompunerea x=uvw.

AF=(Q, , , q0, F),

Q = {q0, q1, q2 , q3},
 = {a, c, b}, F = {q2}.
 (q0, a ) = q0,
 (q0, a ) = q1 ,
 (q1, c ) = q1,
 (q1, b ) = q2,
 (q2, b ) = q3,
 (q3, a ) = q1 .

1) Reprezentăm automatul sub formă de graf:

a c

q0 a a q3
q1

b
b

q2

2) Construim gramatica regulată echivalentă cu automatul dat:

2
 G=( V N , V T , P , S )
1) VN = Q = {q0, q1, q2, q3}
2) VT = å={a, b, c,}
3) S=q0
4) Producţiile sunt definite astfel: P=δ

 (q0, a ) = q0, P={1.q0→aq0

 (q0, a ) = q1 , 2.q0→aq1
 (q1, c ) = q1, 3.q1→cq1
 (q1, b ) = q2, 4.q1→bq2
 (q2, b ) = q3, 5.q2→bq3
 (q3, a ) = q1 . 6.q3→aq1
7.q1→b}

3) Este sau nu automatul dat determinist? De ce?

Automatul dat este nedeterminist, deoarece din starea q0 prin a se poate trece în 2 stări diferite: q0 sau q1

4) Dacă automatul este nedeterminist, construiţi automatul finit determinist echivalent.

Reprezentaţi AFD în formă de graf.
AFD = ( Q',  ,', q0 , F' ),
 = {a, b, c, }

a b c
q0 q0q1
q0q1 q0q1 q2 q1
q2 q3
q1 q2 q1
q3 q1

q0 a q0q1 b q2

b c b

q3 a q1
c

3
5) Inventăm un şir peste vocabularul  care nu este acceptat de către automat. Arătăm acest lucru
scriind secvenţa (secvenţele) de configuraţii respectivă.
Cuvintul neacceptat de gramatica dată este

aacca

6) Lungimea şirurilor nu este mai mică decât n+2, unde n este numărul de stări din Q.
[Link]
[Link]
[Link]
[Link]
[Link]

7) Pentru fiecare şir x scriem secvenţa de configuraţii pentru acceptarea şirului:

(q0, x) — (qi1, x1) — (qi2, x2) — … — (qf, ), unde qf  F.
1.(q0,aabbab)|--(q0q1,abbab)|--(q0q1,bbab)|--(q2,bab)|--(q3,ab)|--(q1,b)|--(q2, );
2.(q0,acbbab)|--(q0q1,cbbab)|--(q1,bbab)|--(q2,bab)|--(q3,ab)|--(q1,b)|--(q2, );
3.(q0,accbbab)|--(q0q1,ccbbab)|--(q1,cbbab)|--(q1,bbab)|--(q2,bab)|--(q3,ab)|--(q1,b)|--(q2, );
4.(q0,acbbacb)|--(q0q1,cbbacb)(q1,bbacb)|--(q2,bacb)|--(q3,acb)|--(q1,cb)|--(q1,b)|--(q2, );
5.(q0,aabbacb)|--(q0q1,abbacb)|--(q0q1,bbacb)|--(q2,bacb)|--(q3,acb)|--(q1,cb)|--(q1,b)|--(q2, );

8) Petru toate cele 5 şiruri obţinute construim aplicând lema de pompare descompunerea z=uvw:
1. z=uvw
2. |z| ≥ n, n=card(Q), |v|≥1
3. |uv| ≤ n
4. uviw є L

1.
1.q0 a q0q1 a q0q1 b q2 b q3 a q1 b q2

u v w
u=a
v=a
w=bbab

2.
q0
a q0q1
c q1
b q2
b q3
a q1
b q2

u v w
u=ac
v=bba
w=b

3.
4
 q0 a q0q1 c q1 c q1 b q2 b q3 a q1 b q2

u v w
u=ac
v=c
w=bbab

4.
a c b b a c b
q0 q0q1 q1 q2 q3 q1 q1 q2

u v w

u=ac
v=bba
w=cb

5.
q0 a q0q1 a q0q1 b q2 b q3 a q1 c q1 b q2

u v w
u=a
v=a
w=bbacb

[Link] Programului:
5
#include<iostream>
#include<conio.h>
#include<string.h>
#include<windows.h>
#include<stdlib.h>
#define L (cout<<" -> ")

using namespace std;

string stare[2][30];
string alfabet[30],F,S;
int n=0,n1,lung=6;

int color(int culoare)

{
HANDLE h;
h=GetStdHandle(STD_OUTPUT_HANDLE);

};
//_______________________________________________
void gotoxy(int x, int y)
{
COORD coord;
coord.X = x;
coord.Y = y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
};
//_______________________________________________
int wherex()
{
HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_SCREEN_BUFFER_INFO csbi;
GetConsoleScreenBufferInfo(hStdOut, &csbi);
return [Link].X;
};

int wherey()
{
HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_SCREEN_BUFFER_INFO csbi;
GetConsoleScreenBufferInfo(hStdOut, &csbi);
return [Link].Y;
};
//_______________________________________________
void introducere()
6
{
char f=161;
string aux;
color(10);int y1=wherey()+1;
cout<<endl<<" Introduceti starile:"<<endl<<endl;
color(12);
int i=0,y=wherey(),x=wherex(),d=0;
do{
gotoxy(12,y+10);d=0;while(d++!=10)cout<<" ";
gotoxy(x,y);
cout<<" "<<i+1<<". ";
cout<<f<<"(";
color(10);y=wherey();x=wherex();
cin>>aux; stare[0][i]=aux; gotoxy(x,y);
cout<<stare[0][i];
cout<<", ";;y=wherey();x=wherex();
cin>>aux;alfabet[i].assign(aux,0,1);gotoxy(x,y);
cout<<alfabet[i];
cout<<")=";
cin>>stare[1][i++];y=wherey(),x=wherex(); n++;
gotoxy(12,y+10); cout<<"[ESC] - finisare; / [ENTER] - continua...";
}while(getch()!=27);
gotoxy(12,y+10);d=0;while(d++!=10)cout<<" ";
for(int afis=y1;afis<y;afis++){gotoxy(25,afis);cout<<(char)186;}
};
//*****************************************************************
void gramatica(){
int x=27,y=1,este=0,ns;
eticheta1:
gotoxy(27,y);cout<<"Introduceti starea initiala: ";x=wherex();
cin>>S;
for(int i=0;i<n;i++)if(S==stare[0][i]){este=1;break;};
gotoxy(x,y);
if(este){cout<<S<<"; "; gotoxy(27,y+2);for(int i=0;i<10;i++)cout<<" ";}
else{cout<<"...";gotoxy(27,y+2);
cout<<"Stare inexistenta, tastati din nou";goto eticheta1;}y++; este=0;
eticheta:
gotoxy(27,y);cout<<"Introduceti starea finala: ";cout<<"F={";x=wherex();
cin>>F;
for(int i=0;i<n;i++)if(F==stare[0][i]||F==stare[1][i]){este=1;break;};
gotoxy(x,y);
if(este){cout<<F<<"}; "; gotoxy(27,y+2);for(int i=0;i<10;i++)cout<<" ";}
else{cout<<"...};";gotoxy(27,y+2);
cout<<"Stare inexistenta, tastati din nou";goto eticheta;}
y+=2; x=27; gotoxy(x,y);
cout<<"Gramatica regulata:"; y++; x+=2;gotoxy(x,y);
7
 for(int i=0;i<n;i++)
{
gotoxy(x,y++);
cout<<i+1<<". "; color(10);
cout<<stare[0][i];L;
cout<<alfabet[i]; cout<<stare[1][i];
}
ns=n;
for(int i=0;i<n;i++)
{
if(stare[1][i]==F)
{
gotoxy(x,y++);
cout<<++ns<<". ";
cout<<stare[0][i];L;
cout<<alfabet[i];
}} y+=2;
for(int linie=5;linie<y;linie++){gotoxy(25,linie);cout<<(char)186;}
for(int afis=1;afis<60;afis++){gotoxy(afis,y);cout<<(char)205;}
gotoxy(25,y);cout<<(char)202;
gotoxy(20,y+2);
};
//**************************************************************
int detect()
{
int este=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(stare[0][i]==stare[0][j])
if(alfabet[i]==alfabet[j])
{este=1;return este;}
return 0;
};
//*************************************************************
void todetermin()
{ string det[50][30]; int nr=2;
det[0][1]=alfabet[0];
for(int i=1,j=0;i<n;i++)
{
for(j=1;j<nr;j++)if(alfabet[i]==det[0][j])break;
if(j==nr)det[0][nr++]=alfabet[i];
}
lung=nr+1;
det[1][0]=S;
int r=2,ii;

8
 for(int rind=1,i=2,j=1;rind<r;rind++)
{
for(int col=1;col<nr;col++)
{
for(int cauta=0;cauta<n;cauta++)
{
for(int c=0;c<det[rind][0].length()-1;c++)
{
if((det[rind][0].compare(c,stare[0][cauta].length(),stare[0]
[cauta])==0)&&(det[0][col]==alfabet[cauta]))
{
if(det[rind][col].compare(0,stare[1][cauta].length(),stare[1][cauta])!=0)
det[rind][col]+=stare[1][cauta];
}
}
}
if(det[rind][col].capacity())
{
for(ii=1;ii<r;ii++)
{
if(det[ii][0]==det[rind][col])break;
}
if(ii==r){r++;det[i++][0]=det[rind][col];}
}
}
}
cout<<" Automatul Finit DETERMINIST:"<<endl;
int x=wherex()+2, y=wherey()+1; gotoxy(x,y);
cout<<(char)201;
for(int i=0;i<nr-1;i++)
cout<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)20
5<<(char)205<<(char)203;
cout<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)20
5<<(char)205<<(char)187;
int a=wherey();
for(int i=0;i<r-1;i++)
{
gotoxy(x,++y);
for(int j=0;j<nr-1;j++)
{
cout<<(char)186<<" ";
} cout<<(char)186<<" "<<(char)186;
gotoxy(x,++y);cout<<(char)204;
for(int j=0;j<nr-1;j++)
9
 {
cout<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)20
5<<(char)205<<(char)206;
}
cout<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)20
5<<(char)205<<(char)185;
}
gotoxy(x,++y);
for(int j=0;j<nr-1;j++)
{
cout<<(char)186<<" ";
} cout<<(char)186<<" "<<(char)186;
gotoxy(x,++y);cout<<(char)200;
for(int i=0;i<nr-1;i+
+)cout<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)
205<<(char)205<<(char)202;
cout<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)205<<(char)20
5<<(char)205<<(char)188;
y=a+1;x++;
for(int i=0;i<r;i++)
{
gotoxy(x,y);
for(int j=0;j<nr;j++)
{
cout<<det[i][j];x+=9;gotoxy(x,y);
}
y+=2; x=3;
}

for(int i=1;i<n;i++)
{
stare[0][i]="";
stare[1][i]="";
alfabet[i]="";
};
int k=0;
for(int i=1;i<r;i++)
for(int j=1;j<nr;j++)
{
if(det[i][j].capacity())
{
stare[0][k]=det[i][0];
stare[1][k]=det[i][j];
alfabet[k++]=det[0][j];
};
10
 }
n=k;
x=10;y+=2;gotoxy(x,y);
};
//*************************************************************
void uvw(string a[2])
{
int i=0,j=0,k=0;
string b[100],sir=a[1];
for(i=0;i<a[1].length();i++)
{
b[i].assign(sir,0,[Link](","));
sir=[Link]([Link](",")+1);
}
j=i;for(i=0;i<j;i++)
if(b[i]=="X")b[i]=F;

cout<<endl;
for(i=0;i<a[0].length();i++)
{
for(j=a[0].length();j>=0;j--)
{
if(j==i)continue;
if(b[i]==b[j])
{
cout<<" u = ";
for(k=0;k<i;k++)
cout<<a[0].at(k);
cout<<endl<<" v = ";
for(k=i;k<j;k++)
cout<<a[0].at(k);
cout<<endl<<" w = ";
for(k=j;k<a[0].length();k++)
cout<<a[0].at(k);
cout<<endl<<endl;
return ;
}
}
}

}
//*************************************************************
void lema()
11
{
n1=n;
cout<<"Lema de pompare:"<<endl<<endl;
for(int i=0;i<n1;i++)
{
if(stare[1][i]==F)
{
stare[0][n1]=stare[0][i];
stare[1][n1]="X";
alfabet[n1++]=alfabet[i];
}
}
string cuv[2];
int l=0,a,m=0;
int lng=lung;
cout<<" Cuvintul: ";
et:
while(1)
{
l=rand()%n+0;
if(stare[0][l]==S)
{
cuv[0]=alfabet[l];
cuv[1]=stare[0][l]+",";
break;
}
};
cuv[1]+=stare[1][l]+",";
lung=rand()%10+lng;

for(int i=0;i<lung;)
{
a=rand()%n+0;
if(stare[1][l]==stare[0][a])
{ i++;
cuv[0]+=alfabet[a];
cuv[1]+=stare[1][a]+",";
l=a;
}
}
int v=1;
while(v)
{
a=rand()%n+0;
if(stare[1][l]==stare[0][a])
{
12
 for(int i=n;i<n1;i++)
{
if(stare[0][a]==stare[0][i])
{
cuv[0]+=alfabet[i];
cuv[1]+=stare[1][i];
v=0;
break;
}
}
if(v){
cuv[0]+=alfabet[a];
cuv[1]+=stare[1][a]+",";
l=a;
}
}
}
int x=wherex(),y=wherey();
cout<<cuv[0]<<endl<<endl;
cout<<" Configuratiile:"<<endl<<endl<<" ";
cout<<"(";color(10);cout<<S;color(12);cout<<",";color(14);cout<<"X";
cout<<") = (";
string aux,sir(cuv[1]);
for(int i=0;i<cuv[0].length();i++)
{

[Link](sir,0,[Link](","));
sir=[Link]([Link](",")+1);
cout<<aux;
cout<<",";
cout<<cuv[0].substr(i);color(12);cout<<") |"<<(char)196<<" (";
}
cout<<aux;
cout<<",";cout<<(char)242;cout<<");"<<endl;
uvw(cuv);
cout<<"_____________________________________________________"<<endl<<endl;
cout<<" [ESC] - Iesire; [Orice tasta] - cuvint nou...";
int x1=wherex(),y1=wherey();
char c;
while((c=getch())!=27)
{gotoxy(x,y);
while(y1+2>wherey())cout<<" ";
gotoxy(x,y);
goto et;
}

13
};
//*************************************************************
void determinare()
{
cout<<"Automatul dat este ";
if(!detect()){cout<<"DETERMINIST"<<endl<<endl;}
else{cout<<"NEDETERMINIST"<<endl<<endl;todetermin();}
lema();
};
//*************************************************************
main()
{
introducere();
gramatica();
determinare();
return 0;
}

[Link] afisarii:

14
15