Искусственный интеллект

105 5. Среды и языки часть времени поиска может расходоваться впустую на анализ избыточной информации. В настоящей главе показано так же, как может быть сокращен объем описания на языке в задачах поиска целевых состояний. 5.1. Автомат и среда Конечным инициальным детерминированным автоматом называют объект, определяемый следующими шестью понятиями. Входной алфавит А = {ар а^ ..., ат). Внутренний алфавит (множество состояний автомата) В = {Ь„ Ь, ..., Ьп). Выходной алфавит С = {сг с2, ..., ср}. Функция переходов/: А х В -> С, записываемая так же, как Да, Ь) = Ь., где а е А, Ь., Ь. е В. Функция выходов ф: В -> С, записываемая так же, как = с, где bj e В, с е С. Начальное состояние Ьо е В. Обычно будем полагать, что Ьо = bt В дальнейшем для простоты вместо длинного словосочетания «инициальный детерминированный конечный автомат» будем говорить просто «автомат». Автомат можно рассматривать как эквивалент некоторой абстрактной среды, имеющей множество состояний В и начальное состояние b0 e В. Когда среда находится в каком-либо состоянии Ь., агентом может быть совершено действие а. В результате среда перейдет в состояние Д, определяемое функцией переходов Да, Ь) = Ь. В каждом состоянии Лу может быть определена функция выходов, называемая также иногда оценочной функцией ф(А) = сг Если автомат находится в состоянии Ьо, то считается, что еще никакая входная последовательность на него не была подана. Для удобства будем полагать, тем не менее, что на него была подана пустая последовательность е.