Определение недостижимых и бесполезных символов, определение приведенной грамматики
Символ 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.