Главная

Регулярные выражения

Опубликовано Admin в Чт, 08/07/2008 - 20:18
Задано регулярное выражение r = (a|b|c)*bc.
Входной алфавит ∑= {a, b, c}.
Написать программу, распознающую строки, соответствующие данному регулярному выражению.
(Соответствуют: abbbabcbbcabc, bc, abc, bbbc, abcbc, cbc, aabbccbc. Не соответствуют: abccba, bca, abcbcc).
Использовать теории регулярных выражений и конечных автоматов (КА):
1. Для заданного регулярного выражения построить соответствующий ему КА;
2. Если автомат, полученный в предыдущем пункте, недетерминированный, то преобразовать его в ДКА;
3. Используя ДКА, написать программу-распознаватель.

Решение
Входной алфавит ∑= {a, b, c}.
Регулярное выражение r = (a|b|c)*bc.

1. КА, соответствующий (a|b|c)*bc:
Состояния КА \ ∑ a b c Прочие
→ A (начальное) A B A E
B A B D E
* D (заключительное) A B A E
E E E E E

2. Полученный КА является ДКА. Преобразований проводить не нужно.
3. Используя ДКА, пишем программу-распознаватель.

Программа
#include <iostream.h>
 
enum TState {A, B, D, E};   // Алфавит состояний автомата
 
TState Move(TState S, char C);   // Прототип функции переходов
 
void main()
{
TState S;   // Текущее состояние автомата
char C;	      // Текущий входной символ
 
S = A;	      // Начальное состояние
cin.get(C);    // Первый символ входной строки
while (C != '\n') {    // Пока не прочитана вся входная строка
S = Move(S, C);       // Переход в следующее состояние
cin.get(C);               // Следующий символ входной строки
}
 
switch (S) {     // Проверка допустимости входной строки
case E: cout << "Недопустимый символ"	<< endl; break;
case D: cout << "Да"<< endl; break;
default: cout << "Нет"	<< endl; break;
}
cin.get(C);      // Пауза для просмотра результата
}
 
TState Move(TState S, char C)	     // Функция переходов
{
switch (S) {     // Переходы к следующему состоянию
case A:	if (C == 'a' || C == 'c')	return A;
else if (C == 'b')	return B;
else			return E;
case B:	if (C == 'a')	return A;
else if (C == 'b')	return B;
else if (C == 'c')	return D;
else			return E;
case D:	if (C == 'a' || C == 'c')	return A;
else if (C == 'b')	return B;
else			return E;
default:		return E;
}
}

Результат работы:
aaabbcccccbc
Да
Ключевые слова: 
регулярное выражение, детерминированный конечный автомат.