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

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

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

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

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

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

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

из алфавита {х1, х2, х3, х4, х5, х6, х7} в соответствии с табл. 2.

Таблица 1

ci C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 C16 C17 C18
si                                    
xi X X X X X X X X X X X X X X X X X X

Таблица 2

А Б В Г Д Е Ж З И Й К Л М Н О П
X1 X5 X2 X4 X6 X6 X4 X3 X3 X0 X7 X0 X3 X7 X4 X5
Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я -
X0 X4 X5 X7 X2 X5 X1 X2 X2 X0 X6 X1 X1 X3 X7 X5

Для курсовой работы задана формальная грамматика G=(Vt, Vn, S, R), где Vt={c1, c2, c3, ... , c8} - терминальный словарь; Vn= {S,A,B,C,D,E,F } - нетерминальный словарь; S, принадлежащее множеству Vn - начальный символ грамматики; R - множество правил вывода, которые имеют следующий вид:

S→c1 c2 c3 A; S→c1 c4 c5 B; S→c6 C; S→c7 F; A→c8 D; A→c9;

B→c8 E; B→c9; C→c8 E; C→c9; D→c10 S; D→c11; E→c10 S;

E→c11; F→c12 c13 c14 c15; F→c16 c13 c14 c15; F→c17 c18 c15;

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

G’=(V’t,V’n, S, R’), где V’t={x0, x1,х2, ... , х7} - новый терминальный словарь;

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

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

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

S→x4 x0 x1A | x4 x7 x7B | x4C | x5F; A→x4D | x6; B→x4E | x6; C→x4E | x6;

D→x0S | x4; E→x0S | x4; F→x6 x0 x5 x2 | x0 x0 x5 x2 | x1 x2 x2

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

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

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

S→x4 S1; S1→x0 S2; S2→x1 A; S→x4 S3; S3→x7 S4; S4→x7 B; S→x4 C; S→x5 F;

A→x4 D; A→x6; B→x4 E; B→x6; C→x4 E; C→x6; D→x0 S; D→x4;

E→x0 S; E→x4; F→x6 F1; F1→x0 F2; F2→x5 F3; F3→x2; F→x0 F4; F4→x0 F5;

F5→x5 F6; F6→x2; F→x1 F7; F7→x2 F8; F8→x2

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

Vn’’ = {S1, S2, S3, S4, А, В, С, D, E, F, F1, F2, F3, F4, F5, F6, F7, F8} и его

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

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

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

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

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

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

Таблица 3

S S1 S2 S3 S4 A B C D E
q0 q1 q2 q3 q4 q5 q6 q7 q8 q9
F F1 F2 F3 F4 F5 F6 F7 F8 -
q10 q11 q12 q13 q14 q15 q16 q17 q18 q19

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

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

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

Рисунок 1

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

Таблица 4

q x0 x1 x2 x3 x4 x5 x6 x7
q0         q1,q3,q7 q10    
q1 q2              
q2   q5            
q3               q4
q4               q6
q5         q8   q19  
q6         q9   q19  
q7         q9   q19  
q8 q0       q19      
q9 q0       q19      
q10 q14 q17         q11  
q11 q12              
q12           q13    
q13     q19          
q14 q15              
q15           q16    
q16     q19          
q17     q18          
q18     q19          
q19                

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

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

q x0 x1 x2 x3 x4 x5 x6 x7
q0         q1,3,7 q10    
q1,3,7 q2       q9   q19 q4
q2   q5            
q4               q6
q5         q8   q19  
q6         q9   q19  
q8 q0       q19      
q9 q0       q19      
q10 q14 q17         q11  
q11 q12              
q12           q13    
q13     q19          
q14 q15              
q15           q16    
q16     q19          
q17     q18          
q18     q19          
q19                

Рисунок 2

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

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

Построение минимального (но числу состояний) автомата, эквивалентного полученному в предыдущем разделе полностью определенному детеминированному конечному автомату, осуществляется в два этапа. На первом находится разбиение состояний автомата на классы эквивалентности, а на втором строится минимальный (иначе - приведенный) автомат. В начале составляется треугольная таблица (табл.6), клетки которой соответствуют всем парам (qi, qj), i≠j рабочих состояний. Она заполняется следующим образом. Если для рабочих состояний qi и qj в таблице существует входной символ хk, при котором переход из qi осуществляется в одно из рабочих состояний, а из qj - в состояние ошибки, то состояния qj и qj не эквивалентны, и соответствующая им клетка помечается крестом. Иначе, если какие-либо две строчки табл.5 содержат разное число рабочих состояний или отличаются позициями, занимаемыми рабочими состояниями, то обозначающие это строки состояния не эквивалентны. В противном случае в клетку таблицы 6 с координатами qi, qj запишем каждую пару состояний (qv, qw), в которые автомат может перейти из qi и qj при подаче одного и того же входного символа.

Таблица 6

1,3,7 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 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 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 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 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 X X X X X X X  
  1,3,7  

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

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

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

эквивалентности: {q5, q6}, {q8, q9,}, {q12, q15},{q13, q16, q18}. Каждое

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

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

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

эквивалентности: q0, q1,3,7, q2, q4, q10, q11, q14, q17, q19,

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

r0={q5, q6}, r1={q8, q9}, r2={q12, q15}, r3={q13, q16, q18}, r4={q1,3,7},

r5={q2}, r6={q4}, r7={q10}, r8={q11}, r9={q14}, r10={q17}, r11={q19}, r12={q0}.

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

Рисунок 3


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


Таблица 7

Наши рекомендации