Совпадение множества языков МП-автоматов и контекстно-свободных языков — различия между версиями
(Новая страница: «{{В разработке}}») |
|||
Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
+ | == Эквивалентность МП-автоматов и КС-языков == | ||
+ | === Построение МП-автомата по заданной КС-грамматике === | ||
+ | {{Определение | ||
+ | |definition= Пусть <tex> G=(V,T,Q,S) </tex> — КС-грамматика. Построим МП-автомат <tex> P=(\{q\},T,V \cup T, \delta ,q,S) </tex>, который допускает <tex> L(G) </tex> по пустому магазину. Функция переходов <tex> \delta </tex> будет определена следующим образом: | ||
+ | * <tex> \delta(q,\epsilon,A)=\{(q,\beta )| A \rightarrow \beta</tex> — продукция <tex> G \} </tex> — для каждой переменной <tex> A </tex>. | ||
+ | * <tex> \delta(q,a,a)=\{(q,\epsilon)\} </tex> для каждого терминала <tex> a </tex>. | ||
+ | }} |
Версия 00:43, 15 января 2011
Эта статья находится в разработке!
Эквивалентность МП-автоматов и КС-языков
Построение МП-автомата по заданной КС-грамматике
Определение: |
Пусть
| — КС-грамматика. Построим МП-автомат , который допускает по пустому магазину. Функция переходов будет определена следующим образом: