Определение недостижимых и бесполезных символов, определение приведенной грамматики

Символ x из (VT U VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики

Алгоритм удаления недостижимых символов:

1. V0 = {S}; i = 1

2. Vi = {x|x из (VT U VN), в Р есть A -> axb и A изVi-1, a, b из (VT U VN)* U Vi-1

3. если Vi != Vi-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = Vi VN; VT’ = Vi VT; P’ состоит из правил множества P, содержащих только символы Vi; G’ = (VT’, VN’, P’, S).

Символ А из VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество {a из VT* | A -> a} пусто

Алгоритм удаления бесплодных символов:

Рекурсивно строим множества N0, N1, …

1. N0 = 0, i = 1

2. Ni = {A| (A -> a) из P и а из (Ni-1 U VT)*} U Ni-1

3. Если Ni != Ni-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = Ni, P’ состоит из правил множества P, содержащих только символы из VN’ U VT; G’ = (VT, VN’, P’, S)

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

Определение детерминированного конечного автомата (КА)

Конечным автоматом называют пятерку следующего вида: M(Q, V, P, R, F), где:

Q – конечное множество состояний автомата

V – конечное множество допустимых входных символов

P – функция переходов, отображающая VxQ в множество подмножеств Q: U(Q), то есть P(a, q) = U, a из V, q из Q, U – подмножество Q

R – начальное состояние автомата Q, R из Q

F – непустое множество конечных состояний автомата F непустое подмножество Q

Конечный автомат называют ДКА, если в каждом из его состояний для любого входного символа функция перехода содержит не более одного состояния: для любого а из V и q из Q: либо P(a, q) = {r}, r из Q, либо P(a, q) = пусто.

Диаграмма состояний (ДС) для заданной леволинейной регулярной грамматики. Построение ДС

Диаграмма состояний НКА – это неупорядоченный помеченный ориентированный граф: узлы – помечены символами состояний из К, дуги соединяющие A и узел помеченный В, помечены t: F(A, t) = B.

Определение недетерминированного конечного автомата

Недетерминированный конечный автомат – это пятерка (K, VT, F, H, S), где K – конечное множество состояний, VT – кон мн-во допустимых вх. символов, F – функция переходов, H – нач. состояние из K, S – мн-во заключительных состояний, подмн-во K.

Алгоритм построения детерминированного конечного автомата по НКА

М = (K, VT, F, H, S) – НКА; M’ = (K’, VT, F’, H’, S’) – ДКА, допускающий тот же язык, что и М.

1. Множество состояний К’ состоит из всех подмножеств множества К. Каждое состояние из К’ будем обозначать [A1A2…An], где Ai из К

2. Отображение F’ определим как F’([A1…An], t) = [B1…Bm], где для каждого 1 <= j <= m F(Ai, t) = Bj для каких-либо 1 <= i <= n

3. Пусть H = {H1, H2, … Hk}, тогдa H' = [H1, H2, …, Hk]

4. Пусть S = {S1, S2, …, Sp}, тогда S’ – все состояния из K’, имеющие вид […Si…], Si из S для какого-либо 1 <= i <= p.