Синтез распознающего автомата
Характеристика способов задания языков грамматиками, распознающими автоматами. Особенности построения модели конечного автомата, распознающего заданный язык, и разработка его программной реализации. Процедура построения детерминированного автомата.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 02.12.2013 |
| Размер файла | 100,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
8
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Курсовая работа
Синтез распознающего автомата
Выполнил
Д.Х. Шакирьянов
ВВЕДЕНИЕ
автомат распознающий язык программный
В наше время, конечные автоматы имеют широкое распространение в компиляторах языков, поэтому программная реализация конечного автомата приобретает высокое значение. Также они применяются для создания лингвистических процессоров, для описания и обработки формальных языков.
Каждый автомат имеет конечное число входов, воспринимающих информацию, изображаемую конечным числом символов из некоторого алфавита, и конечное число выходов для выдачи информации.
Выходная информация автомата зависит не только от входной информации, но и от внутреннего состояния автомата. Конечный автомат имеет конечное число состояний.
Автоматы часто представляют сетями. Для автомата характерен последовательный способ функционирования: автомат последовательно переходит из состояния в состояние с заданной функцией перехода и осуществляет очередной шаг.
Целю курсовой работы, является изучение способов задания языков грамматиками, распознающими автоматами, построение модели конечного автомата, распознающего заданный язык, и его программной реализации.
1.ПОСТАНОВКА ЗАДАЧИ
Необходимо построить праволинейную грамматику на основе индивидуального задания и приведенного ниже определения формальной грамматики. Затем по праволинейной грамматике построить автоматную грамматику. Построить недетерминированный конечный автомат по полученной автоматной грамматике. Преобразовать недетерминированный конечный автомат в детерминированный. Минимизировать полученный автомат, построить таблицу и граф переходов минимального автомата.
Входными данными для автомата является цепочка (строки, вводимые с клавиатуры) из терминальных символов. На выходе автомата выдается состояние - отвергающее или допускающее входную цепочку.
Задана формальная грамматика
G = <Vt, Vn, S, P>,
где
Vt = {C1, C2,…, C18} - терминальный словарь,
Vn = {S, A, B, C, D, E, F}- нетерминальный словарь,
S - начальный символ грамматики, S Vn,
P - множество правил вывода
Правила вывода, имеют следующий вид:
Sc1 c2 c3 A; Sc1 c4 c5 B; Sc6 C; Sc7 F;
Ac8 D; Ac9; Bc8 E; Bc9; Cc8E; Cc9;
Dc10 S; Dc11; Ec10 S; Ec11;
Fc12 c13 c14 c15; Fc16 c13 c14 c15; Fc17 c18 c15.
2. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ
Индивидуальное задание формируется посредством занесения во вторую строку таблицы 1 первых 18 символов фамилии, имени и отчества студента с обязательными пробелами между фамилией и именем, именем и отчеством. Затем в третью строку студент заносит для каждого из 18 символов строки символ из алфавита {x0, x1, x2, x3, x4, x5, x6 ,x7} в соответствии с таблицей 2.
Таблица 1
|
Ci |
C1 |
C2 |
C3 |
C4 |
C5 |
C6 |
C7 |
C8 |
C9 |
C10 |
C11 |
C12 |
C13 |
C14 |
C15 |
C16 |
C17 |
C18 |
|
|
S1 |
Ш |
А |
К |
И |
Р |
Ь |
Я |
Н |
О |
В |
_ |
Д |
И |
Н |
А |
Р |
_ |
Х |
|
|
Xi |
X2 |
X1 |
X7 |
X3 |
X0 |
X6 |
X7 |
X7 |
X4 |
X2 |
X5 |
X6 |
X3 |
X7 |
X1 |
X0 |
X5 |
X5 |
Таблица 2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах контингента студентов. Затем буквы были сформированы в восемь групп с таким расчетом, чтобы появление каждого из символов x0 - x7 было равновероятным.
Таблица 2
|
А |
Б |
В |
Г |
Д |
Е |
Ж |
З |
И |
Й |
К |
Л |
М |
Н |
О |
П |
|
|
x1 |
x5 |
x2 |
x4 |
x6 |
x6 |
x4 |
x3 |
x3 |
x0 |
x7 |
x0 |
x3 |
x7 |
x4 |
x5 |
|
|
P |
С |
Т |
У |
Ф |
Х |
Ц |
Ч |
Ш |
Щ |
Ь |
Ы |
Э |
Ю |
Я |
_ |
|
|
x0 |
x4 |
x5 |
x7 |
x2 |
x5 |
x1 |
x2 |
x2 |
x0 |
x6 |
x1 |
x1 |
x3 |
x7 |
x5 |
Эта грамматика, являющаяся праволинейной, приводится к виду G'=<V't, V'n, S, R'>, где V't={x0, …, x7} - новый терминальный словарь; R' - множество правил вывода, получаемых из заданных заменой символов из алфавита Vt символами из алфавита V't в соответствии с таблицей 1. В данном примере они имеют вид:
S x2 x1 x7 A | x2 x3 x0 B | x6 C | x7 F;
A x7 D | x4;
B x7 E | x4;
C x7 E | x4;
D x2 S | x5;
E x2 S | x5;
F x6 x3 x7x1 | x0 x3 x7 x1 | x5 x5 x1;
Здесь “|” - металингвистический символ (связка), читаемый как "ИЛИ".
Грамматика G', порождаемая из заданной грамматики G, является индивидуальным заданием студента. Примечание. Мощность |V't| словаря V't (число символов в нем) в рассмотренном случае равна 8.
3. ПЕРЕХОД ОТ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ К АВТОМАТНОЙ
Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в модифицированную автоматную G''=< V't, V''n, S, R''>. Таким образом получим множество R'' правил вывода:
Sx2 S1; S1x1 S2; S2x7 A;
Sx2 S3; S3x3 S4; S4x0 B;
Sx6 C;
Sx7 F;
Ax7 D; Ax4 A1; A1;
Bx7 E; Bx4 B1; B1;
Cx7 E; Cx4 C1; C1;
Dx2 S; Dx5 D1; D1;
Ex2 S; Ex5 E1; E1;
Fx6 F1; F1x3 F2; F2x7 F3; F3x1 F4; F4;
Fx0 F5; F5x3 F6; F6x7 F7; F7x1 F8; F8;
Fx5 F9; F9x5 F10; F10x1 F11; F11.
Таким образом, нетерминальный словарь теперь имеет вид V''n = {S, S1, S2, S3, S4, A, A1, B, B1, C, C1, D, D1, E, E1, F, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11} и его мощность |V''n| равна 27.
4.ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА
Построим на основе грамматики G'' конечный автомат. При этом нетерминальным символам грамматики V''n поставим в соответствие состояния автомата (оставим для них те же обозначения). Начальному нетерминалу S поставим в соответствие начальное состояние автомата S. Правилам вывода поставим в соответствие переходы автомата. В результате получим таблицу 3 - таблицу переходов недетерминированного конечного автомата, соответствующего рассматриваемому примеру.
Таблица 3. Таблица переходов недетерминированного частичного автомата
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|||
|
S |
S1,S3 |
C |
F |
0 |
||||||
|
S1 |
S2 |
0 |
||||||||
|
S2 |
A |
0 |
||||||||
|
S3 |
S4 |
0 |
||||||||
|
S4 |
B |
0 |
||||||||
|
A |
A1 |
D |
0 |
|||||||
|
A1 |
1 |
|||||||||
|
B |
B1 |
E |
0 |
|||||||
|
B1 |
1 |
|||||||||
|
C |
C1 |
E |
0 |
|||||||
|
C1 |
1 |
|||||||||
|
D |
S |
D1 |
0 |
|||||||
|
D1 |
1 |
|||||||||
|
E |
S |
E1 |
0 |
|||||||
|
E1 |
1 |
|||||||||
|
F |
F5 |
F9 |
F1 |
0 |
||||||
|
F1 |
F2 |
0 |
||||||||
|
F2 |
F3 |
0 |
||||||||
|
F3 |
F4 |
0 |
||||||||
|
F4 |
1 |
|||||||||
|
F5 |
F6 |
0 |
||||||||
|
F6 |
F7 |
0 |
||||||||
|
F7 |
F8 |
0 |
||||||||
|
F8 |
1 |
|||||||||
|
F9 |
F10 |
0 |
||||||||
|
F10 |
F11 |
0 |
||||||||
|
F11 |
1 |
Полученный автомат является не полностью определенным (частичным), поскольку в таблице переходов (табл. 3) есть незаполненные клетки, и, кроме того, недетерминированным, поскольку в той же таблице есть клетки, содержащие пары состояний.
Чтобы получить полностью определенный автомат, следует ввести дополнительное состояние Er (ошибка). Для этого нужно дополнить автомат соответствующей строкой с состоянием Er и во все пустые клетки таблицы переходов вписать это состояние Er (см. табл. 4).
Таблица 4. Таблица переходов недетерминированного полностью определенного автомата
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|||
|
S |
Er |
Er |
S1,S3 |
Er |
Er |
Er |
C |
F |
0 |
|
|
S1 |
Er |
S2 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
S2 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
A |
0 |
|
|
S3 |
Er |
Er |
Er |
S4 |
Er |
Er |
Er |
Er |
0 |
|
|
S4 |
B |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
A |
Er |
Er |
Er |
Er |
A1 |
Er |
Er |
D |
0 |
|
|
A1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
B |
Er |
Er |
Er |
Er |
B1 |
Er |
Er |
E |
0 |
|
|
B1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
C |
Er |
Er |
Er |
Er |
C1 |
Er |
Er |
E |
0 |
|
|
C1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
D |
Er |
Er |
S |
Er |
Er |
D1 |
Er |
Er |
0 |
|
|
D1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
E |
Er |
Er |
S |
Er |
Er |
E1 |
Er |
Er |
0 |
|
|
E1 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
F |
F5 |
Er |
Er |
Er |
Er |
F9 |
F1 |
Er |
0 |
|
|
F1 |
Er |
Er |
Er |
F2 |
Er |
Er |
Er |
Er |
0 |
|
|
F2 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
F3 |
0 |
|
|
F3 |
Er |
F4 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
F4 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
F5 |
Er |
Er |
Er |
F6 |
Er |
Er |
Er |
Er |
0 |
|
|
F6 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
F7 |
0 |
|
|
F7 |
Er |
F8 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
F8 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
F9 |
Er |
Er |
Er |
Er |
Er |
F10 |
Er |
Er |
0 |
|
|
F10 |
Er |
F11 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
F11 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
Далее построим граф переходов (Рис. 1), при этом в нем опустим состояния исходящие из недопускающих состояний и ведущие в состояние Er(ошибка).
Граф переходов автомата, построенный по таблице 4, показан на рис. 1.
8
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 1. Граф переходов исходного (недетерминированного) автомата
Примечание. Для того чтобы не затемнять картину, на рисунке опущены дуги, исходящие из недопускающих состояний и ведущие в состояние Er (ошибка). Так, например, опущена дуга, ведущая из состояния S в состояние Er, которая должна быть помечена дизъюнкцией входных символов x0x1x2x3x4.
Все дуги, ведущие из допускающих состояний в состояние Er, должны быть помечены дизъюнкцией x0x1x2x3x4x5x6x7.
5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ
Процедура построения детерминированного автомата Ад, эквивалентного недетерминированному автомату Ан, задается следующими шагами:
1. Пометить первую строку таблицы переходов для Ад множеством начальных состояний автомата Ан. Применить к этому множеству шаг 2.
2. По данному множеству состояний В, помечающему строку таблицы переходов автомата Ад, для которой переходы еще не вычислены, вычислить те состояния автомата Ан, которые могут быть достигнуты из В с помощью каждого входного символа х, и поместить полученные множества состояний в соответствующие ячейки таблицы для автомата Ад. Символически это выражается так: если - функция недетерминированных переходов, то функция детерминированных перехода ' задается формулой '(B, x) = {S | S (T, x), Т В}
3. Для каждого нового множества, порожденного переходами на шаге 2, посмотреть, имеется ли уже в Ад строка, помеченная этим множеством. Если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, никаких действий не требуется.
4. Если в таблице автомата Ад есть строка, для которой еще не вычислены переходы, вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, перейти к шагу 5.
5. Пометить строку как допускающее состояние автомата Ад тогда и только тогда, когда она содержит допускающее состояние недетерминированного автомата. В противном случае пометить как отвергающее состояние.
Описанная процедура гарантирует, что детерминированный автомат не содержит недостижимых состояний.
В результате применения этого алгоритма от недетерминированного автомата (табл. 4, рис. 1) можно перейти к эквивалентному детерминированному автомату, таблица переходов которого приведена в таблице 5.
Таблица 5. Таблица переходов детерминированного автомата.
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|||
|
{S} |
{Er} |
{Er} |
{S1,S3} |
{Er} |
{Er} |
{Er} |
{C} |
{F |
0 |
|
|
{S1,S3} |
{Er} |
{S2} |
{Er} |
{S4} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{S2} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{A} |
0 |
|
|
{S4} |
{B} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{A} |
{Er} |
{Er} |
{Er} |
{Er} |
{A1} |
{Er} |
{Er} |
{D} |
0 |
|
|
{A1} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{B} |
{Er} |
{Er} |
{Er} |
{Er} |
{B1} |
{Er} |
{Er} |
{E} |
0 |
|
|
{B1} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{C} |
{Er} |
{Er} |
{Er} |
{Er} |
{C1} |
{Er} |
{Er} |
{E} |
0 |
|
|
{C1} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{D} |
{Er} |
{Er} |
{S} |
{Er} |
{Er} |
{D1} |
{Er} |
{Er} |
0 |
|
|
{D1} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{E} |
{Er} |
{Er} |
{S} |
{Er} |
{Er} |
{E1} |
{Er} |
{Er} |
0 |
|
|
{E1} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{F} |
{F5} |
{Er} |
{Er} |
{Er} |
{Er} |
{F9} |
{F1} |
{Er} |
0 |
|
|
{F1} |
{Er} |
{Er} |
{Er} |
{F2} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{F2} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{F3} |
0 |
|
|
{F3} |
{Er} |
{F4} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{F4} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{F5} |
{Er} |
{Er} |
{Er} |
{F6} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{F6} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{F7} |
0 |
|
|
{F7} |
{Er} |
{F8} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{F8} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{F9} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{F10} |
{Er} |
{Er} |
0 |
|
|
{F10} |
{Er} |
{F11} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
|
|
{F11} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
1 |
|
|
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
{Er} |
0 |
Перейдем к более простым обозначениям состояний автомата:
{S}Y; {S1,S3}Y1;{S2}Y2; {S4}Y3;
{A}Y4;{A1}Y5;{B}Y6; {B1}Y7;
{C}Y8;{C1}Y9;{D}Y10; {D1}Y11;
{E}Y12;{E1}Y13;{F}Y14; {F1}Y15;
{F2}Y16; {F3}Y17; {F4}Y18; {F5}Y19;
{F6}Y20; {F7}Y21; {F8}Y22; {F9}Y23;
{F10}Y24; {F11}Y25; {{Er}}{Er}.
В новых обозначениях таблица переходов автомата приведена в табл. 6.
Таблица 6. Таблица переходов детерминированного автомата (новые обозначения состояний)
|
x0 |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|||
|
Y |
Er |
Er |
Y1 |
Er |
Er |
Er |
Y8 |
Y14 |
0 |
|
|
Y1 |
Er |
Y2 |
Er |
Y3 |
Er |
Er |
Er |
Er |
0 |
|
|
Y2 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Y4 |
0 |
|
|
Y3 |
Y6 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
Y4 |
Er |
Er |
Er |
Er |
Y5 |
Er |
Er |
Y10 |
0 |
|
|
Y5 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Y6 |
Er |
Er |
Er |
Er |
Y7 |
Er |
Er |
Y12 |
0 |
|
|
Y7 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Y8 |
Er |
Er |
Er |
Er |
Y9 |
Er |
Er |
Y12 |
0 |
|
|
Y9 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Y10 |
Er |
Er |
Y |
Er |
Er |
Y11 |
Er |
Er |
0 |
|
|
Y11 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Y12 |
Er |
Er |
Y |
Er |
Er |
Y13 |
Er |
Er |
0 |
|
|
Y13 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Y14 |
Y19 |
Er |
Er |
Er |
Er |
Y23 |
Y15 |
Er |
0 |
|
|
Y15 |
Er |
Er |
Er |
Y16 |
Er |
Er |
Er |
Er |
0 |
|
|
Y16 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Y17 |
0 |
|
|
Y17 |
Er |
Y18 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
Y18 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Y19 |
Er |
Er |
Er |
Y20 |
Er |
Er |
Er |
Er |
0 |
|
|
Y20 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Y21 |
0 |
|
|
Y21 |
Er |
Y22 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
Y22 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Y23 |
Er |
Er |
Er |
Er |
Er |
Y24 |
Er |
Er |
0 |
|
|
Y24 |
Er |
Y25 |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
|
|
Y25 |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
1 |
|
|
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
Er |
0 |
Построим граф переходов автомата, построенный по таблице 6, показан на рис. 2.
8
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 2 Граф переходов детерминированного автомата эквивалентного исходному
Примечание. Чтобы не загромождать рисунок, не изображено состояние {Er} а также дуги, ведущие в него из других состояний.
6.ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЩЕЙ РАСПОЗНАЮЩИЙ АВТОМАТ
Назначение.
Контрольный пример необходим для тестирования программной реализации автомата.
Исходные данные.
Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата: {x0, x1, x2, x3, x4, x5, x6, x7}.
Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики. Для проверки правильности работы автомата нужно проверить его с помощью допустимых цепочек. Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символ. Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал. Выписать терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.
Для полной проверки автомата получим несколько недопустимых цепочек. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле. Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.
Результаты испытания программы представлены в таблице 7.
Таблица 7. Результаты испытаний
|
Номер |
Входная цепочка |
Результат работы программы |
|
|
1 |
х2x5x4x2 |
Незаконченная строка |
|
|
2 |
x0x4x3x7 |
Правильная строка |
|
|
3 |
x2x5x4x1x6x4x5 |
Правильная строка |
|
|
4 |
x0x1x6 |
Незаконченная строка |
|
|
5 |
x0x1x6x4 |
Незаконченная строка |
ЗАКЛЮЧЕНИЕ
В ходе выполнения курсовой работы была построена праволинейная грамматика и ее граф. В дальнейшем по ней была построена автоматная грамматика, из которой в свою очередь был построен недетерминированный конечный автомат. Недетерминированный конечный автомат был сведен к эквивалентному детерминированному. Я произвела минимизацию детерминированного автомата методом разбиения.
Грамматики и автоматы сопровождены графическими изображениями. Результаты минимизации автоматов с помощью теории автоматов совпали с результатами программы реализующей распознающий автомат. Результаты программной реализации удовлетворительны.
ПРИЛОЖЕНИЯ
Текст программы
Здесь представлен программный код реализующий распознающий автомат.
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
btn1: TButton;
mmo1: TMemo;
mmo2: TMemo;
procedure FormCreate(Sender: TObject);
procedure btn1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
function CheckDigit(ch:char):boolean;
function NextState(sym:char; state:string):string;
implementation
{$R *.dfm}
function NextState(sym:char; state:string):string;
begin
if state='1' then
case sym of
'0':begin result:='2'; exit; end;
'1':begin result:='6'; exit; end;
'2':begin result:='4'; exit; end;
else begin result:='0'; exit; end;
end;
if state='2' then
case sym of
'1':begin result:='3'; exit; end;
'4':begin result:='3'; exit; end;
else begin result:='0'; exit; end;
end;
if state='3' then
case sym of
'3':begin result:='4'; exit; end;
'6':begin result:='4'; exit; end;
else begin result:='0'; exit; end;
end;
if state='4' then
case sym of
'5':begin result:='5'; exit; end;
'7':begin result:='11'; exit; end;
else begin result:='0'; exit; end;
end;
if state='5' then
case sym of
'4':begin result:='1'; exit; end;
'6':begin result:='11'; exit; end;
else begin result:='0'; exit; end;
end;
if state='6' then
case sym of
'0':begin result:='7'; exit; end;
'6':begin result:='10'; exit; end;
'7':begin result:='7'; exit; end;
else begin result:='0'; exit; end;
end;
if state='7' then
case sym of
'3':begin result:='8'; exit; end;
else begin result:='0'; exit; end;
end;
if state='8' then
case sym of
'7':begin result:='9'; exit; end;
else begin result:='0'; exit; end;
end;
if state='9' then
case sym of
'5':begin result:='11'; exit; end;
else begin result:='0'; exit; end;
end;
if state='10' then
case sym of
'4':begin result:='9'; exit; end;
else begin result:='0'; exit; end;
end;
end;
function CheckDigit(ch:char):boolean;
begin
case ch of
'0':result:=true;
'1':result:=true;
'2':result:=true;
'3':result:=true;
'4':result:=true;
'5':result:=true;
'6':result:=true;
'7':result:=true
else result:=false;
end;
end;
procedure TForm1.btn1Click(Sender: TObject);
var
i:word;
s,st,st1,outst:string;
symbol:char;
begin
for i := 0 to Form1.mmo1.Lines.Count-1 do
s:=s+Form1.Mmo1.Lines[i];
i:=1;
st:='1';
outst:='1';
while i<Length(s) do begin
symbol:=s[i];
inc(i);
if symbol='x' then begin
symbol:=s[i];
if CheckDigit(symbol) then begin
st:=NextState(symbol,st);
outst:=outst+' '+st;
end
else begin
Form1.mmo2.Lines.Add('Ошибка на символе '+ symbol);
break;
end;
end
else begin
Form1.mmo2.Lines.Add('Ошибка на символе '+ symbol);
break;
end;
inc(i);
if st='0' then begin
Form1.mmo2.Lines.Add('Ошибка на символе '+ symbol);
break;
end;
end;
if st='11' then begin
Form1.mmo2.Lines.Add('Правильная строка');
Form1.mmo2.Lines.Add('Состояния: '+ outst)
end
else Form1.mmo2.Lines.Add('Незаконченная строка')
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
Form1.mmo1.Lines.Clear;
Form1.mmo2.Lines.Clear;
end;
end.
Результат расчета.
Результат программы, реализующей распознающий автомат представлен на рисунке 3 «Результат программы».
Рис.3. Результат программы
Размещено на Allbest.ru
...Подобные документы
Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем.
дипломная работа [1,8 M], добавлен 18.08.2013Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа.
курсовая работа [615,1 K], добавлен 19.06.2012Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.
курсовая работа [903,9 K], добавлен 14.07.2012Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Методика минимизации абстрактного автомата. Порядок построения графа полученного минимизированного автомата. Синтез на элементах ИЛИ-НЕ и Т-тригерах. Составление таблицы переходов. Разработка микропрограммного автомата, реализующего микропрограмму.
курсовая работа [997,7 K], добавлен 28.03.2011Составление формальной грамматики, недетерминированный конечный автомат. Построение конечного автомата, программное моделирование работы конечного автомата. Граф детерминированного автомата, Синтаксическая диаграмма. Блок-схемы, примеры разбора строк.
курсовая работа [486,2 K], добавлен 19.11.2010Устройство управления и синхронизации в структуре микропроцессора. Порядок синтеза конечного автомата (КА) для устройства управления ЭВМ. Алгоритм функционирования КА, заданный с помощью графа, функции переходов. Состояние триггеров в микросхеме.
методичка [1019,0 K], добавлен 28.04.2009Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Разработка функциональной схемы управляющего микропрограммного автомата. Построение графов автомата для модели Мили и Мура. Кодирование состояний для модели Мура на D-триггерах. Алгоритм умножения чисел в дополнительном коде с простой коррекцией.
курсовая работа [764,0 K], добавлен 27.08.2012Понятие, последовательность построения и схемная реализация цифрового автомата. Описание форм представления функций алгебры логики. Принципы минимизации функций выходов и переходов автомата, их перевода в базис. Сведенья о программе Electronics Workbench.
курсовая работа [2,0 M], добавлен 27.10.2010Общая структура и принцип функционирования синхронного управляющего автомата. Анализ граф схемы алгоритма управляющего автомата и детализация блока памяти. Структурный синтез логического преобразователя и разработка электрической функциональной схемы.
курсовая работа [222,6 K], добавлен 19.02.2013Синтез цифрового автомата с комбинационной частью на логических элементах. Реализация спроектированного автомата в виде иерархического блока со схемой замещения на библиотечных компонентах в режиме SPICE–проектов. Разработка абстрактных символов.
курсовая работа [831,2 K], добавлен 23.09.2013Содержание и особенности этапов синтеза дискретного автомата. Граф переходов-выходов автомата Мура, кодирование входных и выходных сигналов. Построение функциональной схемы автомата Мура на RS–триггерах и элементах И-НЕ в программе Electronic WorkBench.
курсовая работа [964,2 K], добавлен 20.07.2015Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Важный частный случай недетерминированного конечного автомата. Проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Составление формальной грамматики, блок-схемы и программы, моделирующей работу конечного автомата.
курсовая работа [210,8 K], добавлен 05.12.2013Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012Проект цифрового устройства для передачи сообщения через канал связи. Разработка задающего генератора, делителя частоты, преобразователя кода, согласующего устройства с каналом связи, схемы синхронизации и сброса, блока питания; оптимизация автомата.
курсовая работа [3,4 M], добавлен 05.02.2013Оптимізація схеми мікропрограмного автомата Мура за рахунок нестандартного подання кодів станів. Аналіз методів синтезу автомата та аналіз сучасного елементного базису. Використанні особливостей автомата для зменшення площини матричної схеми автомата.
презентация [357,0 K], добавлен 16.10.2013
