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

Содержание и основные этапы работы:

• построение праволинейной грамматики;

• построение автоматной грамматики по праволинейной;

• построение недетерминированного конечного автомата;

• сведение недетерминированного конечного автомата к детерминированному;

• минимизация числа состояний автомата;

• выполнение этапов 2-5 с использованием аппарата сетей Петри;

• размещение состояний автомата;

• структурный и логический синтез распознающего автомата в заданном базисе;

• реализация автомата.

1. Индивидуальное задание

Исходными данными для курсовой работы являются две таблицы – таб.1 и таб.2 – и правила вывода R, приведенные ниже.

В таб.1 первоначально записана лишь первая строка, содержащая перечисленные 18 символов с_i­. Во вторую строку s_i записываются первые 18 символов фамилии, имени и отчества с обязательными пробелами между фамилией и именем и именем и отчеством. Затем в третью строку заносим для каждого из 18 символов строки символ из алфавита {x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇,} в соответствии с таб.2.

Таблица 1.

с

с1

с2

с3

с4

с5

с6

с7

с8

с9

с10

с11

с12

с13

с14

с15

с16

с17

с18

si

Л

А

Г

У

Т

И

Н

_

Ю

Р

И

Й

_

В

И

Т

А

Л

xi

х0

х1

х4

х7

х5

х3

х7

х5

X3

х0

Х3

Х0

Х5

Х2

х3

Х5

Х1

Х0

Таблица 2 построена на основе подсчета появлений каждой буквы русского алфавита в фамилиях, именах и отчествах контингента студентов. Затем буквы были сформированы в восемь групп с таким расчетом, чтобы появление каждого из символов х₀-х₇ было равномерным.

Таблица 2.

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

х1

х5

х2

х4

х6

х6

х4

х3

х3

х0

х7

х0

х3

х7

х4

х5

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Э

Ю

Я

-

х0

х4

х5

х7

х2

х5

х1

х2

х2

х0

х6

х1

х1

х3

х7

х5

Наконец, задана формальная грамматика G=<V_t, V_n, S, R>, где V_t={c₁, …, c₁₈} – терминальный словарь; V_n={S, A, B, C, D, E, F} – нетерминальный словарь; S V_n – начальный символ грамматики; R – множество правил вывода, которые имеют следующий вид:

S → с₁ с₂ с₃A; S → с₁ с₄ с₅B; S → с₆C; S → с₇F; A → с₈D;

A → с₉; B → с₈E; B→ с₉; C → с₈E; C → с₉;

D → с₁₀S; D → с₁₁; E → с₁₀S; E → с₁₁;

F → с₁₂ с₁₃ с₁₄ с₁₅; F → с₁₆ с₁₃ с₁₄ с₁₅ F → с₁₇ с₁₈ с₁₅

Эта грамматика, являющаяся праволинейной, приводится к виду G’=<V’_t, V’_n, S, R’>, где V’_t={x₀, … ,x₇} – новый терминальный словарь; R’ – множество правил вывода, получаемых из заданных заменой символов из алфавита V’_t в соответствии с таб.1. В данном примере они имеют вид:

S = x₀ x₁ x₄ A | x₀ x₇ x₅ B | x₃ C | x₇ F

A = x₅ D | x₃

B = x₅ E | x₃

C = x₅ E | x₃

D = x₀ S | x₃

E = x₀ S | x₃

F = x₀ x₅ x₂ x₃ | x₅ x₅ x₂ x₃ | x₁ x₀ x₃

Здесь | - металингвистический символ (связка), читаемый как «ИЛИ». Мощность словаря = 8.

2. Переход от праволинейной грамматики к автоматной

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

S → x₀ S₁; S₁ → x₁ S₂; S₂ → x₄ A; S → x₀ S₃; S₃ → x₇ S₄; S₄ → x₅ B;

S → x₃ C; S → x₇ F; A → x₅ D; A → x₃; B → x₅ E; B → x₃; C → x₅ E; C → x₃;

D → x₀ S; D → x₃; E → x₀ S; E → x₃; F → x₀ F₁; F₁ → x₅ F₂; F₂ → x₂ F₃; F₃ → x₃;

F → x₅ F₄; F₄ → x₅ F₅; F₅ → x₂ F₆; F₆ → x₃; F → x₁ F₇; F₇ → x₀ F₈; F₈→ x₃

Таким образом, нетерминальный словарь теперь имеет вид:

V’’_n = <S, S₁, S_2, S_3, S₄, A, B, C, D, E, F, F₁, F_2, F_3, F_4, F_5, F₆, F_7, F₈>. Мощность словаря равна 19.