Связь регулярных множеств, конечных автоматов и регулярных грамматик
В разделе 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, справедливо ровно одно из следующих двух утверждений:
- Цепочка w принадлежит , то есть при анализе цепочки w автомат никогда не достигает состояний с номерами, большими или равными k.
- Цепочка 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
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий