Сведение недетерминированного автомата к детерминированному.

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

Исходными заданиями для курсовой работы являются две таблицы - табл. 1 и

2-й правила вывода R, приведенные ниже.

В табл. 1 в первую строку записывается перечисление 18 Символов С_i, во

вторую строку записываются первые 18 символов фамилии, имени и отчества

студента, а в третью - заносится для каждого из 18 символов строки символ

из алфавита {х_1, х₂, х₃, х₄, х₅, х₆, х₇} в соответствии с табл. 2.

Таблица 1

c_i

C₁

C₂

C₃

C₄

C₅

C₆

C₇

C₈

C₉

C₁₀

C₁₁

C₁₂

C₁₃

C₁₄

C₁₅

C₁₆

C₁₇

C₁₈

s_i

x_i

Таблица 2

X₁

X₅

X₂

X₄

X₆

X₄

X₃

X₀

X₇

X₀

X₃

X₇

X₄

X₅

X₀

X₄

X₅

X₇

X₂

X₅

X₁

X₂

X₀

X₆

X₁

X₃

X₇

X₅

Для курсовой работы задана формальная грамматика G=(V_t, V_n, S, R), где V_t={c₁, c₂, c₃, ... , c₈} - терминальный словарь; V_n= {S,A,B,C,D,E,F } - нетерминальный словарь; S, принадлежащее множеству V_n - начальный символ грамматики; R - множество правил вывода, которые имеют следующий вид:

Sc₁c₂ c₃A; Sc₁c₄ c₅B; Sc₆C; Sc₇F; Ac₈D; Ac₉;

Bc₈E; Bc₉; Cc₈E; Cc₉; Dc₁₀S; Dc₁₁; Ec₁₀S;

Ec₁₁; Fc₁₂c₁₃ c₁₄c₁₅; Fc₁₆c₁₃ c₁₄c₁₅; Fc₁₇c₁₈ c₁₅;

Эта грамматика, являющаяся праволинейной, приводится к виду

G’=(V’t,V’_n, S, R’), где V’_t={x₀, x_1,х₂, ... , х₇} - новый терминальный словарь;

R' - множество правил вывода, получаемых из заданных заменой символов

из алфавита V_t символами из алфавита V’_t в соответствии с табл. 1.

В данном примере они имеют вид

Dx₀S | x₄; Ex₀S | x₄; Fx₆x₀ x₅ x₂ | x₀x₀ x₅ x₂ | x₁x₂x₂

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

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

Этот этап выполняется путем расширения нетерминального словаря способом, вытекающим из возможности преобразования праволинейной грамматики в автоматную G’’=(V_t’, V_n’’, S, R’’). Для рассматриваемого примера получим множество R’’ правил вывода:

Sx₄S₁; S₁x₀S₂; S₂x₁A; Sx₄S₃; S₃x₇S₄; S₄x₇B; Sx₄C; Sx₅F;

Ax₄D; Ax₆; Bx₄E; Bx₆; Cx₄E; Cx₆; Dx₀S; Dx₄;

Ex₀S; Ex₄; Fx₆F₁; F₁x₀F₂; F₂x₅F₃; F₃x₂; Fx₀F₄; F₄x₀F₅;

F₅x₅F₆; F₆x₂; Fx₁F₇; F₇x₂F₈; F₈x₂

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

V_n’’ = {S₁, S₂, S₃, S₄, А, В, С, D, E, F, F₁, F₂, F₃, F₄, F₅, F₆, F₇, F₈} и его

мощность | V_n | равна 19.

Построение недетерминированного конечного автомата.

Рассмотрим недетерминированный конечный распознающий автомат

A=(Q, х, , q₀, q_k), где Q - множество внутренних состояний; х - входной алфавит; - отображение :x*QP(Q); P(Q) - множество подмножеств из Q; q₀, принадлежащее Q - начальное состояние; q_k, принадлежащее Q - заключительное состояние, q_kq₀.

Этот автомат зададим следующим образом. Поставим в соответствие символам нетерминального словаря V_n’’ состояния из Q, в том числе нетерминалу S - начальное состояние q₀, и добавим заключительное состояние q_k, в котором автомат оказывается, если цепочка предъявляемых ему символов принадлежит L(G’’). Таким образом, мощность | Q | множества Q равна | Q | = | V_n’’ | +1=20.

В данном примере нетерминальным символам, указанным в строках 1 и 3 таблицы 3, соответствует состояния автомата, перечисленные в строках 2 и 4.

Таблица 3

S	S₁	S₂	S₃	S₄	A	B	C	D	E
q₀	q₁	q₂	q₃	q₄	q₅	q₆	q₇	q₈	q₉
F	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	-
q₁₀	q₁₁	q₁₂	q₁₃	q₁₄	q₁₅	q₁₆	q₁₇	q₁₈	q₁₉

Заключительное состояние обозначено через q₁₉.

Поставив правилам вывода в соответствие переходы автомата, получим таблицу переходов недетерминированного конечного автомата (табл. 4) и граф переходов (рис. 1).

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

Рисунок 1

Таблица 4

q	x₀	x₁	x₂	x₃	x₄	x₅	x₆	x₇
q₀					q₁,q₃,q₇	q₁₀
q₁	q₂
q₂		q₅
q₃								q₄
q₄								q₆
q₅					q₈		q₁₉
q₆					q₉		q₁₉
q₇					q₉		q₁₉
q₈	q₀				q₁₉
q₉	q₀				q₁₉
q₁₀	q₁₄	q₁₇					q₁₁
q₁₁	q₁₂
q₁₂						q₁₃
q₁₃			q₁₉
q₁₄	q₁₅
q₁₅						q₁₆
q₁₆			q₁₉
q₁₇			q₁₈
q₁₈			q₁₉
q₁₉

Сведение недетерминированного автомата к детерминированному.

Недетерминированность автомата локально проявляется в том, что из
некоторого его состояния q_i исходят несколько дуг, помеченных одним и тем
же символом X_j. В этом случае она устраняется склеиванием двух состояний
в одно. В результате применения этого алгоритма от автомата на рис.1 можно
перейти к эквивалентному детерминированному автомату, таблица
переходов которого приведена в табл. 5, а соответствующий ей граф
переходов - на рис. 2. Таблица 5

q	x₀	x₁	x₂	x₃	x₄	x₅	x₆	x₇
q₀					q_1,3,7	q₁₀
q_1,3,7	q₂				q₉		q₁₉	q₄
q₂		q₅
q₄								q₆
q₅					q₈		q₁₉
q₆					q₉		q₁₉
q₈	q₀				q₁₉
q₉	q₀				q₁₉
q₁₀	q₁₄	q₁₇					q₁₁
q₁₁	q₁₂
q₁₂						q₁₃
q₁₃			q₁₉
q₁₄	q₁₅
q₁₅						q₁₆
q₁₆			q₁₉
q₁₇			q₁₈
q₁₈			q₁₉
q₁₉

Рисунок 2

Минимизация автомата.

Построение минимального (но числу состояний) автомата, эквивалентного полученному в предыдущем разделе полностью определенному детеминированному конечному автомату, осуществляется в два этапа. На первом находится разбиение состояний автомата на классы эквивалентности, а на втором строится минимальный (иначе - приведенный) автомат. В начале составляется треугольная таблица (табл.6), клетки которой соответствуют всем парам (q_i, q_j), ij рабочих состояний. Она заполняется следующим образом. Если для рабочих состояний q_i и q_j в таблице существует входной символ х_k, при котором переход из q_i осуществляется в одно из рабочих состояний, а из q_j - в состояние ошибки, то состояния q_j и q_j не эквивалентны, и соответствующая им клетка помечается крестом. Иначе, если какие-либо две строчки табл.5 содержат разное число рабочих состояний или отличаются позициями, занимаемыми рабочими состояниями, то обозначающие это строки состояния не эквивалентны. В противном случае в клетку таблицы 6 с координатами q_i, q_j запишем каждую пару состояний (q_v, q_w), в которые автомат может перейти из q_i и q_j при подаче одного и того же входного символа.

Таблица 6

1,3,7

Витоге невычеркнутые клетки табл. 6 соответствуют всем парам

эквивалентных состояний. Класс эквивалентности образуется состояниями,

которые попарно эквивалентны. В данном случае получается 4 класса

эквивалентности: {q₅, q₆}, {q₈, q₉,}, {q₁₂, q₁₅},{q₁₃, q₁₆, q₁₈}. Каждое

состояние, не вошедшее ни в один класс эквивалентности, эквивалентно

лишь само себе и само образует этот класс. В нашем примере к

перечисленным классам необходимо добавить еще 9 классов

эквивалентности: q₀, q_1,3,7, q₂, q₄, q₁₀, q₁₁, q₁₄, q₁₇, q₁₉,

Состояния минимального автомата обозначим буквами r с индексами:

r₀={q₅, q₆}, r₁={q₈, q₉}, r₂={q₁₂, q₁₅}, r₃={q₁₃, q₁₆, q₁₈}, r₄={q_1,3,7},

r₅={q₂}, r₆={q₄}, r₇={q₁₀}, r₈={q₁₁}, r₉={q₁₄}, r₁₀={q₁₇}, r₁₁={q₁₉}, r₁₂={q₀}.

Минимальный автомат содержит, таким образом, 13 состояний, не считая состояния ОШИБКА. Граф переходов этого автомата приведен на рис. 3, а таблица переходов - в табл. 7

Рисунок 3

Таблица 7