Московский государственный университет 4 страница

Затем рассматриваем каждый переход среди состояний. Допустим, хотим проверить переход в с входом a и выходом o, когда автомат находится в состоянии . Сначала нужно перевести автомат из в , подать входной символ a, получить o, и проверить конечное состояние . Мы не можем просто использовать , т.к. ошибки могут изменить конечное состояние. Вместо этого, мы используем последовательность

. Сначала автомат переходит в , реакция которого на уже известна из (1). . переводит автомат в состояние . Затем проверяем правильность перехода входным сигналом a, затем проверяем конечное состояние через . Таким образом, следующая последовательность проверяет корректность перехода в

. (2)

После этой последовательность автомат будет в состоянии . Повторяем этот процесс для каждого перехода и в итоге получим проверяющую последовательность.

Пример 4. Простой безусловный диагностический для автомата на рис.1 =ab и соответствующие выходы для состояний , и : 01, 11 и 00, соответственно. Переводящая последовательность, например для и : . Последовательность из (1) для проверки состояний есть abababab. Затем следующая последовательность babbab проверяет переход : b переводит автомат в , если мы получим 01, значит ab перевело автомат в , наконец, bab переводит в через b и проверяет конечное состояние. Другие переходы проверяются так же.

Мы можем использовать простые условные диагностические эксперименты для постройки тестовой последовательности. Для каждого состояния , мы рассматриваем дерево решений и берем входную последовательность , идущую из корня до листа (см. часть III-C). Множества ={ } образуют разделяющее семейство. Для примера, на рис.10 изображен простой условный диагностический эксперимент автомата на рис.1. Имеем, =ab, =a и =ab. Чтобы построить тестовую последовательность, в (1) и (2) мы заменяем на каждый , проверяющий состояние . Из (1) и (2) получим следующее:

, где .

.

Простой условный диагностический эксперимент O( ), а путь по всем вершинам имеет длину не больше n, тогда последовательность в (1) имеет длину O( ). Каждый тест из (2) имеет длину O( ), тогда для pn переходов требуется время O( ). Получаем тестовую последовательность длины O( ). Вначале построение простого условного диагностического эксперимента занимает время O( ), и время O(pn) для построения пути в остовном дереве (с помощью поиска в ширину), что в итоге требует O( ).

Как говорилось ранее, простые диагностические эксперименты схожи с ненадежным статусным сообщением, если представим = – эта последовательность переводит автомат из в и выдает статусное сообщение для . { } образуют разделяющее семейство. Тестовая последовательность может быть получена способом аналогичным ненадежным статусным сообщениям через эйлеров путь: для первого посещения состояния применяем дважды, в остальных случаях по одному, где каждый переход в проверяется через . Получим тестовую последовательность, имеющую длину O( ).

5. Вывод.

Мы рассмотрели алгоритмы решения 4-х фундаментальных проблем тестирования:

Проблема I (установочная/синхронизирующая последовательность): Определить финальное состояние автомата после теста.

Проблема II (идентификация состояния): Найти неизвестно начальное состояние.

Проблема III (верификация состояния): Автомат должен быть в определенном начальном состоянии, проверить, что это так.

Проблема IV (тест на соответствие): Проверить автомат B на корректную реализацию автомата-эталона A.

Были реализован алгоритм построения простого условного диагностического эксперимента для решения проблемы II, наряду с построением дерева условного эксперимента, на котором базируется алгоритм. Проверена его работоспособность.

6. Список литературы

[1] Lee and Yannakakis: Principles and methods of testing finite state machines-a suvrey - Proceedings of The IEEE, Vol. 84, No. 8, August 1996, pp. 1090-1123

[2] И.К. Рысцов. Доказательство достижимой оценки длины условного диагностического эксперимента для конечного автомата // Кибернетика, 1977,3,20-22.

[3] В.Б. Кудрявцев, С.В. Алёшин, А.С. Подколзин. Введение в теорию автоматов. Изд-во «Наука», М., 1985, 320 с.

[4] М.Н. Соколовский. О диагностических экспериментах с автоматами // Кибернетика, 1971, 6,44-49.

[5] М.П. Кудрявцев, И.С. Грунский, В.Ф. Козловский, «Анализ поведения автоматов», Дискрет. матем., 21:1 (2009), 3-35.

[6] М.П. Василевский. О распознавании неисправностей автомата // Кибернетика.-1973. №4.-С. 93-108.

7.Приложение.

#include <stdio.h>

#include <stdlib.h>

int E(int*,int*,int);

void F(int l,int*,int*,int*,int*,int);

void G(int*,int*,int*,int);

int in(int*,int*,int);

void reG(int*,int*,int*,int);

void concut(int*,int,int*,int,int*);

void resp(int*,int*,int*,int);

void upresp(int*,int*,int);

struct vortex{

struct vortex *C1;

struct vortex *C2;

int *s;

int str[10];

int b;

int l;

int leaf;

};

void find(int*,struct vortex*,struct vortex*,int);

int ff(struct vortex,int);

void tree(struct vortex*,struct vortex*,struct vortex*,int*,int*,int*,int*,int*,int*,int*,int*,int*,int);

void sept(int*,int*,int*,int);

void printtree(struct vortex,int);

int appl(struct vortex*,struct vortex*,int*,int*,int);

void norm(struct vortex*,int*,int);

int main(void)

{

int *phi0,*phi1,*psi0,*psi1,*tau,*mu,*nu,*nulik,q,i,n,bl;

struct vortex V,tmp,NU,*fi;

printf("SKOLKO SOSTOYANIY???\n");

scanf("%d",&n);

phi0=(int*)malloc(n*sizeof(int));

tau=(int*)malloc(n*sizeof(int));

mu=(int*)malloc(n*sizeof(int));

nu=(int*)malloc(n*sizeof(int));

nulik=(int*)malloc(n*sizeof(int));

phi1=(int*)malloc(n*sizeof(int));

psi0=(int*)malloc(n*sizeof(int));

psi1=(int*)malloc(n*sizeof(int));

printf("VVEDI FUNKCIYU PEREHODOV\n");

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

{

printf("SOSTOYANIE %d\nPO 0 ",i);

scanf("%d",&phi0[i]);

printf("PO 1 ");

scanf("%d",&phi1[i]);

nulik[i]=0;

}

printf("VVEDI FUNKCIYU VIHODOV\n");

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

{

printf("SOSTOYANIE %d\nPO 0 ",i);

scanf("%d",&psi0[i]);

printf("PO 1 ");

scanf("%d",&psi1[i]);

}

V.s=(int*)malloc(n*sizeof(int));

fi=(struct vortex*)malloc(sizeof(struct vortex));

(*fi).s=(int*)malloc(n*sizeof(int));

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

{

V.s[i]=1;

}

V.leaf=1;

V.l=0;

q=1;

while(q==1)

{

q=0;

tree(&V,fi,&V,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,&q,n);

}

printtree(V,n);

bl=0;

norm(&V,&bl,n);

if(bl!=0)

{

printf("-----------Impossible to answer---------------\n");

return 0;

}

printf("APPLY?\n");

q=appl(&V,fi,phi0,phi1,n);

printf("-------%d-------\n",q);

return 0;

}

int E(int *s,int *phi,int n)

{

int i,*r;

r=(int*)malloc(n*sizeof(int));

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

{

r[i]=0;

}

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

{

if(s[i]==1)

{

if(r[phi[i]]==1)

return 0;

else

r[phi[i]]=1;

}

}

return 1;

}

void F(int l,int* s,int* phi,int *psi,int *r,int n)

{

int i;

for(i=0;i<n;i++) r[i]=0;

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

{

if((s[i]==1)&&(psi[i]==l))

r[i]=1;

}

}

void G(int *s,int *phi,int *r,int n)

{

int i;

for(i=0;i<n;i++) r[i]=0;

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

{

if(s[i]==1) r[phi[i]]=1;

}

}

int in(int *a,int *b, int n)

{

int i;

for(i=0;i<n;i++) if(a[i]>b[i]) return 0;

return 1;

}

int ff(struct vortex V,int n)

{

int p,i;

p=0;

if(V.C1==NULL)

{

p--;

for(i=0;i<n;i++) p+=V.s[i];

}

else p+=ff(*V.C1,n);

if(V.C2==NULL)

{

p--;

for(i=0;i<n;i++) p+=V.s[i];

}

else p+=ff(*V.C1,n);

return p;

}

void find(int* s,struct vortex* V,struct vortex* y,int n)

{

int i;

if((*V).leaf!=1)

{

if((in(s,(*((*V).C1)).s,n)==1))

{

(*y).leaf=(*((*V).C1)).leaf;

for(i=0;i<n;i++) (*y).s[i]=(*((*V).C1)).s[i];

(*y).C1=(*((*V).C1)).C1;

(*y).C2=(*((*V).C1)).C2;

(*y).l=(*((*V).C1)).l;

(*y).b=(*((*V).C1)).b;

for(i=0;i<(*((*V).C1)).l;i++) (*y).str[i]=(*((*V).C1)).str[i];

find(s,(*V).C1,y,n);

}

if((in(s,(*((*V).C2)).s,n)==1))

{

(*y).leaf=(*((*V).C2)).leaf;

for(i=0;i<n;i++) (*y).s[i]=(*((*V).C2)).s[i];

(*y).C1=(*((*V).C2)).C1;

(*y).C2=(*((*V).C2)).C2;

(*y).l=(*((*V).C2)).l;

(*y).b=(*((*V).C2)).b;

for(i=0;i<(*((*V).C2)).l;i++) (*y).str[i]=(*((*V).C2)).str[i];

find(s,(*V).C2,y,n);

}

}

}

void sept(int* a,int* b,int* r,int n)

{

int i;

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

{

r[i]=a[i]*b[i];

}

}

void tree(struct vortex* V,struct vortex* fi,struct vortex* NU, int *phi0, int *phi1, int *psi0, int *psi1,int* tau,int* mu,int* nu,int* nulik,int* q,int n)

{

int i,u;

u=0;

for(i=0;i<n;i++) u+=(*V).s[i];

if(u==1) return;

if((*V).leaf==1)

{

if(E((*V).s,phi0,n)==1)

{

F(1,(*V).s,phi0,psi0,tau,n);

if(in(tau,nulik,n)==0)

{

F(0,(*V).s,phi0,psi0,mu,n);

if(in(mu,nulik,n)==0)

{

*q=1;

(*V).C1=(struct vortex*)malloc(sizeof(struct vortex));

(*V).C2=(struct vortex*)malloc(sizeof(struct vortex));

(*((*V).C1)).s=(int*)malloc(n*sizeof(int));

(*((*V).C2)).s=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++) {(*((*V).C1)).s[i]=tau[i];(*((*V).C2)).s[i]=mu[i];}

(*((*V).C1)).leaf=1;

(*((*V).C2)).leaf=1;

(*((*V).C1)).b=1;

(*((*V).C2)).b=0;

(*V).leaf=0;

(*V).str[0]=0;

(*V).l=1;

tree((*V).C1,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

tree((*V).C2,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

return;

}

}

G((*V).s,phi0,tau,n);

(*fi).leaf=(*NU).leaf;

for(i=0;i<n;i++) (*fi).s[i]=(*NU).s[i];

(*fi).C1=(*NU).C1;

(*fi).C2=(*NU).C2;

(*fi).l=(*NU).l;

for(i=0;i<(*fi).l;i++) (*fi).str[i]=(*NU).str[i];

(*fi).b=(*NU).b;

find(tau,NU,fi,n);

if((*fi).leaf!=1)

{

*q=1;

(*V).leaf=0;

(*V).l=1+(*fi).l;

(*V).str[0]=0;

for(i=1;i<(*fi).l+1;i++) (*V).str[i]=(*fi).str[i-1];

sept(tau,(*((*fi).C1)).s,nu,n);

sept(tau,(*((*fi).C2)).s,mu,n);

(*V).C1=(struct vortex*)malloc(sizeof(struct vortex));

(*V).C2=(struct vortex*)malloc(sizeof(struct vortex));

(*((*V).C1)).s=(int*)malloc(n*sizeof(int));

(*((*V).C2)).s=(int*)malloc(n*sizeof(int));

reG(nu,phi0,tau,n);

sept(tau,(*V).s,nu,n);

for(i=0;i<n;i++) (*((*V).C1)).s[i]=nu[i];

reG(mu,phi0,tau,n);

sept(tau,(*V).s,mu,n);

for(i=0;i<n;i++) (*((*V).C2)).s[i]=mu[i];

(*((*V).C1)).leaf=1; (*((*V).C2)).leaf=1; (*((*V).C1)).b=(*((*fi).C1)).b; (*((*V).C2)).b=(*((*fi).C2)).b;

tree((*V).C1,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

tree((*V).C2,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

return;

}

}

if(E((*V).s,phi1,n)==1)

{

F(1,(*V).s,phi1,psi1,tau,n);

if(in(tau,nulik,n)==0)

{

F(0,(*V).s,phi1,psi1,mu,n);

if(in(mu,nulik,n)==0)

{

*q=1;

(*V).C1=(struct vortex*)malloc(sizeof(struct vortex));

(*V).C1=(struct vortex*)malloc(sizeof(struct vortex));

(*V).C2=(struct vortex*)malloc(sizeof(struct vortex));

(*((*V).C1)).s=(int*)malloc(n*sizeof(int));

(*((*V).C2)).s=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++) {(*((*V).C1)).s[i]=tau[i];(*((*V).C2)).s[i]=mu[i];}

(*((*V).C1)).leaf=1;

(*((*V).C2)).leaf=1;

(*V).leaf=0;

(*V).str[0]=1;

(*V).l=1;

(*((*V).C1)).b=1;

(*((*V).C2)).b=0;

tree((*V).C1,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

tree((*V).C2,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

return;

}

}

G((*V).s,phi1,tau,n);

(*fi).leaf=(*NU).leaf;

for(i=0;i<n;i++) (*fi).s[i]=(*NU).s[i];

(*fi).C1=(*NU).C1;

(*fi).C2=(*NU).C2;

(*fi).l=(*NU).l;

for(i=0;i<(*fi).l;i++) (*fi).str[i]=(*NU).str[i];

(*fi).b=(*NU).b;

find(tau,NU,fi,n);

if((*fi).leaf!=1)

{

*q=1;

(*V).leaf=0;

(*V).l=1+(*fi).l;

(*V).str[0]=1;

for(i=1;i<(*fi).l+1;i++) (*V).str[i]=(*fi).str[i-1];

sept(tau,(*((*fi).C1)).s,nu,n);

sept(tau,(*((*fi).C2)).s,mu,n);

(*V).C1=(struct vortex*)malloc(sizeof(struct vortex));

(*V).C2=(struct vortex*)malloc(sizeof(struct vortex));

(*((*V).C1)).s=(int*)malloc(n*sizeof(int));

(*((*V).C2)).s=(int*)malloc(n*sizeof(int));

reG(nu,phi1,tau,n);

sept(tau,(*V).s,nu,n);

for(i=0;i<n;i++) (*((*V).C1)).s[i]=nu[i];

reG(mu,phi1,tau,n);

sept(tau,(*V).s,mu,n);

for(i=0;i<n;i++) (*((*V).C2)).s[i]=mu[i];

(*((*V).C1)).leaf=1; (*((*V).C2)).leaf=1; (*((*V).C1)).b=(*((*fi).C1)).b; (*((*V).C2)).b=(*((*fi).C2)).b;

tree((*V).C1,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

tree((*V).C2,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

return;

}

}

}

else

{

tree((*V).C1,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

tree((*V).C2,fi,NU,phi0,phi1,psi0,psi1,tau,mu,nu,nulik,q,n);

return;

}

return;

//else if(E((*V).s,phi1,n)==1)

}

void printtree(struct vortex V,int n)

{

int i;

for(i=0;i<n;i++) printf("%d ",V.s[i]);

printf("\n");

for(i=0;i<V.l;i++) printf("%d",V.str[i]);

printf("\n");

printf("%d",V.b);

printf("\nleaf=%d\n",V.leaf);

if (V.leaf!=1)

{

printtree(*(V.C1),n);

printtree(*(V.C2),n);

}

}

void reG(int *s,int *phi,int *r,int n)

{

int i;

for(i=0;i<n;i++) r[i]=0;

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

{

if(s[phi[i]]==1) r[i]=1;

}

}

void concut(int* a,int n,int* b,int m,int* c)

{

int i;

for(i=0;i<n;i++) c[i]=a[i];

for(i=n;i<n+m;i++) c[i]=b[i-n];

}

int appl(struct vortex *V,struct vortex *fi,int* phi0,int* phi1,int n)

{

int i,j,b,q,*C,*I,*tau,*tr;

C=(int*)malloc(n*sizeof(int));

I=(int*)malloc(n*sizeof(int));

tau=(int*)malloc(n*sizeof(int));

tr=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++) {C[i]=1; I[i]=1; tau[i]=0; tr[i]=i;}

q=n;

while(q!=1)

{

(*fi).leaf=(*V).leaf;

for(i=0;i<n;i++) (*fi).s[i]=(*V).s[i];

(*fi).C1=(*V).C1;

(*fi).C2=(*V).C2;

(*fi).l=(*V).l;

for(i=0;i<(*fi).l;i++) (*fi).str[i]=(*V).str[i];

(*fi).b=(*V).b;

find(C,V,fi,n);

printf("apply ");

for(i=0;i<(*fi).l;i++) printf("%d",(*fi).str[i]);

printf("\n enter the last output\n");

scanf("%d",&b);

if((*((*fi).C1)).b==b)

{

sept((*((*fi).C1)).s,C,tau,n);

for(i=0;i<n;i++) C[i]=tau[i];

resp(tau,tr,I,n);

for(i=0;i<(*fi).l;i++)

{

if((*fi).str[i]==0) {upresp(tr,phi0,n); G(C,phi0,tau,n); for(j=0;j<n;j++) {C[j]=tau[j];}}

else {upresp(tr,phi1,n); G(C,phi1,tau,n); for(j=0;j<n;j++) {C[j]=tau[j];}}

}

}

else

{

sept((*((*fi).C2)).s,C,tau,n);

for(i=0;i<n;i++) C[i]=tau[i];

resp(tau,tr,I,n);

for(i=0;i<(*fi).l;i++)

{

if((*fi).str[i]==0) {upresp(tr,phi0,n); G(C,phi0,tau,n); for(j=0;j<n;j++) {C[j]=tau[j];}}

else {upresp(tr,phi1,n); G(C,phi1,tau,n); for(j=0;j<n;j++) {C[j]=tau[j];}}

}

}

q=0;

for(i=0;i<n;i++) {q+=I[i];}

}

for(i=0;i<n;i++) if(I[i]==1) return i;

return 666;

}

void resp(int* tau, int* tr, int* I, int n)

{

int i,j;

for(i=0;i<n;i++) I[i]=0;

for(i=0;i<n;i++) if(tau[i]==1) for(j=0;j<n;j++) if(tr[j]==i) I[j]=1;

}

void upresp(int* tr, int* phi, int n)

{

int i, *t;

t=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++) t[i]=phi[tr[i]];

for(i=0;i<n;i++) tr[i]=t[i];

free(t);

}

void norm(struct vortex* V,int* bl, int n)

{

int i;

if((*V).leaf==1)

{

*bl=*bl-1;

for(i=0;i<n;i++) *bl=*bl+(*V).s[i];

}

else

{

norm((*V).C1,bl,n);

norm((*V).C2,bl,n);

}

}

Дата добавления: 2015-08-29