Відмінності між версіями «Скінченний автомат»

(Скасування редагування № 12681847 користувача Aktommy (обговорення))
Якщо функція виходу є функцією стану і вхідної абетки(<math>\omega: S \times \Sigma \rightarrow \Gamma</math>) таке визначення відповідає '''моделі Мілі''', і може бути виконана як [[автомат Мілі]]. Якщо функція виходу залежить тільки від стану (<math>\omega: S \rightarrow \Gamma</math>) тоді таке визначення відповідає '''моделі Мура''', і може бути виконана як [[автомат Мура]]. Скінченний автомат без функції виходу відомий як напівавтомат або як [[модель станів і переходів]].
 
==== Автоматні оператори ====
'''Означення:''' Відповідність, яка відображає вхідні ланцюжки '''a''' автомата '''M''' у вихідні ланцюжки '''w''' описаним вище способом, називають автоматним відображенням, а також автоматним оператором''' M'''. Якщо результат застосування цього оператора до ланцюжка '''a''' - вихідний ланцюжок '''w''',
 
то це позначають '''M(a) = w'''. Кількість символів у ланцюжку '''a''', як завжди, називають довжиною ланцюжка '''a''' та позначають '''|a|''' чи l'''(a)'''.
 
<u>Автоматне відображення має дві властивості:</u>
 
1. Ланцюжки '''a''' та '''w = M(a)''' мають однакову довжину: '''|a| = |w|''' (збереження довжини).
 
2. Якщо '''a = a1a2''' й '''M(a1a2) = w1w2''', де''' |a1| = |w1|''', то '''M(a1) = w1''', тобто образ відрізка довжиною l дорівнює відрізку образу з такою самою довжиною.
 
Властивість 2 означає, що автоматні оператори - це оператори без випередження, тобто такі, котрі, обробляючи ланцюжок зліва направо, “не підглядають уперед”: i-та буква вихідного ланцюжка залежить тільки від перших i букв вхідного ланцюжка. Приклад оператора з випередженням - той, який ланцюжку ''a = x1x2…xk'' ставить у відповідність ланцюжок ''xk…x1x2'', перша буква вихідного ланцюжка тут дорівнює останній букві вхідного ланцюжка. Зазначимо, що ці дві властивості - це не достатні умови автоматності відображення: існують відображення, які задовольняють умови 1 і 2, але не реалізовані в скінченному автоматі.
== Див. також ==
{{Портал|Математика}}
14

редагувань