Скінченний автомат, як модель перетворювача дискретної інформації

Визначення 1. Автомат – це схематизований алгоритм, у якому переходи виконуються детерміновано залежно від зовнішніх впливів (вхідних даних). Вважається, що:

1) Автомат функціонує в абстрактному дискретному часі.

2) Усі переходи відбуваються миттєво.

Скінченний автомат можна зобразити у вигляді схеми (рис. 1), що складається з вхідної стрічки, односторонньої вхідної голівки. що зміщується тільки вправо, і керуючого пристрою зі скінченним числом станів (зі скінченною пам’яттю).

Вхідна стрічка – це лінійна послідовність комірок, кожна з яких містить один і лише один вхідний символ . На рис. 1 кінцеві ліва і права комірки ділянки, що обробляється автоматом, позначені кінцевим маркером , а порожня комірка позначена як .

Вхідна голівка у кожний момент обробляє одну комірку вхідної стрічки.

Керуючий пристрій має скінченну множину станів , що характеризуються певним набором внутрішніх змінних і відіграють роль деякої пам’яті про його передісторію. Він містить відображення, що залежно від попереднього стану і поточного вхідного символу визначають наступний стан керуючого пристрою, переміщення вхідної голівки й вихідну інформацію.

Запуск (start) роботи скінченного автомату здійснюється з його початкової конфігурації – керуючий пристрій знаходиться у заданому початковому стані, вхідна голівка виставлена на крайній лівий символ ділянки вхідної стрічки. На кожному t -му такті (кроці) (t=1,2,…)роботи автомату виконуються наступні операції:

1) вхідна голівка читає одну поточну вхідну комірку;

2) залежно від прочитаного вхідного символу і поточного стану керуючого пристрою цей стан змінюється чи залишається тим самим;

3) якщо це передбачено, голівка заносить у комірку вихідний символ;

4) вхідна голівка зміщується на одну комірку вправо або залишається нерухомою. Автомат завершує функціонування, досягши одного зі заздалегідь указаних завершальних станів або обробивши всю задану ділянку вхідної стрічки. Ці умови зупинки повинні бути однозначно встановленими.

<== попередня сторінка	\|	наступна сторінка ==>
	\|	Визначення та властивості скінченого автомату

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.