Синтез распознающего автомата

  • Вид работы:
    Курсовая работа (т)
  • Предмет:
    Информационное обеспечение, программирование
  • Язык:
    Русский
    ,
    Формат файла:
    MS Word
    206,68 Кб
  • Опубликовано:
    2012-07-13
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!

Синтез распознающего автомата

Федеральное агентство по образованию

ГОУ ВПО «Ижевский государственный технический университет»

факультет «Информатика и вычислительная техника»








ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе по дисциплине

«Теория языков программирования и методы трансляции»

на тему «Синтез распознающего автомата»

Выполнил

студент гр. 4-78-10 Протозанов Е.С.

Принял

д.т.н., профессор Сенилов М.А.




Ижевск 2011г.

ВВЕДЕНИЕ


Проектирование распознающего автомата и его программная реализация необходимы при построении узлов цифровых вычислительных машин, при создании компиляторов, лингвистических процессоров и лексических анализаторов в трансляторах.

Цель курсовой работы состоит в изучении и использовании различных способов задания языков грамматиками. В курсовой работе необходимо использовать построение распознающего автомата и сети Петри для задания языков. Построить модель конечного автомата, распознающего заданный язык, реализовать полученный автомат программно.

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

1.   ПОСТАНОВКА ЗАДАЧИ


Построить модель распознающего автомата на основе индивидуального задания

Для этого необходимо на основе формальной грамматики получить праволинейную грамматику, построить ее граф. По праволинейной грамматики построить автоматную. Затем построить недетерминированный распознающий автомат, задать таблицу переходов для него и изобразить граф переходов. Перейти от недетерминированного к полностью определенному детерминированному автомату. Задать таблицу переходов и изобразить граф переходов для полученного автомата. Минимизировать этот автомат. Задать таблицу переходов и граф переходов для минимального автомата.

Получить граф переходов минимального автомата по праволинейной грамматике используя сети Петри. Сравнить полученную автоматную сеть с графом минимального автомата.

Входными данными для автомата является цепочка из терминальных символов. На выходе автомата появляется состояние, отвергающее или допускающее входную цепочку.

Задана формальная грамматика

G = <Vt, Vn, S, P>

Где Vt = {C1, C2,…, C18} - терминальный словарь,

Vn = {S, A, B, C, D, E, F}- нетерминальный словарь,

S - начальный символ грамматики, S Vn,

P - множество правил вывода

Правила вывода имеют следующий вид:

S -> C1 C2 C3 A; S -> C1 C4 C5 B; S -> C6 C; S -> C7 F; A -> C8 D; A -> C9; B -> C8 E; B -> C9; C -> C8 E;

C -> C9; D -> C10 S; D -> C11; E -> C10 S; E -> C11; F -> C12 C13 C14 C15; F -> C16 C13 C14 C15; F -> C17 C18 C15.

 


2. ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ. ПОСТРОЕНИЕ ПРАВОЛИНЕЙНОЙ ГРАММАТИКИ


Индивидуальным заданием является грамматика G', порождаемая из заданной формальной грамматики G.

Грамматика G приводится к виду

G'=<V't, V'n, S, R'>

Где V't={x0, x1, … , x7} - новый терминальный словарь, получаемый из Vt заменой ci на xi в соответствии с таблицей 1.

Таблица 1

ci

c1

c2

c3

с4

c5

c6

c7

c8

c9

c10

c11

c12

c13

c14

c15

c16

c17

c18

si

П

Р

О

Т

О

З

А

Н

О

В

_

Е

В

Г

Е

Н

И

Й

xi

x5

x0

x4

x5

x4

x3

x1

x7

x4

x2

x5

x6

x2

x4

x6

x7

x3

x0

' - множество правил вывода, получаемых из множества R, путем замены символов алфавита Vt символами алфавита V't, в соответствии с таблицей 1. Таблица 1 заполняется следующим образом: во вторую строку таблицы 1 заносятся имя фамилия и отчество, с обязательными пробелами между ними.

Третья строка таблицы 1 заполняется в соответствии с таблицей 2.

Таблица 2

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

x1

х5

x2

x4

x6

x6

x4

x3

x3

x0

x7

x0

x3

x7

x4

x5

P

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Э

Ю

Я

_

x0

х4

x5

x7

x2

x5

x1

x2

x2

x0

x6

x1

x1

x3

x7

x5



В результате, множество правил вывода праволинейной грамматики G' имеет вид:

1) S -> x5 x0 x4 A; 2) S -> x5 x5 x4 B; 3) S -> x3 C; 4) S -> x1 F; 5) A -> x7 D; 6) A -> x4; 7) B -> x7 E; 8) B -> x4; 9) C -> x7 E;

10) C -> x4; 11) D -> x2 S; 12) D -> x5; 13) E -> x2 S; 14) E -> x5; 15) F -> x6 x2 x4 x6; 16) F -> x7 x2 x4 x6; 17) F -> x3 x0 x6;


Построим граф грамматики G' (рис. 1).

Граф грамматики G’

Рис. 1

3. ПОСТРОЕНИЕ АВТОМАТНОЙ ГРАММАТИКИ ПО ПРАВОЛИНЕЙНОЙ


Процедура перевода праволинейной грамматики в автоматную.

Праволинейная грамматика:

1) S -> x5 x0 x4 A; 2) S -> x5 x5 x4 B; 3) S -> x3 C; 4) S -> x1 F; 5) A -> x7 D; 6) A -> x4; 7) B -> x7 E; 8) B -> x4; 9) C -> x7 E;

10) C -> x4; 11) D -> x2 S; 12) D -> x5; 13) E -> x2 S; 14) E -> x5; 15) F -> x6 x2 x4 x6; 16) F -> x7 x2 x4 x6; 17) F -> x3 x0 x6;


Для получения автоматной грамматики, необходимо заменить правила, у которых в правой части перед нетерминальным символом стоит более чем один терминальный, несколькими правилами.

В результате замены правил, были получены следующие правила

1.1)   S -> x5 S1;

.2)     S1 -> x0 S2;

1.3)   S2 -> x4 A;

.1)     S -> x5 S3;

.2)     S3 -> x5 S4;

.3)     S4 -> x4 B;

.1)     A -> x4 A1;

.2)     A1 -> ɛ;

.1)     B -> x4 B1;

.2)     B1 -> ɛ;

.1)     C -> x4 C1;

.2)     C1 -> ɛ;

12.1) D -> x2 D1;

.2) D1 -> ɛ;

.1)     E -> x2 E1;

14.2) E1 -> ɛ;

15.1)   F -> x6 F1;

15.2) F1 -> x2 F2;

15.3) F2 -> x4 F3;

15.4) F3 -> x6 F4;

15.5) F4 -> ɛ;

16.1)   F -> x7 F5;

16.2) F5 -> x2 F5;

16.3) F6 -> x4 F6;

16.4) F7 -> x6 F8;

16.5) F8 -> ɛ;

17.1)   F -> x3 F9;

17.2) F9 -> x0 F10;

17.3) F10 -> x6 F11.

17.4) F11 -> ɛ;

В итоге получаем следующую автоматную грамматику

1.1)   S -> x5 S1;

.2)     S1 -> x0 S2;

.3)     S2 -> x4 A

.1)     S -> x5 S3

.2)     S3 -> x5 S4

.3)     S4 -> x4 B

)        S -> x3 C;

)        S -> x1 F;

)        A -> x7 D;

.1)     A -> x4 A1;

.2)     A1 -> ɛ;

)        B -> x7 E;

.1)     B -> x4 B1;

.2)     B1 -> ɛ;

)        C -> x7 E;

.1)     C -> x4 C1;

10.2) C1 -> ɛ;

)        D -> x2 S;

.1)     D -> x2 D1;

.2)     D1 -> ɛ;

)        E -> x2 S;

.1)     E -> x2 E1;

.2)     E1 -> ɛ;

.1)     F -> x6 F1;

.2)     F1 -> x2 F2;

.3)     F2 -> x4 F3;

.4) F3 -> x6 F4;

.5)     F4 -> ɛ;

.1)     F -> x7 F5;

.2)     F5 -> x2 F5;

.3)     F6 -> x4 F6;

.4)     F7 -> x6 F8;

.5)     F8 -> ɛ;

.1)     F -> x3 F9;

.2)     F9 -> x0 F10;

.3)     F10 -> x6 F11;

.4)     F11 -> ɛ;

 


4. ПОСТРОЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА


Процедуру построения недетерминированного автомата по автоматной грамматике:

1)   Входным множеством автомата будет терминальное множество грамматики;

2)      Множеством состояний автомата будет нетерминальное множество грамматики, а в качестве начального состояния будет выступать начальный нетерминальный символ грамматики - S;

)        По правилам 6.2, 8.2, 10.2, 12.2, 14.2, 15.5, 16.5, 17.4 состояния A1, B1, C1, D1, E1, F4, F8, F11 будут допускающими;

)        Для всех правил грамматики по правилу A ® xB вводим в автомате переход из состояния A в состояние B по входу x;

)        Чтобы получить полностью определенный автомат, вводим состояние ошибки - Err, и во все оставшиеся клетки записываем переход в состояние ошибки.

Результатом такого построения является недетерминированный автомат с одним начальным состоянием и с одним допускающим состоянием. Таблицей переходов полученного автомата является таблица 3.

Таблица 3 Таблица переходов недетерминированного автомата


x0

x1

x2

x3

x4

x5

x6

x7


S

Err

F

Err

C

Err

S1, S3

Err

Err

0

S1

S2

Err

Err

Err

Err

Err

Err

Err

0

S2

Err

Err

Err

Err

A

Err

Err

Err

0

S3

Err

Err

Err

Err

Err

S4

Err

Err

0

S4

Err

Err

Err

Err

B

Err

Err

Err

0

A

Err

Err

Err

Err

A1

Err

Err

D

0

A1

Err

Err

Err

Err

Err

Err

Err

Err

1

B

Err

Err

Err

Err

B1

Err

Err

E

0

B1

Err

Err

Err

Err

Err

Err

Err

Err

1

C

Err

Err

Err

Err

C1

Err

E

0

C1

Err

Err

Err

Err

Err

Err

Err

Err

1

D

Err

S

Err

Err

Err

D1

Err

Err

0

D1

Err

Err

Err

Err

Err

Err

Err

Err

1

E

Err

S

Err

Err

Err

E1

Err

Err

0

E1

Err

Err

Err

Err

Err

Err

Err

Err

1

F

Err

Err

Err

F9

Err

F5

F1

Err

0

F1

Err

Err

F2

Err

Err

Err

Err

Err

0

F2

Err

Err

Err

Err

F3

Err

Err

Err

0

F3

Err

Err

Err

Err

Err

Err

F4

Err

0

F4

Err

Err

Err

Err

Err

Err

Err

Err

1

F5

Err

Err

F6

Err

Err

Err

Err

Err

0

F6

Err

Err

Err

Err

F7

Err

Err

Err

0

F7

Err

Err

Err

Err

Err

Err

F8

Err

0

F8

Err

Err

Err

Err

Err

Err

Err

Err

1

F9

F10

Err

Err

Err

Err

Err

Err

Err

0

F10

Err

Err

Err

Err

Err

Err

Err

Err

0

F11

Err

Err

Err

Err

Err

Err

F11

Err

1

Err

Err

Err

Err

Err

Err

Err

Err

Err

0


Построим граф переходов недетерминированного автомата (рис. 2). Для облегчения читаемости графа не отображено состояние ошибки и переходы из всех состояний недетерминированного автомата в состояние ошибки по оставшимся входным символам.

Граф переходов недетерминированного автомата S

Рис. 2

 


5. СВЕДЕНИЕ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА К ДЕТЕРМИНИРОВАННОМУ


Для каждого недетерминированного конечного распознавателя существует эквивалентный детерминированный автомат, который допускает те же цепочки, что и недетерминированный.

Обозначения:

АН - недетерминированный автомат;

АД - эквивалентный ему, детерминированный автомат.

Процедура построения АД по АН:

. Пометить первую строку таблицы переходов для АД множеством начальных состояний автомата АН.

. По данному множеству состояний B, помечающему строку таблицы
переходов автомата АД, для которой переходы еще не выполнены, вычислить те состояния АН, которые могут быть достигнуты из B с помощью каждого входного символа и поместить полученное множество состояний в состояние ячейки для автомата АД.

. Для каждого нового множества, порожденного на шаге 2, посмотреть: имеется ли уже в АД строка, помеченная этим множеством, если нет, то создать новую строку и пометить ее этим множеством. Если множество уже использовалось как метка, то никаких действий не надо.

. Если в таблице АД есть строка, для которой еще не вычислены переходы, то вернуться назад и применить к этой строке шаг 2. Если все переходы вычислены, то переходим к шагу 5.

. Пометить строку как допускающее состояние АД, тогда и только тогда, когда она содержит допускающее состояние АН, иначе пометить как отвергающее.

Добавим состояние ошибки R и во всех пустых клетках запишем переход в состояние ошибки. Получим детерминированный автомат таблицей переходов которого является таблица 4.

Таблица 4 Таблица переходов детерминированного автомата


x0

x1

x2

x3

x4

x5

x6

x7


S

Err

F

Err

C

Err

{S1,S3}

Err

Err

0

{S1,S3}

S2

Err

Err

Err

Err

S4

Err

Err

0

S2

Err

Err

Err

Err

A

Err

Err

Err

0

S4

Err

Err

Err

Err

B

Err

Err

Err

0

A

Err

Err

Err

Err

A1

Err

Err

D

0

A1

Err

Err

Err

Err

Err

Err

Err

Err

1

B

Err

Err

Err

Err

B1

Err

Err

E

0

B1

Err

Err

Err

Err

Err

Err

Err

Err

1

C

Err

Err

Err

Err

C1

Err

Err

E

0

C1

Err

Err

Err

Err

Err

Err

Err

Err

1

D

Err

S

Err

Err

Err

D1

Err

Err

0

D1

Err

Err

Err

Err

Err

Err

Err

Err

1

E

Err

S

Err

Err

Err

E1

Err

Err

0

E1

Err

Err

Err

Err

Err

Err

Err

Err

1

F

Err

Err

F9

Err

F5

F1

Err

0

F1

Err

Err

F2

Err

Err

Err

Err

Err

0

F2

Err

Err

Err

Err

F3

Err

Err

Err

0

F3

Err

Err

Err

Err

Err

Err

F4

Err

0

F4

Err

Err

Err

Err

Err

Err

Err

Err

1

F5

Err

Err

F6

Err

Err

Err

Err

Err

0

F6

Err

Err

Err

Err

F7

Err

Err

Err

0

F7

Err

Err

Err

Err

Err

Err

F8

Err

0

F8

Err

Err

Err

Err

Err

Err

Err

Err

1

F9

F10

Err

Err

Err

Err

Err

Err

Err

0

F10

Err

Err

Err

Err

Err

Err

Err

Err

0

F11

Err

Err

Err

Err

Err

Err

F11

Err

1

Err

Err

Err

Err

Err

Err

Err

Err

Err

0


Построим граф переходов детерминированного автомата (рис. 3). Для облегчения читаемости графа не отображено состояние ошибки и переходы из всех состояний детерминированного автомата в состояние ошибки по оставшимся входным символам.

детерминированный автомат праволинейный грамматика

Граф переходов детерминированного автомата

Рис. 3

6. ПОСТРОЕНИЕ МИНИМАЛЬНОГО АВТОМАТА


Для получения минимального автомата воспользуемся методом разбиения. Метод разбиения заключается в разбиении множества состояний на непересекающиеся подмножества (блоки), такие, что неэквивалентные состояния попадают в разные блоки.

Условия эквивалентности состояний:

условие подобия: состояния S и T должны быть либо оба допускающими, либо оба отвергающими;

условие преемственности: для всех входных символов состояния S и T должны переходить в эквивалентные состояния, т.е. их преемники эквивалентны.

Сначала состояния разбиваются на 2 блока. Один содержит только допускающие, другой - отвергающие. Очевидно, никакое из состояний 1-го блока не эквивалентно ни одному состоянию второго блока, что следует из условия подобия. Затем происходит разбиение этих блоков на более мелкие по следующему алгоритму:

). Если под действием какого-либо входного символа какая-то часть состояний данного блока переходит в состояния из другого блока, что нарушает условие преемственности, то необходимо разбить данный блок на части так, чтобы не нарушалось в одном блоке условие преемственности.

). Необходимо повторять шаг 1 до тех пор, пока дальнейшее разбиение невозможно.

). За один раз можно разбить только один блок.

Обозначим {S1,S3} как {M}.

Поделим на группы допускающих, недопускающих состояний:

{{S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем {S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} по входу x4:

{{S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A, B, C}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем блок {S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} по входу x5:

{{S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем блок {S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err} по входу x5:

{{S, M, S2, S4, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10},

{D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем блок {S, M, S2, S4, F, F1, F2, F5, F6, F9, Err} по входу x7: {{S, M, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем блок {S, M, S2, S4, F, F1, F2, F5, F6, F9, Err} по входу x7:

{{S, M, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем блок {S, M, F, F1, F2, F5, F6, F9, Err} по входу x4:

{{S, M, F, F1, F5, F9, Err}, {A, B, C},{F2, F6}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем блок {S, M, F, F1, F5, F9, Err} по входу x2:

{{S, M, F, F9, Err}, {A, B, C}, {F2, F6}, {F1, F5}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Разобьем блок {S, M, F, F9, Err}, выделив начальное состояние и состояние ошибки:

{{S}, {M, F, F9}, {Err}, {A, B, C}, {F2, F6}, {F1, F5}, {F3, F7, F10}, {S2, S4}, {D, E}, {A1, B1, C1, D1, E1, F4, F8, F11}}.

Дальнейшее разбиение невозможно. Полученные блоки состояний можно использовать для построения нового автомата, который эквивалентен исходному, и не содержит эквивалентных состояний. Для построения нового автомата, произведем замену обозначений блоков:

{S}                                                   ->    A

{M}                                        ->    B

{F}                                          ->    C

{F9}                                        ->    D

{F2, F6}                                          ->    E

{F1, F5}                                 ->    F

{S2,S4}                                           ->    G

{D, E}                                              ->    H

{A,B,C}                                           ->    I

{F3, F7, F10}                                  ->    J

{A1, B1, C1, D1, E1, F4, F8, F11} ->    K

{Err}                                       ->    L

В соответствии с этими обозначениями мы получаем минимальный автомат, таблица переходов которого представлена таблицей 5.

Таблица 5 Таблица переходов минимального автомата


x0

x1

x2

x3

x4

x5

x6

x7


A

L

С

L

I

L

B

L

L

0

B

G

L

L

L

L

G

L

L

0

C

L

L

L

D

L

F

F

L

0

D

J

L

L

L

L

L

L

L

0

E

L

L

L

L

J

L

L

L

0

F

L

L

E

L

L

L

L

L

0

G

L

L

L

L

I

L

L

L

0

H

L

A

L

L

L

K

L

L

0

I

L

L

L

L

K

L

L

H

0

J

L

L

L

L

L

L

K

L

0

K

L

L

L

L

L

L

L

L

1

L

L

L

L

L

L

L

L

L

0

Граф переходов минимального автомата построен на рис. 4. Для облегчения читаемости, на рисунке не изображено состояние L и ведущие к нему переходы.

Рис. 4

 


7. ПОСТРОЕНИЕ СЕТИ ПЕТРИ


Построим для грамматики G' сеть Петри. Для этого, поставим в соответствие нетерминальным символам позиции (кружки) сети. А терминалам - переходы (планки) сети. Пометим позиции и переходы соответствующими нетерминалами и терминалами.

Позиции соединяются дугами только через переходы, а переходы - через позиции. Если в правой части некоторого правило вывода из R’ имеет место конкатенация терминалов, то в сети Петри между переходами, помеченными терминалами, должны появляться дополнительные позиции, которые можно помечать символами левой части правил вывода с индексами 1, 2, … .

Таким образом, позиции могут иметь несколько входящих и исходящих дуг, но переходы - в точности по одной входящей и не более чем одной исходящей дуге (исходящая дуга может отсутствовать, если в правой части правила вывода отсутствует замыкающий нетерминал).

Выполнив эти действия, получаем сеть Петри (рис. 5).

Сеть Петри

Рис. 5

Для полноты соответствия построенной сети Петри распознающему автомату Мура, введем не показанную на рис. 5 заключительную позицию Z, в которую направим дуги из всех переходов, ранее не имевших исходящих дуг. В результате получим новую сеть Петри (рис. 6).

Сеть Петри с заключительной позицией Z

Рис. 6

Далее, необходимо минимизировать сеть Петри. Для этого определим в ней идентичные фрагменты. Итак, идентичными фрагментами являются позиции D и E c инцидентными им переходами x5 и x4. Также, позиции A, B и С с инцидентными им переходами x4 и x7. Позиции S1 и S3, F2 и F5, F3 и F6, F1 и F4, F6 и F8 можно склеить попарно. В результате получаем минимизированную недетерминированную сеть Петри (рис. 7).

Минимизированная сеть Петри

Рис. 7

Этот этап соответствует минимизации числа состояний автомата, но он выполнен для автомата, сохраняющего недетерминированность. Источником недетерминированности, очевидно, могут являться лишь позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами.

Недетерминированность устраняется склеиванием двух позиций Pl и Pk в одну (Pl, Pk). При этом позиции (Pl, Pk) инцидентны все исходящие дуги, являющиеся исходящими дугами позиций Pl и Pk.

В полученной сети Петри отсутствуют позиции свободного выбора, исходящие дуги которых являются входящими дугами переходов, помеченных одинаковыми терминалами. А значит, сеть Петри (рис. 7) уже детерминирована и минимизирована.

Теперь обозначим позиции сети Петри следующими буквами:

S -> A S1,S3 -> B F -> C F7 -> D F2, F5 -> E F1,F4 -> F

S2,S4 -> G D,E -> H A,B,C -> I F3,F6,F8 -> J Z -> K


Уберем переходы из сети Петри, дуги подпишем терминалами переходов, тогда получим граф переходов (рис.8).

Граф переходов полученный из сети Петри

Рис.8

Сравнив полученный граф (рис.8) с графом минимального автомата (рис. 4) мы видим, что они идентичны. Значит, минимальный автомат построен правильно.

8. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ РАСПОЗНАЮЩИЙ АВТОМАТ

 

8.1 Вводная часть


Программа: машина Тьюринга

Обозначение программы: turing.exe

Программа используется для построения моделей машины Тьюринга

8.2 Функциональное назначение

Программа предназначена для моделирования работы машины Тьюринга. Программа обрабатывает цепочку входных символов согласно правилам грамматики, записанным в виде таблицы переходов, и устанавливает состояние, позволяющее определить допустимость цепочки.

8.3 Системные требования


1.   Операционная система семейства Windows, Linux или MacOS с графическим фреймворком Qt версии не менее 4.0

2.      Оперативная память не менее 32 мегабайт

.        10 мегабайт места на жестком диске

8.4 Описание входных данных


В настройках программы задается следующая информация:

1.   Таблица переходов конечного автомата

2.      Множество состояний машины

.        Множество входных символов

.        Пустой символ ленты

.        Конечные состояния машины

.        Допустимые состояния машины

На вход программе подается строка, символы которой входят в множество входных символов машины. Строка проверяется на корректность и вводит в программу только содержащиеся во входном множестве символы.

Для допуска строки вводится дополнительное состояние, не являющеся состоянием минимального автомата, но требуемое для окончания работы машины Тьюринга с допускающим результатом.

 


9. ОПИСАНИЕ КОНТРОЛЬНОГО ПРИМЕРА

 

9.1 Назначение


Контрольный пример необходим для тестирования программной реализации автомата - программы «turing».

9.2 Исходные данные


Входная цепочка символов автомата. Цепочки символов состоят из символов входного алфавита автомата

{x0, x1, x2, x3, x4, x5, x6, x7}

Построим цепочки символов, для контрольного примера, исходя из праволинейной грамматики.

Что бы получить допустимую цепочку символов необходимо взять одно из правил, в левой части которого стоит начальный символ S.

Выписать все терминальные символы из этого правила и если в конце стоит нетерминал, то перейти к одному из правил, в левой части которого стоит этот нетерминал.

Выписать терминальные символы из этого правила и если в конце стоит нетериманл, то перейти к новому правилу и т.д., пока мы не дойдем до правила, правая часть которого кончается терминалом.

Итак, получаем допускающие цепочки:

1)   S -> x5 x5 x4 B -> x4 - допустить

      2                   8

отсюда получаем цепочку: x5 x5 x4 x4;

2)   S -> x3 C -> x7 E -> x5 - допустить

      3          9        14

цепочка: x3 x7 x5;

3)   S -> x1 F -> x3 x0 x6 - допустить

      4        17

цепочка: x1 x3 x0 x6;

Для полной проверки автомата получим несколько недопустимых цепочек. Их можно получить, если выписывать терминалы, не доходя до терминала, который стоит последним в правиле.

Или же если записать терминал, которого нету в правой части ни одного из правил, в левой части которых стоит необходимый нетерминал.

Недопустимые цепочки:

4)  x5 x5 x4

5)      x3 x7

)        x1 x3 x0

9.4 Результаты испытания программы


Результаты испытания программы представлены в таблице 6.

Таблица 6 Результат испытания программы

Номер тестируемой цепочки

Входная цепочка

Результат работы программы

1

x5 x5 x4 x4

цепочка допущена

2

x3 x7 x5

цепочка допущена

3

x1 x3 x0 x6

цепочка допущена

6

x5 x5 x4

цепочка отвергнута

7

x3 x7

цепочка отвергнута

8

x1 x3 x0

цепочка отвергнута


Результаты испытания программы совпали с ожидаемыми, что говорит о правильности построения минимального автомата и реализации программы.

 

ЗАКЛЮЧЕНИЕ


В ходе данной работы было выполнено построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Автоматы, полученные двумя способами, идентичны, что говорит о правильности выполнения вычислений.

Для автоматизированной обработки входных последовательностей была реализована машина Тьюринга с устанавливаемым автоматом. Проверка теоретически построенных допустимых и недопустимых последовательностей показала, что программа работает верно.

 

Список литературы


1. Методические указания для самостоятельной работы студентов по  дисциплине "Теория вычислительных процессов и структур". Ч1/ Ижевск. гос. техн. университет; Сост. Сенилов М.А. ИжГТУ, 2000.

2. ГОСТ 19.005 - 78. Общие требования к программным документам // Единая система программной документации. - М.: Издательство стандартов, 1980. - 2с.

ПРИЛОЖЕНИЕ 1

 

Текст программы


1.      Заголосочный файл mainwindow.cpp

#ifndef MAINWINDOW_H

#define MAINWINDOW_H

#include <QMainWindow>

#include <QSet>

#include <QList>

#include <QTimer>

Ui {MainWindow;

}

MainWindow : public QMainWindow

{_OBJECT

:MainWindow(QWidget *parent = 0);

~MainWindow();

:isStopState(const QChar c);isAllowedState(const QChar c);getMeaningByState(const QChar c);writeSymbol(QChar c);moveRight();moveLeft();::MainWindow *ui;<QChar> stateSet;<QChar> symbolsSet;<QChar> endStateSet;<QChar> allowedStateSet;<QChar> ribbon;ribbonPos, fakePos;currentX, currentY;currentState;timer;running;ready;

slots:step();resetState();setRules();on_buttonSetStates_clicked();on_load_triggered();on_save_triggered();on_buttonSetString_clicked();

on_ruleTable_cellPressed(int row, int column);

on_comboWriteSymbol_currentIndexChanged(int index);

on_comboMoveTo_currentIndexChanged(int index);on_comboSetState_currentIndexChanged(int index);

on_comboSpaceSymbol_currentIndexChanged(int index);

on_buttonStep_clicked();

on_buttonStartStop_clicked();

on_horizontalSlider_sliderMoved(int position);

on_buttonReset_clicked();

on_lineEndState_editingFinished();

on_lineAllowedState_editingFinished();

on_pushButton_clicked();

on_about_triggered();

on_about_Qt_triggered();

:stateChanged();

};

#endif // MAINWINDOW_H

2.      Заголовочный файл visualization.h

#ifndef VISUALISATION_H

#define VISUALISATION_H

#include <QWidget>

visualisation : public QWidget

{_OBJECT:visualisation(QWidget *parent = 0);setRibbon(QList<QChar> *r);setSpaceSymbol(QChar c);setFakePos(int *pos);setRealPos(int *pos);setState(QChar *c);setResultText(const QString str);

:<QChar> *ribbon;resultText;spaceSymbol, *state;*fakePos, *realPos;:

slots:

:paintEvent(QPaintEvent *);

};

#endif // VISUALISATION_H

3.      Реализация mainwindow.cpp

#include <QFile>

#include <QFileDialog>

#include <QDebug>

#include <QMessageBox>

#include "mainwindow.h"

#include "ui_mainwindow.h"

::MainWindow(QWidget *parent) :(parent),(new Ui::MainWindow)

{>setupUi(this);>comboMoveTo->addItem(trUtf8("Влево"));>comboMoveTo->addItem(trUtf8("Стоять"));>comboMoveTo->addItem(trUtf8("Вправо"));= 0;= 0;(this, SIGNAL(stateChanged()), ui->widget, SLOT(repaint()));(&timer, SIGNAL(timeout()), this, SLOT(step()));>widget->setRibbon(&ribbon);>widget->setFakePos(&fakePos);>widget->setRealPos(&ribbonPos);>widget->setState(&currentState);= 0;= 0;= false;= false;

}

::~MainWindow()

{ui;

}

MainWindow::isStopState(const QChar c)

{endStateSet.contains(c);

}

MainWindow::writeSymbol(const QChar c)

{.insert(ribbonPos, c);.removeAt(ribbonPos + 1);stateChanged();

}

MainWindow::moveRight()

{++;(ribbonPos == ribbon.count() - 1).append(ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0));++;stateChanged();

}

MainWindow::moveLeft()

{-;(ribbonPos > 0)-;.prepend(ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0));stateChanged();

}

MainWindow::step()

{>widget->setResultText(QString(""));(!isStopState(currentState) && ready)

{logString;+= trUtf8("Входной символ '");i = 0, j = 0;in;(ribbon.count() != 0)= ribbon.at(ribbonPos);= ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0); += in + trUtf8("', устанавливается состояние '");

QString inSymbol = ui->ruleTable->horizontalHeaderItem(i)->text();(in != inSymbol && i < ui->ruleTable->columnCount())

{++;= ui->ruleTable->horizontalHeaderItem(i)->text();

}

state = ui->ruleTable->verticalHeaderItem(j)->text();(state != currentState && j < ui->ruleTable->rowCount())

{++;= ui->ruleTable->verticalHeaderItem(j)->text();

}asd = ui->ruleTable->item(j, i)->text().at(2); += asd + trUtf8("', записывается символ '");

currentState = asd;>writeSymbol(ui->ruleTable->item(j, i)->text().at(0));+= ui->ruleTable->item(j, i)->text().at(0);+= trUtf8("', каретка ");

(ui->ruleTable->item(j, i)->text().at(1) == QString("L").at(0))

{>moveLeft();+= trUtf8("движется влево");

}if (ui->ruleTable->item(j, i)->text().at(1) == QString("R").at(0))

{>moveRight();+= trUtf8("движется вправо");

}+= trUtf8("стоит на месте");>logWidget->addItem(logString);

}

{= false;>buttonStartStop->setText(trUtf8("Старт"));.stop();

}(isStopState(currentState))

{= false;>logWidget->addItem(QString(trUtf8("Достигли конечного состояния; остановка")));(isAllowedState(currentState))>widget->setResultText(this->getMeaningByState(currentState));>widget->setResultText(trUtf8("Состояние недопустимо"));

}

}

MainWindow::resetState()

{>logWidget->clear();(ready)

{= 0;= 0;= ui->comboBaseState->itemText(ui->comboBaseState->currentIndex()).at(0);stateChanged();

}

}

MainWindow::on_buttonSetStates_clicked()

{.clear();.clear();.clear();(int i = 0; i < ui->lineStateSymbols->text().length(); i++)+= ui->lineStateSymbols->text().at(i);

.clear();(int i = 0; i < ui->lineInputSymbols->text().length(); i++)+= ui->lineInputSymbols->text().at(i);

<QChar> stateList = stateSet.toList();<QChar> symbolsList = symbolsSet.toList();(stateList);(symbolsList);

>ruleTable->clear();>meaningsTable->clear();>ruleTable->setRowCount(stateSet.count());>ruleTable->setColumnCount(symbolsSet.count());>meaningsTable->setRowCount(stateSet.count());>meaningsTable->setColumnCount(1);

>ruleTable->setItem(0,0, new QTableWidgetItem);str = "";>meaningsTable->clear();>comboSetState->clear();>comboBaseState->clear();(int i = 0; i < stateList.length(); i++)

{>ruleTable->setVerticalHeaderItem(i, new QTableWidgetItem(QString(stateList.at(i))));>meaningsTable->setVerticalHeaderItem(i, new QTableWidgetItem(QString(stateList.at(i))));+= stateList.at(i);>comboSetState->addItem(stateList.at(i));>comboBaseState->addItem(stateList.at(i));

}>lineStateSymbols->setText(str);

= "";>comboWriteSymbol->clear();>comboSpaceSymbol->clear();(int i = 0; i < symbolsList.length(); i++)

{>ruleTable->setHorizontalHeaderItem(i, new QTableWidgetItem(QString(symbolsList.at(i))));+= symbolsList.at(i);>comboWriteSymbol->addItem(symbolsList.at(i));>comboSpaceSymbol->addItem(symbolsList.at(i));

}>lineInputSymbols->setText(str);

(int i = 0; i < ui->ruleTable->rowCount(); i++)(int j = 0; j < ui->ruleTable->columnCount(); j++)>ruleTable->setItem(i,j, new QTableWidgetItem);

(int i = 0; i < ui->ruleTable->rowCount(); i++)(int j = 0; j < ui->ruleTable->columnCount(); j++)

{asd = " ";[0] = ui->ruleTable->horizontalHeaderItem(j)->text().at(0);[1] = QString("R").at(0);[2] = ui->ruleTable->verticalHeaderItem(i)->text().at(0);>ruleTable->item(i, j)->setText(asd);

}= true;>resetState();

}

MainWindow::on_load_triggered()

{fileName = QFileDialog::getOpenFileName(this, trUtf8("Загрузить таблицу"),

"",("Таблицы правил (*.tbl)"));file( fileName );( !file.open( QIODevice::ReadOnly ) );

stream( &file );.setVersion( QDataStream::Qt_4_2 );

>ruleTable->clear();.clear();.clear();rows, columns, posa, posc;>> rows;>> columns;>> stateSet;>> symbolsSet;>> posa;>> posc;>> endStateSet;>> allowedStateSet;

>ruleTable->setRowCount(rows);>ruleTable->setColumnCount(columns);

str;(int i = -1; i < rows; i++)(int j = -1; j < columns; j++)

{>> str;(i > -1 && j > -1)

{>ruleTable->setItem(i, j, new QTableWidgetItem);>ruleTable->item(i, j)->setText(str);

}

{(i == -1 && j > -1)

{>ruleTable->setHorizontalHeaderItem(j, new QTableWidgetItem(str));

}(j == -1 && i > -1)

{>ruleTable->setVerticalHeaderItem(i, new QTableWidgetItem(str));

}

}

}

= "";>comboSetState->clear();>comboBaseState->clear();>meaningsTable->clear();>meaningsTable->setRowCount(stateSet.count());>meaningsTable->setColumnCount(1);

<QChar> endStateList = endStateSet.toList();<QChar> allowedStateList = allowedStateSet.toList();<QChar> stateList = stateSet.toList();

= "";(endStateList);(int i = 0; i < endStateList.length(); i++)

{+= endStateList.at(i);>lineEndState->setText(str);

}

= "";(allowedStateList);(int i = 0; i < allowedStateList.length(); i++)

{+= allowedStateList.at(i);>lineAllowedState->setText(str);

}

= "";(stateList);(int i = 0; i < stateList.length(); i++)

{+= stateList.at(i);>comboSetState->addItem(stateList.at(i));>comboBaseState->addItem(stateList.at(i));>meaningsTable->setVerticalHeaderItem(i, new

QTableWidgetItem(stateList.at(i)));>meaningsTable->setItem(i, 0, new QTableWidgetItem);asd;>> asd;>meaningsTable->item(i, 0)->setText(asd);

}>comboBaseState->setCurrentIndex(posa);>lineStateSymbols->setText(str);

= "";>comboWriteSymbol->clear();>comboSpaceSymbol->clear();

<QChar> symbolsList = symbolsSet.toList();(symbolsList);(int i = 0; i < symbolsList.length(); i++)

{+= symbolsList.at(i);>comboWriteSymbol->addItem(symbolsList.at(i));>comboSpaceSymbol->addItem(symbolsList.at(i));

}>comboSpaceSymbol->setCurrentIndex(posc);>lineInputSymbols->setText(str);= true;>resetState();

}

MainWindow::on_save_triggered()

{fileName = QFileDialog::getSaveFileName(this,

trUtf8("Сохранить таблицу"),

"",("Таблицы правил (*.tbl)"));file( fileName );( !file.open( QIODevice::WriteOnly ) );

stream( &file );.setVersion( QDataStream::Qt_4_2 );

rows = ui->ruleTable->rowCount();columns = ui->ruleTable->columnCount();<< rows << columns;<< stateSet << symbolsSet;<< ui->comboBaseState->currentIndex() << ui-

>comboSpaceSymbol->currentIndex();<< endStateSet << allowedStateSet;str;(int i = -1; i < rows; i++)(int j = -1; j < columns; j++)

{(i > -1 && j > -1)

{= ui->ruleTable->item(i, j)->text();<< str;

}

{(i == -1 && j > -1)

{= ui->ruleTable->horizontalHeaderItem(j)->text();<< str;

}(j == -1 && i > -1)

{= ui->ruleTable->verticalHeaderItem(i)->text();<< str;

}(i == -1 && j == -1)

{= "";<< str;

}

}

}

(int i = 0; i < ui->meaningsTable->rowCount(); i++)<< ui->meaningsTable->item(i, 0)->text();

}

MainWindow::on_buttonSetString_clicked()

{.clear();(int i = 0; i < ui->lineInputString->text().length(); i++)

{(symbolsSet.contains(ui->lineInputString->text().at(i)))

{.append(ui->lineInputString->text().at(i));

}

}>resetState();>widget->setResultText(QString(""));stateChanged();

}

MainWindow::on_ruleTable_cellPressed(int row, int column)

{= row;= column;inSymbol = ui->ruleTable->horizontalHeaderItem(column)->text().at(0);curState = ui->ruleTable->verticalHeaderItem(row)->text().at(0);ruleSym = ui->ruleTable->item(row, column)->text().at(0);ruleState = ui->ruleTable->item(row, column)->text().at(2);>currentInputSymbol->setText(inSymbol);>currentMachineState->setText(curState);

(int i = 0; i < ui->comboWriteSymbol->count(); i++)(ruleSym == ui->comboWriteSymbol->itemText(i).at(0))>comboWriteSymbol->setCurrentIndex(i);

(int i = 0; i < ui->comboSetState->count(); i++)(ruleState == ui->comboSetState->itemText(i).at(0))>comboSetState->setCurrentIndex(i);

(ui->ruleTable->item(row, column)->text().at(1) == QString("L").at(0))

{>comboMoveTo->setCurrentIndex(0);

}

{(ui->ruleTable->item(row, column)->text().at(1) == QString("R").at(0))>comboMoveTo->setCurrentIndex(2);>comboMoveTo->setCurrentIndex(1);

}

}

MainWindow::setRules()

{(ui->comboWriteSymbol->count() != 0 && ui->comboSetState->count() != 0)

{result = " ";[0] = ui->comboWriteSymbol->itemText(ui->comboWriteSymbol->currentIndex()).at(0);[2] = ui->comboSetState->itemText(ui->comboSetState->currentIndex()).at(0);(ui->comboMoveTo->currentIndex() == 0)[1] = QString("L").at(0);if (ui->comboMoveTo->currentIndex() == 2)[1] = QString("R").at(0);[1] = QString("H").at(0);

>ruleTable->item(currentX, currentY)->setText(result);

}

}

MainWindow::on_comboWriteSymbol_currentIndexChanged(int index)

{

}

MainWindow::on_comboMoveTo_currentIndexChanged(int index)

{

}

MainWindow::on_comboSetState_currentIndexChanged(int index)

{

}

MainWindow::on_comboSpaceSymbol_currentIndexChanged(int index)

{(index != -1)>widget->setSpaceSymbol(ui->comboSpaceSymbol->itemText(ui->comboSpaceSymbol->currentIndex()).at(0));

}

MainWindow::on_buttonStep_clicked()

{>step();

}

MainWindow::on_buttonStartStop_clicked()

{(ready)

{(running)

{= false;.stop();>buttonStartStop->setText(trUtf8("Старт"));

}

{= true;.start();>buttonStartStop->setText(trUtf8("Стоп"));

}

}

}

MainWindow::on_horizontalSlider_sliderMoved(int position)

{.setInterval(position);

}MainWindow::on_buttonReset_clicked()

{= 0;= 0;>widget->setResultText(QString(""));= ui->comboBaseState->itemText(ui->comboBaseState->currentIndex()).at(0);stateChanged();

}

MainWindow::on_lineEndState_editingFinished()

{.clear();str;(int i = 0; i < ui->lineEndState->text().length(); i++)

{(stateSet.contains(ui->lineEndState->text().at(i)))

{+= ui->lineEndState->text().at(i);+= ui->lineEndState->text().at(i);

}

}>lineEndState->setText(str);

}

MainWindow::isAllowedState(const QChar c)

{allowedStateSet.contains(c);

}

MainWindow::getMeaningByState(const QChar c)

{(int i = 0; i < ui->meaningsTable->rowCount(); i++)

{(ui->meaningsTable->verticalHeaderItem(i)->text().at(0) == c)

{str = ui->meaningsTable->item(i, 0)->text();str;

}

}

}

MainWindow::on_lineAllowedState_editingFinished()

{.clear();(int i = 0; i < ui->lineAllowedState->text().length(); i++)

{(stateSet.contains(ui->lineAllowedState->text().at(i)))

{+= ui->lineAllowedState->text().at(i);

}

}

}

MainWindow::on_pushButton_clicked()

{>setRules();

}

MainWindow::on_about_triggered()

{*box = new QMessageBox;>setIconPixmap(QPixmap::fromImage(QImage(":/images/about.png")));>setText(QString(trUtf8("Автор: Протозанов Евгений\nИжГТУ 4-78-10 2012")));>setWindowTitle(QString(trUtf8("Машина Тьюринга")));>show();

}

MainWindow::on_about_Qt_triggered()

{::aboutQt(this, trUtf8("О Qt"));

}

4.      Реализация visualization.cpp

#include <QPainter>

#include <QBrush>

#include <QPen>

#include <cmath>

#include "visualisation.h"

::visualisation(QWidget *parent) :(parent)

{

}

visualisation::paintEvent(QPaintEvent *)

{spacerX = (this->width() - 620)/2;spacerY = (this->height() - 100)/2;*painter = new QPainter();>begin(this);>save();>setRenderHint(QPainter::Antialiasing);>setFont(QFont("", 14));

//=======================================mid = 15*floor(*fakePos/15);real_mid = *realPos - (*fakePos - mid);start = real_mid - 15;end = real_mid + 15;x = -300;(int i = start; i <= end; i++)

{c;(i < 0 || i >= ribbon->count())= spaceSymbol;= ribbon->at(i);>setPen(QPen(QColor(Qt::black)));>drawText(300 + x + spacerX, 60 + spacerY, 20, 20, Qt::AlignCenter, c);>drawRect(300 + x + spacerX, 60 + spacerY, 20, 25);+= 20;

}>setBrush(QBrush(QColor(Qt::black)));>drawPie(300 + 20*(*fakePos - mid) + spacerX, 80 + spacerY, 20, 20, 240 * 16, 60 * 16);>drawText(0, 30 + spacerY, this->width(), 20, Qt::AlignCenter, resultText);

>drawRect(300 + spacerX, spacerY, 20, 25);>setPen(QPen(QColor(Qt::white)));>drawText(300 + spacerX, 2 + spacerY, 20, 20, Qt::AlignCenter, *state);

//=======================================>restore();>end();

}

visualisation::setRibbon(QList<QChar> *r)

{= r;

}

visualisation::setSpaceSymbol(QChar c)

{= c;

}

visualisation::setFakePos(int *pos)

{= pos;

}

visualisation::setRealPos(int *pos)

{= pos;

}visualisation::setState(QChar *c)

{= c;

}

visualisation::setResultText(const QString str)

{

resultText = str;

}

ПРИЛОЖЕНИЕ 2

 

Результаты расчета на ЭВМ контрольного примера


Ввод последовательности символов



Результат обработки входной строки

Похожие работы на - Синтез распознающего автомата

 

Не нашли материал для своей работы?
Поможем написать уникальную работу
Без плагиата!