Недетерминированные конечные автоматы.

 

Пусть A⁰ – недетерминированный конечный автомат.

A⁰ = < P⁰, S⁰, s₀⁰,φ⁰,F⁰>

F⁰ – множество конечных подмножеств алфавита состояний.

S = {S₀, S₁, S₂}

M(S) = {{ S₀ }, { S₁ }, { S₂ }, { S₀, S₁}, { S₀, S₂}, { S₁, S₂}, { S₀, S_1, S₂}}

M^* <= M

φ: P*SàS – детерминированный алфавит

φ⁰: P*SàM^* - недетерминированный автомат

 

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

ТЕОРЕМА: Если L(A⁰) – язык который допускается некоторым конечным автоматом A⁰, то существует детерминированный конечный автомат A который допускает этот же язык.

 

Преобразование недетерминированного автомата в детерминированный.

 

 

Имеется два способа:

1. Общий способ

Пример:

 

P = {a,b}

S = {I,B,C}

M(S) = {[I], [B], [C], [IB], [IC], [BC], [IBC], o}

φ(I, a) = [I, c]

φ(I, b) = [B]

φ(B, a) = [C]

φ(B, b) = []

φ(C, a) = [B]

φ(C, b) = [B]

φ(IB, a) = [IC]

φ(IB, b) = [B]

φ(IC, a) = [I,C, B]

φ(IC, b) = [B]

φ(BC, a) = [BC]

φ(BC, b) = [B]

φ(IBC, a) = [IBC]

φ(IBC, b) = [B]

 

 

Вершины IB и BC являются недостижимыми, а вершины 0 нет в выходном сигнале для состояния B, следовательно граф упроститься:

 

Это общий способ построения автомата.

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

 

2 способ. Сокращенный способ.

a) Строится заготовка таблицы переходов детерминированного конечного автомата.

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

c) Если полученное подмножество состояний или состояния отсутствуют в левой части таблицы переходов, то они заносятся туда и осуществляется переход к пункту 2.

 

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

Пример:

 

Pi / Si	a	b
I	IC	B
IC	ICB	B
B	C	---
ICB	ICB	B
C	B	B

 

 

Пример: Недетерминированный конечный автомат.

 

D – конечная вершина.

 

Преобразование некоторых типов грамматики к автоматному ввиду.

 

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

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

Пусть задан язык:

L = {x₁ x₂ x₃…x_n} x_i? V_t^*

X_i = a₁a₂a₃…a_m a_i? V_t

Для построения грамматики введем следующие нетерминальные символы: A₁A₂…A_m-1  и следующие правила:

X_i à a₁A₁ A₁à a₂A₂ …A_m-2àa_m-1A_m-1 A_m-1àa_m

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

Рассмотрим контекстно-свободные грамматики.

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

Правила вида:

A à xB – правосторонняя, где A,B – нетерминальные символы.

A à Bx – левосторонняя.

A à x – заключительное правило.

Для любой правосторонней или левосторонней грамматики может быть построено эквивалентная ей правосторонняя или левосторонняя автоматная грамматика.

Доказательство:

G = <V_t, Vⁿ, I, R> создается набор правил вида:

A à xB, где x? V_t^*

Предположим, что x_i = a₁a₂…a_m  введем нетерминальные символы A₁A2…A_m-1  и добавим правило A à a₁A₁

A₁àa₂A₂ A_m-1 àa_m-1A_m-1 A_m-1 à a_mB либо A_m-1 à a_m

Цепочка правил, заканчивающаяся A_m-1 à a_mB заменит одно правило A à xB. Цепочка правил, заканчивающаяся A_m-1 à a_m заменит правило A à x

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

если ώàξ₁ A ξ₂  и есть правило

A à B, B à Cx то применяя эти правила в результате получим:

ξ₁ A ξ₂ à ξ₁ B ξ₂ à ξ₁ Cx ξ₂ это равносильно тому, что A à Cx

Доказательство: пусть есть правило вида

R = {…AàB…BàCx}

В этом случае вывод любой цепочки, содержащий нетерминальный символ A, осуществляется следующим образом, пусть есть вывод

ώàξ₁ A ξ₂, тогда данная цепочка преобразуется в конечную следующим образом:

ξ₁ A ξ₂ à ξ₁ B ξ₂à ξ₁ Cx ξ₂

Равносильно A à Cx

Чтобы исключить цепочку ξ₁ B ξ₂ вместо A, B нужно записать A à Cx.

 

Алгоритм получения правил, не содержащих правил вывода нетерминальных символов.

1) Грамматика имеет набор правил R. Разобьем его на R₁  и R₂ , причем в R₁ будут входить только правила типа A à B, где A,B? V_n

2) Для любого символа A_i стоит в левой части правила нетерминала построим подмножество правил (A_i) следующим образом, если существует

          A_i à A_n; A_n àηB, то в SA_i войдет A_i à ηB.

3) Строим новую грамматику, создающую следующий набор правил:

       R = V_i=1^k S(A_i) v R_i где k – число нетерминальных символов, находящихся слева в правилах набора R подмножества. Построение грамматики будет эквивалентно исходной и не создаст правил нетерминалов.

Рассмотрим пример:

G:

R = {IàaM, MàA, AàaA, AàB, BàbB, Bàb}

V_t = {a, b}

V_n = {I, M, A, B}

R₁ = {M à A, A à B}

R₂ = {I à aM, A à aA₁ B à bB, B à b}

S(M) = {MàaA, M à bB, M à b}

S(A) = {A à bB, A à b}

R = {M à aA, M à bB, M à b, A àbB, A àb, I à aM, A à aA, B à bB, B à b}

Грамматика правосторонняя или левосторонняя контекстно-свободная, создается правило нетерминал-нетерминал, может быть преобразовано к автоматному виду.

Грамматика, контекстно-свободная создающаяся и правосторонней и левосторонней не может быть преобразована а автоматному виду.

Если грамматика имеет правило вида:

A à φAψ, φ,ψ? V^* φ ≠ ε, то она не может быть преобразована к контекстно-свободной.

Самовосстанавливающаяся грамматика, которая содержит правило вида: Aà φAψ, где φ,ψ – любые символы, причем не пустые не может быть преобразована к автоматному виду.

Данный вывод вытекает из вывода два.

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