Недетерминированные конечные автоматы. Поисковая система

Написать программу, осуществляющую поиск множества ключевых слов {beta, begin, green} в текстовом файле. Результатом работы программы должен быть список найденных слов и номера позиций этих слов в тексте. Символ новой строки не учитывать при подсчете позиции слова.

Использовать теории регулярных выражений и конечных автоматов:
1. Упростить, если это возможно, регулярное выражение;
2. Для заданного регулярного выражения построить соответствующий ему КА; Представление – диаграмма.
3. Если автомат, полученный в предыдущем пункте, недетерминированный, то преобразовать его в ДКА, используя метод “ленивого” вычисления подмножеств;
4. Если это удобно, переобозначить состояния полученного ДКА;
5. Используя ДКА, написать программу поиска ключевых слов в текстовом файле.

Решение.
1. Регулярное выражение: be( ta | gin ) | green
2. Диаграмма НКА, соответствующего этому регулярному выражению: ( рис )

НКА может быть представлен в виде таблицы переходов. В такой таблице: строки – состояния КА, столбцы – входные символы. Запись в строке для символа a - подмножество состояний, которые могут быть достигнуты из состояния при входном символе a. Строка, соответствующая начальному состоянию, отмечена стрелкой. Строки, соответствующие заключительным состояниям, отмечены «*».

Изначально таблица переходов ДКА содержит только одно состояние – eps( {S0} ). Это состояние объявляется текущим подмножеством .
Для текущего состояния по каждому символу из входного алфавита строим подмножество eps( move( T, a ) ).
Тем самым происходит заполнение текущей строки в таблице переходов ДКА. Если при этом образуются новые подмножества, те, которые еще не включены в эту таблицу, то дописываем их в новую строку как еще одно состояние ДКА.
Процесс останавливается после заполнения всей таблицы. В построенной таблице строка, соответствующая eps( {S0} ), объявляется начальным состоянием для ДКА.
Заключительными объявляются те из полученных подмножеств, в состав которых входит хотя бы одно из заключительных состояний исходного НКА.

//Программа поиска слов "beta", "begin", "green" в заданном тексте
#include <stdio.h>
#include <fstream.h>
#include <string.h>
#include <ctype.h>
 
//таблица переходов ДКА
int M[13][9] =
{
    1,    0,    0,    0,    2,    0,    0,    0,    0,
    1,    3,    0,    0,    2,    0,    0,    0,    0,
    1,    0,    0,    0,    2,    0,    0,    4,    0,
    1,    0,    5,    0,    6,    0,    0,    0,    0,
    1,    7,    0,    0,    2,    0,    0,    0,    0,
    1,    0,    0,    8,    2,    0,    0,    0,    0,
    1,    0,    0,    0,    2,    9,    0,    4,    0,
    1,    10,    0,    0,    2,    0,    0,    0,    0,
    1,    0,    0,    0,    2,    0,    0,    0,    0,
    1,    0,    0,    0,    2,    0,    11,    0,    0,
    1,    0,    0,    0,    2,    0,    12,    0,    0,
    1,    0,    0,    0,    2,    0,    0,    0,    0,
    1,    0,    0,    0,    2,    0,    0,    0,    0
};
// Шаблон части входного алфавита
// Используется функцией NumbCol для
// определения по символу номера столбца в
// таблице переходов
char PatternStr[] = "betaginr";    
 
// Прототип функции переходов    
int Move(int S, char C);
 
// массив, R[i] содержит номер
// столбца в таблице переходов символа i
int R[26] = { 3, 0, 8, 8, 1, 8, 4, 8, 5, 8, 8, 8, 8, 6, 8, 8, 8, 7, 8, 2, 8, 8, 8, 8, 8, 8 };
 
int main()
{
    cout << "Searching words \"beta, begin, green\"";
    cout << "\nFind:\t\t  Word   Position" << endl;
 
    // Текущий входной символ
    char C;    
 
    // num[] - Количество найденных ключевых слов
    // S - Текущее состояние ДКА
    int i = 0, num[3] = {0}, S;
 
    // Открытие файла с данными
    ifstream fin( "dka.txt", ios::in );
 
    // Начальное состояние
    S = 0;    
 
    // Первый символ входной строки
    fin.get(C); 
    i++;        
 
    // Пропуск символа новой строки
    while( C == '\n' ) fin.get(C);
 
    while( C != EOF ) 
    {            
        // Переход к следующему состоянию
        S = Move( S, C );    
 
        // Проверка заключительных состояний
        switch( S ) 
        {        
            // Найдено beta
            case 8:   
                // Увеличиваем счетчик на 1
                num[0]++; 
                // Выводим найденное слово, позицию слова в тексте
                cout << "\t\t  beta   " << i-strlen("beta")+1 << endl; 
                break;
            // Найдено begin
            case 11: 
                num[1]++;
                cout << "\t\t  begin  " << i-strlen("begin")+1 << endl; 
                break;
            // Найдено green
            case 12: 
                num[2]++;
                cout << "\t\t  green  " << i-strlen("green")+1 << endl; 
                break;
        }
        // Следующий символ входной строки
        fin.get(C); 
            i++;
 
        // Пропуск символа новой строки
        while (C == '\n') 
            fin.get(C);
    }
 
    // Закрытие файла
    fin.close();                
 
    // Статистика поиска
    cout << "\nStatistic:\t  Word   Quantity" << endl;
    cout << "\t\t  beta   " << num[0] << endl;
    cout << "\t\t  begin  " << num[1] << endl;
    cout << "\t\t  green  " << num[2] << endl;
 
    return 0;
}
 
// Функция переходов по ДКА
int Move(int S, char C)    
{
    // Следующее состояние из таблицы M
    return M[ S ][ R[tolower(C)-'a'] ];    
}

Ключевые слова: 
регулярные выражения, недетерминированные конечные автоматы, поисковая система
search.jpg