Форум программистов, компьютерный форум CyberForum.ru

Реализация работы конечного автомата - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.86
Heit
0 / 0 / 0
Регистрация: 29.07.2012
Сообщений: 20
16.04.2013, 22:21     Реализация работы конечного автомата #1
Задача: Построить конечный автомат, проверяющий есть ли во входной цепочке S хотя бы одна из следующих подстрок: X1=“aaa”; X2=“aab”; X3=“abab”.
Нужно:
1) построить конечный автомат, таблицу переходов, схему переходов и прочее, прочее, прочее. - это всё сделано.
2) написать программу, реализующую работу этого автомата. программа должна работать с файлами. входной файл состоит из одной цепочки только из символов a и b, в выходном файле должны быть (по придуманному автомату) на первой строчке входная цепочка, на второй - "Да/Нет, aaa/aab/abab/символ пустой строки"
собственно вопросы:
1) можно краткое описание работы с файлами в СИ++ ))
2) не очень понимаю как должен реализовываться автомат в программе: ИМХО
есть три "обязательные" переменные: строка(входная цепочка), итог(да/нет), подстрока(ааа,ааб,абаб), по идее из входного файла читается посимвольно(такая функция есть в СИ++?) добавляется в переменную строка, затем "небольшой пробел в размышлениях" (встроенными функциями проверки подстрок пользоваться скорее всего нельзя)
и при нахождении любой подстроки ИТОГ=Да, ПОДСТРОКА=подстроке, и больше они не меняются, только увеличивается СТРОКА, ну и вывод этого всего в выходной файл
P.S. если нужна первая часть задания с построенным автоматом и прочими заданиями по нему(ворд файл на 4 страницы), то могу выложить/прислать, если подскажете как
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.04.2013, 22:21     Реализация работы конечного автомата
Посмотрите здесь:

Алгоритм нахождения минимального конечного автомата C++
C++ Реализация работы с массивом только в одном потоке
C++ Конечный автомат(Разработать граф переходов конечного автомата для выделения в тексте исходной программы на С++ комментариев)
Построение конечного недетерминированного автомата C++
C++ Построение конечного автомата по регулярной грамматике
Создать программу конечного автомата C++
C++ Реализовать поиск подстрок с помощью недетерминированного конечного автомата

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,917
Записей в блоге: 1
17.04.2013, 02:20     Реализация работы конечного автомата #2
1) Любая книжка для начинаюших
2) Да, есть функции посимвольного ввода и работы с потоками
3) Если у вас в самом деле автомат, никаких функций сравнения подстрок ему НЕ требуется, текущее состояние автомата и есть представление введенной подстроки.

Если по окончании ввода вы оказались в одном из допускающих состояний - ответ "Да", иначе - "Нет".
Никаких дополнительных проверок не требуется.

Вот это поищите:

Мозговой М.В. - Классика программирования- алгоритмы, языки, автоматы, компиляторы. Практический подход. M.: Наука и техника, 2006

P.S.

Вот здесь по ссылкам пройдитесь: Parsers
Изображения
 
Heit
0 / 0 / 0
Регистрация: 29.07.2012
Сообщений: 20
28.04.2013, 20:38  [ТС]     Реализация работы конечного автомата #3
Попробовал написать код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdlib>
#include <iostream>
#include <stdio.h>
using namespace std;
 
int main(int argc, char *argv[])
{
    FILE *fp; 
    char c,fname[15],stroka[255],podstroka[5],itog[4];
    int i=0,j,result=0,flag=0,l;
    int mass[6][3]={{1,0,0},{2,4,0},{3,3,0},{3,3,1},{5,0,0},{2,3,0}};
    puts ("VVedite imya faila s vhodnoi cepochkoi:");
    gets (fname);
    if ((fp=fopen(fname,"r")) == NULL)
      {
        cout<<"Fail ne naiden";
        getchar();
        return 1;
      }
    while ((c=getc(fp)) != EOF)
    {
      flag=1;
      if ((c !='a') and (c !='b')) 
      {
        cout<<"simvol = "<<c<<" ne podhodit. Fail doljen soderjat tolko simvoli 'a' i 'b'.\n";
        break;
      }
      else if (c=='a')
      {
        j=mass[i][1];
        if ((j==3) and (i!=3))
        {
          result=mass[j][3];
          strcpy(podstroka,"aaa");
        }
        i=j;
        l=strlen(stroka);
        stroka[l]=c;
        stroka[l+1];
      }
      else
      {
        j=mass[i][2];
        if ((j==3) and (i!=3))
          if (i==2)
          {
            result=mass[j][3];
            strcpy(podstroka,"aab");
          }
          else
          {
            result=mass[j][3];
            strcpy(podstroka,"abab");             
          }
        i=j;
        l=strlen(stroka);
        stroka[l]=c;
        stroka[l+1];
      }
    }
    fclose (fp);
    if ((flag==0) or (result==0)) 
      strcpy(itog,"NET");
    else
      strcpy(itog,"DA");
      
    if (flag==1)
    {   
      puts ("VVedite imya faila kuda zapisat resultat:");
      gets (fname);
      if ((fp=fopen(fname,"w")) == NULL)
      {
        cout<<"Fail ne naiden";
        getchar();
        return 1;
      }
      fputs("Vhodnaya cepochka:\n",fp);
      fputs(stroka,fp);
      fputs(itog,fp);
      fputs(podstroka,fp);
      fclose(fp);
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}
, вроде все работает, но при копировании в выходном файле какие-то непонятные символы. При добаление в код вывода переменной СТРОКИ на консоль появляются такие же непонятные символы. Почему может кто объяснить? и как лучше(правильней) добавить с переменную СТРОКА символ С?
P.S. Код толком не оптимизирован, главное пока что разобрать с основной проблемой, но и какието замечание по коду тоже приветсвуются))

Добавлено через 2 часа 37 минут
с основной ошибкой разобрался, возник другой вопрос :
при инициализации массива символов STROKA[255] там уже есть какие то символы и добавляться туда символы С начинают не с начала. можно как то обнулиить весь массив символов?
Yandex
Объявления
28.04.2013, 20:38     Реализация работы конечного автомата
Ответ Создать тему
Опции темы

Текущее время: 06:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru