DFA не принимает строки
Моя программа должна реализовывать dfa для двоичной строки... dfa - это машина, которая может находиться только в одном состоянии за раз (когда вы вводите строку, машина должна использовать ее и на последнем шаге она должна достичь конечное состояние. если так, мы говорим, что строка принята машиной) ... эта машина работает следующим образом:
Сначала программа спрашивает количество состояний, если вы рассматриваете мою картинку, вы видите, что она имеет 3 состояния (q0,q1,q2), поэтому мы вводим 3. Затем она спрашивает о количестве входов. мои входы 0,1, поэтому я ввожу 2... затем он просит ввести входы, мы вводим 0, а затем 1! затем запрашивается число конечных состояний, конечное состояние здесь только q1... поэтому мы входим в него... затем вы видите это: (q0,0) = q это означает, что q0 переходит в какое состояние с 0... например, здесь q0 переходит к q0 с 0... другие такие. заполнив эту часть, мы вводим строку и она говорит, если строка действительна или нет
вот код:
#include<stdio.h>
#include<conio.h>
int ninputs;
int check(char,int ); //function declaration
int dfa[10][10];
char c[10], string[10];
int main()
{
int nstates, nfinals;
int f[10];
int i,j,s=0,final=0;
printf("enter the number of states that your dfa consist of \n");
scanf("%d",&nstates); // 3
printf("enter the number of input symbol that dfa have \n");
scanf("%d",&ninputs); // 2
printf("\nenter input symbols\t");
for(i=0; i<ninputs; i++)
{
printf("\n\n %d input\t", i+1);
printf("%c",c[i]=getch()); // 01
}
printf("\n\nenter number of final states\t");
scanf("%d",&nfinals); // 1
for(i=0;i<nfinals;i++)
{
printf("\n\nFinal state %d : q",i+1);
scanf("%d",&f[i]); // 1
}
printf("-----------------------------------------------------------------------");
printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");
for(i=0; i<ninputs; i++)
{
for(j=0; j<nstates; j++)
{
printf("\n(q%d , %c ) = q",j,c[i]);
scanf("%d",&dfa[i][j]);
// q(0,0)=0
// q(1,0)=0
// q(2,0)=2
// q(0,1)=1
// q(1,1)=2
// q(2,1)=1
}
}
do
{
i=0;
printf("\n\nEnter Input String.. ");
scanf("%s",string); // 01
while(string[i]!='\0')
{
if((s=check(string[i++],s))<0)
break;
for(i=0 ;i<nfinals ;i++)
{
if(f[i] ==s )
final=1;
if(final==1)
printf("\n valid string");
else
printf("invalid string");
getch();
printf("\nDo you want to continue.? \n(y/n) ");
}
}
}
while(getch()=='y');
getch();
}
int check(char b,int d)
{
int j;
for(j=0; j<ninputs; j++)
if(b==c[j])
return(dfa[d][j]);
return -1;
}
проблема в том, что когда я ввожу свою строку, программа говорит, что она недействительна, однако она должна быть принята машиной... например, рассмотрите машину на фотографии и проверьте эту строку на ней: 01
так что не так с кодом?
4 ответа
Оптимизированный код C для приема строк с использованием DFA
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
int a,b,i,j,k,state,ch;
char s[10][10],*st,v[10],ss[10];
printf("Enter the number of state:\n");
scanf("%d",&a);
printf("Enter State :\n");
for(i=0;i<a;i++)
{
fflush(stdin);
scanf("%c",&ss[i]);
}
printf("Enter th no. of var..:\n");
scanf("%d",&b);
printf("Enter variable :\n");
for(i=0;i<b;i++)
{
fflush(stdin);
scanf("%c",&v[i]);
}
printf("Enter table:\n");
for(i=0;i<a;i++)
{
for(j=0;j<b;j++)
{
fflush(stdin);
scanf("%c",&s[i][j]);
}
}
printf("Enter string :\n");
fflush(stdin);
gets(st);
i=0;
state=0;
while(st[i]!='\0')
{
for(j=0;j<b;j++)
{
if(st[i]==v[j])
{
if(s[state][j]=='-')
{
goto check;
}
else
{
for(k=0;k<a;k++)
{
if(s[state][j]==ss[k])
{
printf("State:%c\n",s[state][j]);
state=k;
goto o;
}
}
}
o:
}
}
i++;
}
check:
ch=1;
for(i=0;i<b;i++)
{
if(s[state][i]!='-')
{
ch=0;
}
}
if(ch==1)
{
printf("String is matching..");
}
else
{
printf("String is not matching..");
}
getch();
return 0;
}
Просто поставьте пробел перед%c . И отредактируйте несколько строк кода. Этот код успешно выполнен в версии Code::Blocks 13.12. Как это C++ компилятор сохранить файл с расширением.cpp. И нажмите на "Выходное изображение" . Вы увидите, как вводить и выводить данные с консоли
<-------- Вот отредактированный код && Он будет работать нормально ---> #
#include<stdio.h>
#include<cstdio>
#include<iostream>
int ninputs,bb;
int check(char,int ); //function declaration
int dfa[10][10];
char c[10], string[10],b;
int main()
{
int nstates, nfinals;
int f[10];
int i,j,s=0,final=0;
printf("enter the number of states that your dfa consist of \n");
scanf("%d",&nstates);
printf("enter the number of input symbol that dfa have \n");
scanf("%d",&ninputs);
printf("\nenter input symbols");
for(i=0; i<ninputs; )
{
bb =i;
printf("\n %d input",bb+1);
// printf(" %c",c[i]=getchar());
scanf(" %c" , &c[i]); //just put an space before %c
i++;
}
printf("\n\nenter number of final states\t");
scanf("%d",&nfinals);
for(i=0;i<nfinals;i++)
{
printf("\n\nFinal state %d : q",i+1);
scanf("%d",&f[i]);
}
printf("-----------------------------------------------------------------------");
printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");
for(i=0; i<ninputs; i++)
{
for(j=0; j<nstates; j++)
{
printf("\n(q%d , %c ) = q",j,c[i]);
scanf("%d",&dfa[i][j]);
}
}
do
{
i=0;
printf("\n\nEnter Input String.. ");
scanf("%s",string);
while(string[i]!='\0')
if((s=check(string[i++],s))<0)
break;
for(i=0 ;i<nfinals ;i++)
if(f[i] ==s )
final=1;
if(final==1)
printf("\n valid string");
else
printf("invalid string");
printf("\nDo you want to continue.? \n(y/n) ");
}
while(b =='y');
scanf(" %c", &b); // chnge here
}
int check(char b,int d)
{
int j;
for(j=0; j<ninputs; j++)
if(b==c[j])
return(dfa[d][j]);
return -1;
}
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
main()
{
int state,symbol;
char str[30];
cout<<"Enter the string which you want to check :: "<<endl;
fgets(str,sizeof(str),stdin);
cout<<"Enter the Number of state :: ";cin>>state;
cout<<"Enter the Number of input symbol :: ";cin>>symbol;
cout<<"Enter the states : "<<endl;
char st[state];
for(int i=0;i<state;i++)
{
cout<<"state : "<<i<<" : ";cin>>st[i];
}
cout<<"Enter the input symbol : "<<endl;
char sy[symbol];
for(int i=0;i<symbol;i++)
{
cout<<"symbol : "<<i<<" : ";cin>>sy[i];
}
char table[state][symbol];
cout<<"------Enter next move or state------ if no relation put -"<<endl;
for(int i=0;i<state;i++)
{
for(int j=0;j<symbol;j++)
{
cout<<"("<<st[i]<<", "<<sy[j]<<") = ";cin>>table[i][j];
}
}
char ststate,fnstate;
cout<<"Start state :: ";cin>>ststate;
cout<<"Final state :: ";cin>>fnstate;
cout<<"----------------------------------"<<endl;
int str_len=strlen(str);
int p,q;
int flag=1;
int j=0;
for(j=0;j<str_len-1;j++)
{
cout<<"input state"<<endl;
for(int i=0;i<state;i++)
{
if(st[i]==ststate)
{
p=i;
cout<<p<<endl;
break;
}
else
{
p=-1;
}
}
cout<<"input string"<<endl;
for(int i=0;i<state;i++)
{
if(sy[i]==str[j])
{
q=i;
// cout<<q<<endl;
break;
}
else
{
q=-1;
}
}
if(p!=-1 && q!=-1)
{
cout<<"table output :: "<<table[p][q]<<endl;
ststate=table[p][q];
}
}
cout<<endl;
cout<<"----------------------------------------------------------------------------------";
if((table[p][q]==fnstate) && (j==str_len-1))
{
cout<<"String is recognized"<<endl;
flag=0;
}
if(flag!=0)
{
cout<<"String is not recognized.";
}
cout<<endl;
return 0;
}
// i Can't be able to put image just because my reputation is only 1 but i am dam sure this program work successfully as not much as my reputation on stack overflow.
Эта часть кода:
while(string[i]!='\0')
{
if((s=check(string[i++],s))<0)
break;
for(i=0 ;i<nfinals ;i++)
{
использует и изменяет i в обоих циклах. Вам нужно использовать что-то еще в одном из них.