Изменения

Перейти к: навигация, поиск

Эквивалентность ДМП-автоматов

60 байт добавлено, 00:03, 17 января 2017
Нет описания правки
[[Нормальная форма ДМП-автомата|Предположим детерминированный строгий автомат с единственным состоянием с элементами, представленный тройкой]]: входной алфавит на ленте <tex>\Sigma</tex>, стековым алфавит <tex>\Gamma</tex> и множеством переходов <tex>\Delta</tex>. Мы предполагаем наличие полного порядка на <tex>\Sigma</tex>,и говорим, что слово <tex>u</tex> короче слова <tex>v</tex> если <tex>|u| < |v|</tex> или <tex>|u| = |v|</tex> и <tex>u</tex> лексикографически меньше <tex>v</tex>. Пусть <tex>E, F, G,\dotsc</tex> - допустимые конфигурации.
{{Определение
|definition=<tex>E \cdot u</tex> - конфигурация '''<tex>E</tex> после слова <tex>u</tex>''', единственная допустимая конфигурация <tex>F</tex> такая что <tex>(E, u) \rightarrow F</tex>, которая может быть и <tex>\emptyset</tex>.
7
правок

Навигация