Вікіпедія

Детермінований скінченний автомат: відмінності між версіями

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Kot212001 (обговорення | внесок)
73 редагування
Немає опису редагування
Мітки: Візуальний редактор Редагування з мобільного пристрою Редагування через мобільну версію
Kot212001 (обговорення | внесок)
73 редагування
Немає опису редагування
Мітки: Візуальний редактор Редагування з мобільного пристрою Редагування через мобільну версію
Рядок 46:
== Приклад ==
 
НаступнийНижче наведентй приклад ДСА ''М'', з двійковою абеткою, який розпізнає рядки з парною кількістю 0.
 
[[Файл:DFAexample.svg|right|thumb|250px|[[Діаграма станів]] для ''M'']]
''M'' = (''Q'', Σ, δ, ''q<sub>0</sub>'', ''F''), де
* ''Q'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>},
* Σ = {0, 1},
Рядок 63:
|}
 
Стан ''S''<sub>1</sub> показує, що восеред вхідних даних, наразі опрацьованих на даний час, зустріласьтрапилася парна кількість 0, тоді як ''S''<sub>2</sub> вказує на непарну кількість. 1 на вході не змінює стану автомата. ПоПісля завершенізавершення введення даних, стан буде вказувати, чи зустріласьтрапилась парна кількість 0. Якщо зустріласьтак парнадійсно кількість 0сталося, ''M'' опиниться в стані ''S''<sub>1</sub>, допустимийщо станє допустимим станом, тож поданий на вхід рядок буде розпізнаний.
 
Мова, розпізнаванащо розпізнається ''M, -'' це [[регулярна мова]], задана [[регулярний вираз|регулярним виразом]]
: <math> 1^* \bigl( 0 (1^*) 0 (1^*) \bigr)^*, \,</math>
 
де «*» - це [[зірка Кліні]], тобто, 1* позначає будь-яку кількість (можливо нуль) символів «1».
<!--(1<sup>*</sup>(0(1)<sup>*</sup>0)<sup>*</sup>)<sup>*</sup>-->
<!-- The \,\! is to keep the formula rendered as PNG instead of HTML to ensure consistency of representation. Please don't remove it.-->
Отримано з https://uk.wikipedia.org/wiki/Детермінований_скінченний_автомат