Курсовая работа: Моделирование работы конечного распознавателя для последовательно-сти элементов типа "дата" в немецком формате, разделенных запятыми и заключённых в фигурные скобки
· Множество нетерминальных символов: <фраза>, <дата>, <год>, <месяц>, <день>, <цифра>, <цифра1>, <цифра2>.
· Множество правил вывода R0,R1, R2, R3, R4, R5, R6, R7, R8, R9, R10, R11, R12, R13, R14.
2 Построение конечного автомата
Между конечными автоматами и автоматными грамматиками существует тесная связь: класс языков, допускаемых конечными автоматами, совпадает с классом языков, порождаемых автоматными грамматиками.
Для построения конечного автомата составленную грамматику путем введения дополнительных состояний надо преобразовать к автоматному виду, в результате получится следующая таблица переходов:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | { | } | . | , | |
| да | ||||||||||||||
| нет | ||||||||||||||
| день | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | денф | нет |
| денб | Дб1 | Дб1 | Дб1 | Цф1 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет |
| Дб1 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | нет | нет | нет | нет |
| Дб2 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | мес | нет |
| Цф1 | Дб2 | Дб2 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет |
| денм | Дб1 | Дб1 | Дб1 | Цф0 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет |
| Цф0 | Дб2 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет |
| денф | Дб1 | Дб1 | Цф3 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет |
| Цф3 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | Дб2 | нет | нет | нет | нет | нет | нет |
| мес | Мес0 | Мес1 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет |
| Мес0 | нет | месб | фев | месб | месм | месб | месм | месб | месб | месм | нет | нет | нет | нет |
| Мес1 | месб | месм | месб | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет |
| месб | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | денб | нет |
| месм | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | денм | нет |
| дата | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | год | нет | нет | нет |
| год | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | Цг1 | нет | нет | нет | нет |
| Цг1 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | Цг2 | нет | нет | нет | нет |
| Цг2 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | Цг3 | нет | нет | нет | нет |
| Цг3 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | Цг4 | нет | нет | нет | нет |
| Цг4 | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | нет | да | нет | день |
3 Граф детерминированного автомата
Для того, чтобы улучшить зрительное восприятие и облегчить понимание сложных синтаксических описаний, часто применяют представление правил грамматики в виде синтаксических диаграмм.
Синтаксическая диаграмма представляет собой ориентированный граф для каждого правила грамматики.
4 Программное моделирование работы конечного автомата
#include "iostream.h"
#include "stdio.h"
#include "conio.h"
int main()
{int i,j,kol,tsost,slsost,tsymb;
int tabl[24][14]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0},//da
{1,1,1,1,1,1,1,1,1,1,1,1,1,1},//net
{1,1,1,1,1,1,1,1,1,1,3,1,1,1},
{4,4,4,5,1,1,1,1,1,1,1,1,1,1},
{1,6,6,6,6,6,6,6,6,6,1,1,1,1},
{8,9,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,20,1},
{16,16,16,16,16,16,16,16,16,16,1,1,1,1},
{1,1,1,1,1,1,1,1,1,1,1,1,10,1},
{1,1,1,1,1,1,1,1,1,1,1,1,11,1},
{12,13,1,1,1,1,1,1,1,1,1,1,1,1},
{14,15,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,23,1,23,1,1,23,1,1,1,1},
{23,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,23,1,23,1,23,1,23,23,1,1,1,1,1},