Скінченний автомат: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Addbot (обговорення | внесок) |
м Виправлення параметрів шаблону Портал; косметичні зміни |
||
Рядок 43:
Згідно із загальною класифікацією, дані наступні визначення:
* ''детермінований скінченний автомат'' або ''детермінований скінченний автомат акцептор'' є [[Кортеж|п'ятіркою]] <math>(\Sigma, S, s_0, \delta, F)</math>, де:
** <math>\Sigma</math> вхідна [[абетка (інформатика)|абетка]] (скінченний, не порожній набір символів).
** <math>S</math> — скінченний, не порожній набір станів.
** <math>s_0</math> — початковий стан, елемент з <math>S</math>.
** <math>\delta</math> — функція переходу: <math>\delta: S \times \Sigma \rightarrow S</math> (в [[недетермінований скінченний автомат|недетермінованих скінченних автоматах]] це буде <math>\delta: S \times \Sigma \rightarrow \mathcal{P}(S)</math>, тобто, <math>\delta</math> повертає набір станів).
** <math>F</math> набір кінцевих станів, (можливо порожня) підмножина <math>S</math>.
Для обох детермінованих і недетермінованих СА, зручно дозволити <math>\delta</math> бути неповною функцією, тобто <math>\delta(q,x)</math> не має бути визначеною для кожної комбінації <math>q \isin S</math> and <math>x \isin \Sigma</math>. Якщо СА <math>M</math> перебуває в стані <math>q</math>, наступний символ <math>x</math> і <math>\delta(q,x)</math> не визначена, тоді <math>M</math> може повідомити про помилку (тобто відхілити ввід).
Рядок 62:
== Див. також ==
{{Портал
{{Multicol}}
* [[Теорія автоматів]]
| |||