2015-06-28
572
б) проверка на эквивалентность:
{1, 2, 3, 7} { 4, 5, 6, 8 } (по воздействию символа –| все состояния разбиты на допускающие и отвергающие)
воздействие символа а:
{1}; {2}; {3}; {7}; {5}; {4,6,8}.
воздействие символа b:
{1}; {2}; {3}; {7}; {5}; {4,6}; {8}.
воздействие символа c:
{1}; {2}; {3}; {7}; {5}; {4}; {6}; {8}.
Вывод: эквивалентных состояний нет (построен минимальный конечный автомат).
4 Полное описание конечного автомата:
V вх = {a,b,c, –|}; S = {1, 2, 3, 4, 5, 6, 7, 8}; Sнач = 1; Sдоп = { 4, 5, 6, 8}.
Варианты заданий темы 1 для самостоятельной подготовки
Построить конечный автомат (КА –распознаватель) для распознания регулярного множества цепочек трехсимвольного алфавита,,заданного в виде описания.
| № задачи | Описание регулярного множества |
| Содержит не более двух символов 1, начинается на 3, а символ 2 встречается только парами | |
| Содержит не более двух символов 2, начинается на 11, а символ 3 встречается только по одному | |
| Содержит ровно два символа 1, заканчивается на 23 и символы 1 и 2 не стоят рядом | |
| Содержит не более одного символа 3, начинается на 21, а символ 1 встречается только парами | |
| Содержит два символа 2, заканчивается на 13 и символы 2 и 3 не стоят рядом | |
| Содержит не более двух символов 3, начинается на 13, а символ 1 встречается только по одному | |
| Содержит ровно два символа 2, заканчивается на 31 и символы 2 и 3 не стоят рядом | |
| Содержит ровно одно сочетание 12, заканчивается на 2 и символы 2 и 3 не стоят рядом | |
| Содержит ровно одно сочетание 32, заканчивается на 1 и символы 1 и 3 не стоят рядом |
Вопросы по теории темы 1 для самостоятельной подготовки
|
|
|
1 Понятие конечного автомата (КА); задание КА.
2 Эквивалентные и недостижимые состояния КА, получение минимального КА.
3 Построение диаграммы состояний КА.
4 Построение таблицы переходов для КА.
Тема № 2 Построение МП – автоматов
Построение МП – распознавателей
Задание
Построить МП–распознаватель для цепочек из 0 и 1, в которых 0 встречаются только по два.
