Пожалуйста найдите ошибку в Конечном Автомате на С++

@Marad · Регистрация: 05.04.2013

Author24 — интернет-сервис помощи студентам

Помогите найти ошибку в Конечном Автомате на С++ для: а*b*с*(d|f)+n*h* .
Может даже и не верна введена таблица для исходного выражения.

C++

#include "stdafx.h"
#include "iostream"
#include "string.h"
using namespace std;
 
void main()
{
    int j;  
    int a[6][7]=
            {
             {2,3,4,0,0,0,0},
             {0,3,4,0,0,0,0},
             {0,0,4,5,5,0,0},
             {0,0,0,5,5,6,7},
             {0,0,0,0,0,6,7},
             {0,0,0,0,0,0,7}
            };
char s[50];
cin>>s;
int size=strlen(s);
int i=0;
int q=1;
while ((q!=0)&(i<size))
      {
         cout<<"q=="<< q << "\n";
         switch(s[i])
            {
                case 'a': j=0; break;
                case 'b': j=1; break;
                case 'c': j=2; break;
                case 'd': j=3; break;
                case 'f': j=4; break;
                case 'n': j=5; break;
                case 'h': j=6; break;
                default: q=0; break;
            }
    q=a[q-1][j];
    cout<<"q= "<< q << '\n';
    i++;
      };
 
if ((q==5)|(q==7)) cout<<" Yes\n";
else cout<<" No\n";
system("pause");
}

alsav22 · 06.04.2013, 00:30

Что код делать должен?

Добавлено через 8 минут
Что должно вводиться?

@Marad · 06.04.2013, 00:55 **[ТС]**

По идее, я должен вводить комбинацию из букв a,b,c,(d или f),n,h , где a* - значит что может быть хоть сколько элементов 'a' или не быть,также для и для b*,c*,n*,h*. А (d|f)+ это какой нибудь из двух элементов d или f ,
в котором может быть хоть сколько элементов, но обязательность должен быть один элемент. К примеру выражение abcdnh - верно, acfn-верно и даже просто d или f - верно.

alsav22 · 06.04.2013, 06:27

Просто 'а' верно? Одиночные символы из набора - верно?

@kamre · 06.04.2013, 07:05

Сообщение от Marad

Помогите найти ошибку в Конечном Автомате на С++ для: а*b*с*(d|f)+n*h* .
Может даже и не верна введена таблица для исходного выражения.

Если убрать из таблицы состояние 0, то получается примерно такая картинка. Как это связанно с выражением "а*b*с*(d|f)+n*h*" сложно понять... Вроде бы никак не связанна, т.е. автомат не соответствует этому выражению.

@kamre · 06.04.2013, 07:44

Вот вроде бы такой автомат должен быть:

@Marad · 06.04.2013, 12:41 **[ТС]**

kamre, Дело в том, что это еще нужно запрограммировать на С++ таблицой

Добавлено через 6 минут
alsav22, Просто 'а' не будет верен, так как есть 'd' и 'f' , над которым стоит знак плюс, означает что 'd' или 'f' должен быть обязательно, верно будет ad или af. Также ответом является просто элемент 'd' или 'f'.

@kamre · 06.04.2013, 13:22

Сообщение от Marad

kamre, Дело в том, что это еще нужно запрограммировать на С++ таблицой

Ну так подправьте свою таблицу исходя из картинки автомата. Это совсем не сложно: из состояния '1' при встрече буквы 'b' переход идет в состояние '2', значит на 1 строке (соотв. '1') во 2 столбце (соотв. 'b') стоит значение 2 (соотв. '2').

@Marad · 06.04.2013, 15:55 **[ТС]**

Извиняюсь, но до меня ваще не доходит, башка не шарит чета, можешь наброски хотя бы сделать

@kamre · 06.04.2013, 22:25

Набросок (переходы из состояния '1'):

C++

int a[7][7] = }
/*         a  b  c  d  f  n  h */
/* 0 */  { 0, 0, 0, 0, 0, 0, 0 },
/* 1 */  { 1, 2, 3, 4, 4, 0, 0 },
/* 2 */  { 0, 0, 0, 0, 0, 0, 0 },
/* 3 */  { 0, 0, 0, 0, 0, 0, 0 },
/* 4 */  { 0, 0, 0, 0, 0, 0, 0 },
/* 5 */  { 0, 0, 0, 0, 0, 0, 0 },
/* 6 */  { 0, 0, 0, 0, 0, 0, 0 },
};

Остальные переходы аналогично.

@Marad · 07.04.2013, 02:34 **[ТС]**

kamre, Спасибо, программа стала работать лучше но все же есть косяки.

C++

    int a[6][7] = 
{
/*         a  b  c  d  f  n  h */
/* 1 */  { 2, 3, 4, 5, 5, 0, 0 },
/* 2 */  { 0, 3, 4, 5, 5, 0, 0 },
/* 3 */  { 0, 0, 4, 5, 5, 0, 0 },
/* 4 */  { 0, 0, 0, 5, 5, 6, 7 },
/* 5 */  { 0, 0, 0, 0, 0, 6, 7 },
/* 6 */  { 0, 0, 0, 0, 0, 0, 7 },
};

Вот я вставил остальные состояния, убрал первую нулевую строку, элементы прибавил на 1, так как использую q=a[q-1][j] в программе.
А можно как нибудь тебе файл отправить чтоб ты подкорректировал программу.

Добавлено через 15 минут
Похоже ошибка в таблице. К примеру, когда я ввожу 'a' 'd' то пишет верно и переходит на 5 строчку, когда 'a' 'd' 'd' то неверно, переходит на ноль.

Добавлено через 54 минуты

C++

#include "stdafx.h"
#include "iostream"
#include "string.h"
using namespace std;
 
void main()
{
    int j;  
    int a[7][7] = 
{
/*         a  b  c  d  f  n  h */
/* 1 */  { 2, 3, 4, 0, 0, 0, 0 },
/* 2 */  { 2, 3, 4, 5, 5, 0, 0 },
/* 3 */  { 0, 3, 4, 5, 5, 0, 0 },
/* 4 */  { 0, 0, 4, 5, 5, 0, 0 },
/* 5 */  { 0, 0, 0, 5, 5, 6, 7 },
/* 6 */  { 0, 0, 0, 0, 0, 6, 7 },
/* 7 */  { 0, 0, 0, 0, 0, 0, 7 }
};
char s[50];
cin>>s;
int size=strlen(s);
int i=0;
int q=1;
while ((q!=0)&(i<size))
      {
         cout<<"q=="<< q << "\n";
         switch(s[i])
            {
                case 'a': j=0; break;
                case 'b': j=1; break;
                case 'c': j=2; break;
                case 'd': j=3; break;
                case 'f': j=4; break;
                case 'n': j=5; break;
                case 'h': j=6; break;
                default : q=0; break;
            }
    q=a[q-1][j];
    cout<<"q= "<< q << '\n';
    i++;
      };
 
if ((q==1)||(q==5)||(q==6)||(q==7)) cout<<" Yes\n";
else cout<<" No\n";
system("pause");
}

kamre, программа почти работает правильно, но есть одна ошибка, нужно чтоб было d и f были по отдельности как бы сказать, только d или f. Если же к примеру я ввожу acdddfn он должен вывести ошибку, а он говорит что это верно.

Добавлено через 13 секунд

C++

#include "stdafx.h"
#include "iostream"
#include "string.h"
using namespace std;
 
void main()
{
    int j;  
    int a[7][7] = 
{
/*         a  b  c  d  f  n  h */
/* 1 */  { 2, 3, 4, 0, 0, 0, 0 },
/* 2 */  { 2, 3, 4, 5, 5, 0, 0 },
/* 3 */  { 0, 3, 4, 5, 5, 0, 0 },
/* 4 */  { 0, 0, 4, 5, 5, 0, 0 },
/* 5 */  { 0, 0, 0, 5, 5, 6, 7 },
/* 6 */  { 0, 0, 0, 0, 0, 6, 7 },
/* 7 */  { 0, 0, 0, 0, 0, 0, 7 }
};
char s[50];
cin>>s;
int size=strlen(s);
int i=0;
int q=1;
while ((q!=0)&(i<size))
      {
         cout<<"q=="<< q << "\n";
         switch(s[i])
            {
                case 'a': j=0; break;
                case 'b': j=1; break;
                case 'c': j=2; break;
                case 'd': j=3; break;
                case 'f': j=4; break;
                case 'n': j=5; break;
                case 'h': j=6; break;
                default : q=0; break;
            }
    q=a[q-1][j];
    cout<<"q= "<< q << '\n';
    i++;
      };
 
if ((q==1)||(q==5)||(q==6)||(q==7)) cout<<" Yes\n";
else cout<<" No\n";
system("pause");
}

kamre, программа почти работает правильно, но есть одна ошибка, нужно чтоб было d и f были по отдельности как бы сказать, только d или f. Если же к примеру я ввожу acdddfn он должен вывести ошибку, а он говорит что это верно.

@kamre · 07.04.2013, 04:48

Сообщение от Marad

убрал первую нулевую строку, элементы прибавил на 1

Непонятно зачем прибавлял единицу.

Сообщение от Marad

Если же к примеру я ввожу acdddfn он должен вывести ошибку, а он говорит что это верно.

Почему должен вывести ошибку, если эта строка подходит под выражение а*b*с*(d|f)+n*h* ?
И автомат распознает ее корректно:

@Marad · 07.04.2013, 10:27 **[ТС]**

d|f означает, что должен быть только один из этих элементов, либо d, либо f. И если автомат видит их сразу двоих, то обязан видеть ошибку

@kamre · 07.04.2013, 12:21

Сообщение от Marad

d|f означает, что должен быть только один из этих элементов, либо d, либо f. И если автомат видит их сразу двоих, то обязан видеть ошибку

(d|f)+ допускает любое сочетание из d и f, откуда ошибка?

@Marad · 07.04.2013, 14:21 **[ТС]**

Ошибка в том, что должно быть только одна из этих букв d или f, так как символ ' | ' в выражении (d|f)+ означает или f или d. Если я введу выражение abcdfnh acdf acdf df , то все они будет не верны. Должно быть abcdnh или abcfnh, acf, acd, f , d . А где именно исправить это я не знаю. Нужно добавить в программе что если в выражении попадутся d и f, выдавала ошибку. Типо добавить

C++ (Qt)

1	if f & d =0

@kamre · 07.04.2013, 21:25

Сообщение от Marad

Ошибка в том, что должно быть только одна из этих букв d или f, так как символ ' | ' в выражении (d|f)+ означает или f или d.

А что означает + после выражения? Должно означать повтор выражения один раз или более. Поэтому d и f могут повторяться сколько угодно раз чередуясь в произвольном порядке.

@Marad · 07.04.2013, 22:32 **[ТС]**

+ означает, что элемент может повторяться хоть сколько раз, но обязательно должен быть один раз.
* означает, что элемент может повторяться хоть сколько раз, а может и не быть.
d|f означает, либо первый элемент, либо второй,но не могут быть вместе.
Поэтому и выражение a*b*c*(d|f)+n*h* одним из ответом является d или f.

@kamre · 08.04.2013, 07:45

Сообщение от Marad

+ означает, что элемент может повторяться хоть сколько раз, но обязательно должен быть один раз
...
d|f означает, либо первый элемент, либо второй,но не могут быть вместе

И вот эта конструкция "либо первый элемент, либо второй" после добавления к ней + может повторяться сколько угодно раз:
"либо d, либо f",
"либо d, либо f",
"либо d, либо f",
....
В итоге любая комбинация из d и f будет подходить, неужели это не очевидно?

alsav22 · 08.04.2013, 09:12

Сейчас проверил в Qt. Получается, что kamre прав.

Добавлено через 5 минут
Вот такая конструкция выдаст true:

C++ (Qt)

1
2
3

QRegExp reg("а*b*с*(d|f)n*h*");
QString str("df");
qDebug() << str.contains(reg);

Т.е., если в str стоит d, или f, то это соответствует регулярному выражению.
Или так:

C++ (Qt)

1
2
3

QRegExp reg("а*b*с*(d|f)n*h*");
QString str("fd");
qDebug() << str.contains(reg);

Добавлено через 5 минут
Или так:

C++ (Qt)

1
2
3

QRegExp reg("а*b*с*(d|f)n*h*");
QString str("dfdfdf");
qDebug() << str.contains(reg);

Хотя бы один есть - уже истина. Если нет ни d, ни f, тогда false.

Добавлено через 3 минуты
Отсюда уже и это истинно:

C++ (Qt)

1
2
3

QRegExp reg("а*b*с*(d|f)+n*h*");
QString str("ddfffdddffff");
qDebug() << str.contains(reg);

@Marad · 08.04.2013, 17:09 **[ТС]**

Все, спасибо вам ребята, програ работает отлично =)

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	07.04.2013, 21:25	16
	Сообщение от Marad Ошибка в том, что должно быть только одна из этих букв d или f, так как символ ' \| ' в выражении (d\|f)+ означает или f или d. А что означает + после выражения? Должно означать повтор выражения один раз или более. Поэтому d и f могут повторяться сколько угодно раз чередуясь в произвольном порядке. 1

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	08.04.2013, 07:45	18
	Сообщение от Marad + означает, что элемент может повторяться хоть сколько раз, но обязательно должен быть один раз ... d\|f означает, либо первый элемент, либо второй,но не могут быть вместе И вот эта конструкция "либо первый элемент, либо второй" после добавления к ней + может повторяться сколько угодно раз: "либо d, либо f", "либо d, либо f", "либо d, либо f", .... В итоге любая комбинация из d и f будет подходить, неужели это не очевидно? 1

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	06.04.2013, 00:30	2
	Что код делать должен? Добавлено через 8 минут Что должно вводиться? 1

@Marad 0 / 0 / 0 Регистрация: 05.04.2013 Сообщений: 15
	06.04.2013, 00:55 [ТС]	3
	По идее, я должен вводить комбинацию из букв a,b,c,(d или f),n,h , где a* - значит что может быть хоть сколько элементов 'a' или не быть,также для и для b,c,n,h. А (d\|f)+ это какой нибудь из двух элементов d или f , в котором может быть хоть сколько элементов, но обязательность должен быть один элемент. К примеру выражение abcdnh - верно, acfn-верно и даже просто d или f - верно. 0

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	06.04.2013, 06:27	4
	Просто 'а' верно? Одиночные символы из набора - верно? 1

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	06.04.2013, 07:05	5
	Сообщение от Marad Помогите найти ошибку в Конечном Автомате на С++ для: аbс(d\|f)+nh* . Может даже и не верна введена таблица для исходного выражения. Если убрать из таблицы состояние 0, то получается примерно такая картинка. Как это связанно с выражением "аbс(d\|f)+nh*" сложно понять... Вроде бы никак не связанна, т.е. автомат не соответствует этому выражению. Миниатюры 1

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	06.04.2013, 07:44	6
	Вот вроде бы такой автомат должен быть: Миниатюры 1

@Marad 0 / 0 / 0 Регистрация: 05.04.2013 Сообщений: 15
	06.04.2013, 12:41 [ТС]	7
	kamre, Дело в том, что это еще нужно запрограммировать на С++ таблицой Добавлено через 6 минут alsav22, Просто 'а' не будет верен, так как есть 'd' и 'f' , над которым стоит знак плюс, означает что 'd' или 'f' должен быть обязательно, верно будет ad или af. Также ответом является просто элемент 'd' или 'f'. 0

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	06.04.2013, 13:22	8
	Сообщение от Marad kamre, Дело в том, что это еще нужно запрограммировать на С++ таблицой Ну так подправьте свою таблицу исходя из картинки автомата. Это совсем не сложно: из состояния '1' при встрече буквы 'b' переход идет в состояние '2', значит на 1 строке (соотв. '1') во 2 столбце (соотв. 'b') стоит значение 2 (соотв. '2'). 1

@Marad 0 / 0 / 0 Регистрация: 05.04.2013 Сообщений: 15
	06.04.2013, 15:55 [ТС]	9
	Извиняюсь, но до меня ваще не доходит, башка не шарит чета, можешь наброски хотя бы сделать 0

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	07.04.2013, 04:48	12
	Сообщение от Marad убрал первую нулевую строку, элементы прибавил на 1 Непонятно зачем прибавлял единицу. Сообщение от Marad Если же к примеру я ввожу acdddfn он должен вывести ошибку, а он говорит что это верно. Почему должен вывести ошибку, если эта строка подходит под выражение аbс(d\|f)+nh* ? И автомат распознает ее корректно: Миниатюры 0

@Marad 0 / 0 / 0 Регистрация: 05.04.2013 Сообщений: 15
	07.04.2013, 10:27 [ТС]	13
	d\|f означает, что должен быть только один из этих элементов, либо d, либо f. И если автомат видит их сразу двоих, то обязан видеть ошибку 0

@kamre 127 / 131 / 11 Регистрация: 25.12.2011 Сообщений: 443
	07.04.2013, 12:21	14
	Сообщение от Marad d\|f означает, что должен быть только один из этих элементов, либо d, либо f. И если автомат видит их сразу двоих, то обязан видеть ошибку (d\|f)+ допускает любое сочетание из d и f, откуда ошибка? 0

@Marad 0 / 0 / 0 Регистрация: 05.04.2013 Сообщений: 15
	07.04.2013, 22:32 [ТС]	17
	+ означает, что элемент может повторяться хоть сколько раз, но обязательно должен быть один раз. * означает, что элемент может повторяться хоть сколько раз, а может и не быть. d\|f означает, либо первый элемент, либо второй,но не могут быть вместе. Поэтому и выражение abc(d\|f)+nh* одним из ответом является d или f. 0

@Marad 0 / 0 / 0 Регистрация: 05.04.2013 Сообщений: 15
	08.04.2013, 17:09 [ТС]	20
	Все, спасибо вам ребята, програ работает отлично =) 0