Вопрос 39. Теорема о представимости регулярных языков конечными автоматами.
Теорема 3.3. Для любого непустого языка L порождаемого регулярной грамматикой G3, существует КА К, возможно недетерминированный, представляющий ( порождающий и распознающий) язык L. ? L=L(G3), L? {e}; G3=< V,W,P,I>; ? K=< A,Q,B,?,? > ; { K(q1)}? L. ДОК-ВО : 1). Пусть задана некоторая регулярная грамматика G, G3=< V,W,P,I > , где V={ a1,a2, … , am}; W={ w1,w2, … ,wn}; I=w1; P={ wi?wi’aj ( wi?aj wi’); wi?aj ; wi ? W; aj?V} 2). Введем новый нетерминальный знак ?0 , и построим грамматику эквивалентную исходной. G3’=< V,W’,P’,I >; W’=W?{ ?0}; P’=P??i??i’aj ? P|?i??0aj ? {?0?e}. 3). Построим КА Kn порождающий язык L(G3’) : Kn=< An,Qn,Bn,?n,?n>, где ?n : Qn*An?Bn; ?n : Qn*An?Qn; An={e}; Qn=W’ ; Bn=V; P={ wi?wi’aj}; wie?wi’aj , где wi?Qn aj?Bn мы получили систему команд описывающею автомат ; 4). Построим КА Kp распознающий язык L(G3’) : Kp=< Ap,Qp,Bp,?p,?p> где Ap=V; Qp=W’; Bp={e}; P’={ wi?wi aj} wi aj?wi’
Замечание : т.к. любой конечный автомат может быть представлен автоматом Мура, поэтому при детерминации автоматов можно не учитывать состояние входов , а рассматривать автомат в виде ориентированного графа с единственным знаком aj на дуге.
Вопрос 40. Алгебра регулярных событий. Теорема о представимости регулярного события регулярной грамматикой.
R=< V, {?, •, ?}> , где ? — объединение, • — конкатенация, * — итерация ( замыкание Клини) 1). L1?L2={ ?i, ?j | ?i?L1, ?j?L2}; 2). L1•L2=L1L2={?i?j | ? ?i?L1 ? ?j?L2}; 3). L1*=Ui=0? L1i ={e} ? L1 ? L1L1 ? …? L1i ?… Регулярным событием называется строки, которые могут быть построены в алгебре регулярных событий. Пример (a?b)* • (a?aa) это язык состоящий из знаков a и b , оканчивающийся подстроками a и aa.
Теорема 3.4.: ( о представимости регулярного события регулярной грамматикой) : любое регулярное событие представимо регулярной грамматикой ( но не любая регулярная грамматика может быть представлена в виде конечного выражения в регулярной алгебре). ДОК-ВО : 1). Пусть заданы регулярные языки L1 и L2, L1?V*, L2?V*; L1?L2=L G31 ?L1; G32 ?L2; G3U?L; G31 = < V,W1,P1,I1>; G32 = < V,W2,P2,I2> ; G3U =< V,W,P,I> ; P={ I?I1 | I2, P1, P2}. Вывод : Объединение регулярных грамматик есть регулярный язык. 2). Докажем, что конкатенация регулярных языков есть регулярный язык : L1•L2=L(G3); надо построить G3=< V,W,P,I> P=P1?P2’ , где P2’ — множество продукций Р2 в которых все продукции вида A?a , A?V , W=W1?W2?{I} заменены A?I1a . Вывод : конкатенация регулярных языков является регулярным языком. 3). Докажем , что итерация регулярных языков является регулярным языком : (L1(G31))*=L(G3); G P=P1?{ I?I1I} каждую продукцию из {A?a}?P1 заменяем на продукцию A?Ia , и добавляем продукцию I?I1 , в итоге получаем систему продукций регулярной грамматики. 4). Вывод : т.к. применение операции алгебры регулярных событий не нарушает регулярности языков, а в качестве элементарных языков используем знаки алфавита V ( представляемых регулярной грамматикой), то можно сделать вывод о справедливости теоремы.
Вопрос 41. Алгебра регулярных событий. Теорема о представимости регулярного события конечным автоматом.
R=< V, {?, •, ?}> , где ? — объединение, • — конкатенация, * — итерация ( замыкание Клини) 1). L1?L2={ ?i, ?j | ?i?L1, ?j?L2}; 2). L1•L2=L1L2={?i?j | ? ?i?L1 ? ?j?L2}; 3). L1*=Ui=0? L1i ={e} ? L1 ? L1L1 ? …? L1i ?… Регулярным событием называется строки, которые могут быть построены в алгебре регулярных событий. Пример (a?b)* • (a?aa) это язык состоящий из знаков a и b , оканчивающийся подстроками a и aa.
Теорема 3.5. : (Теорема о представимости регулярного события конечным автоматом). Теорема Клини : Любое регулярное выражение может быть представлено в виде КА , который либо порождает , либо распознает R?KA( Ku,Kp). Для любого регулярного события R существует КА , возможно недетерминированный , представляющий, распознающий и порождающий это событие. ДОК-ВО : т.к. существует регуляр. событие может быть представлено в виде регулярной грамматике G3, которая может быть представлена в виде КА , порождающего распознающего строки грамматики, откуда в результате транзитивности следует справедливость теоремы Клини : R?G3?KA( Ku,Kp). Удобно рассматривать некоторый автомат преобразователь Кпр как КА распознаватель Kp.
Вводим новый алфавит A| который равен декартовому произведению входного и выходного алфавита исходного автомата. A={a1,a2}; B={b1,b2}; A|=A*B={a|11, a|12, a|21, a|22}; a|ij=< ai,bj >. Полученный автомат можно рассмотрим как автомат — преобразователь ( такие автоматы называется источниками).