Автомат над деревьями

Материал из WEGA
Версия от 13:24, 24 сентября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Автомат над деревьями''' (Tree automation) - обобщение понятия ''конечного автомат...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Автомат над деревьями (Tree automation) - обобщение понятия конечного автомата применительно к деревьям, отличным от цепочек. Существуют две версии такого автомата. Автомат нисходящего типа начинает работу с корня дерева; прочитав символ в вершине, он соответствующим образом изменяет состояние и разделяется на [math]\displaystyle{ d }[/math] автоматов для обработки [math]\displaystyle{ d }[/math] вершин-потомков по отдельности. Автомат восходящего типа начинает с нескольких самовозбуждений --- по одному на каждый лист дерева. По завершении обработки всех поддеревьев конкретной вершины автоматы, которые обрабатывают эти поддеревья, заменяются одним автоматом данной вершины. Его состояние определяется символом в этой вершине и конечными состояниями автоматов-потомков. Полученный автомат сам теперь может использоваться при дальнейшем объединении поддеревьев более высоких вершин.

Литература

[Словарь]