Теория и реализация языков программирования

           

Связь регулярных множеств, конечных автоматов и регулярных грамматик


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

Теорема 3.1. Язык, допускаемый детерминированным конечным автоматом, является регулярным множеством.

Доказательство. Пусть L - язык, допускаемый детерминированным конечным автоматом

Введем De - расширенную функцию переходов автомата M: De(q, w) = p, где

, тогда и только тогда, когда
.

Обозначим посредством

множество всех слов x таких, что De(qi, x) = qj и если De(qi, y) = qs для любой цепочки y - префикса x, отличного от x и e, то s
k.

Иными словами,

есть множество всех слов, которые переводят конечный автомат из состояния qi в состояние qj , не проходя ни через какое состояние qs для s > k. Однако, i и j могут быть больше k.

может быть определено рекурсивно следующим образом:

Таким образом, определение

означает, что для входной цепочки w, переводящей M из qi в qj без перехода через состояния с номерами, большими k, справедливо ровно одно из следующих двух утверждений:

  1. Цепочка w принадлежит
    , то есть при анализе цепочки w автомат никогда не достигает состояний с номерами, большими или равными k.
  2. Цепочка w может быть представлена как w = w1w2w3, где
    (подцепочка w1 переводит M сначала в qk),
    (подцепочка w2 переводит M из qk обратно в qk, не проходя через состояния с номерами, большими или равными k), и
    (подцепочка w3 переводит M из состояния qk в qj) - рис. 3.16.


Рис. 3.16. 

Тогда

. Индукцией по k можно показать, что это множество является регулярным.

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

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

Праволинейная грамматика G = (N, T, P, S) называется регулярной, если



Содержание  Назад  Вперед




Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий