Краен автомат: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Ред 25:
Крайните автомати биват ''детерминирани'' и ''недетерминирани''. При детерминираните може да има най-много по един преход от дадено състояние за всяка буква от азбуката на автомата, докато при недетерминираните са възможни няколко различни прехода за една и съща буква. Също така детерминираните крайни автомати имат едно единствено начално състояние.
Всеки недетерминиран автомат може да се преобразува в детерминиран, като последният може да има най-много <math>2^n</math> или <math>Card(\mathcal{P}(S))</math> състояния, където <math>n
'''Пример за детерминиране:'''
[[Картинка:Afn_exemple.png|мини|200п|дясно|Недетерминиран краен автомат]]
Нека имаме един недетерминиран краен автомат <math>\mathcal{M}=(S,\Sigma,T,I,A)</math> такъв, че:
* S = {1,2,3}
* Σ = {a,b}
* T = {(1,a,1),(1,b,1),(1,a,2),(2,a,3),(2,b,3)}
* I = {1}
* A = {3}
Този автомат разпознава езика (a+b)*a(a+b).
<math>n=Card(S)=3 \Rightarrow 2^3=8</math> е най-големият възможен брой състояния, който можем да имаме в детерминирания автомат. Можем да проверим това и чрез броя на частите на S: <math>\mathcal{P}(S)=\{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}</math>. Очевидно е, че <math>Card(\mathcal{P}(S))=8</math>.
За да получим състоянията и преходите на детерминирания краен автомат, съставяме следната таблица:
{| border="1" cellspacing="0"
!
! a
! b
|-
! {1}
| {1,2}
| {1}
|-
! {1,2}
| {1,2,3}
| {1,3}
|-
! {1,2,3}
| {1,2,3}
| {1,3}
|-
! {1,3}
| {1,2}
| {1}
|}
[[Картинка:Afd_exemple.png|мини|200п|дясно|Резултатът: детерминиран краен автомат]]
Получаваме детерминиран краен автомат <math>\mathcal{D}=(S_\mathcal{D},\Sigma, T_\mathcal{D}, I_\mathcal{D}, A_\mathcal{D})</math> такъв, че:
* <math>S_\mathcal{D}=\{\{1\},\{1,2\},\{1,3\},\{1,2,3\}\}</math>
* Множеството на преходите <math>T_\mathcal{D}</math> е представено от таблицата.
* <math>I_\mathcal{D}=\{\{1\}\}</math>
* <math>A_\mathcal{D}=\{\{1,3\},\{1,2,3\}\}</math>
Крайните състояния на получения автомат са тези, които съдържат крайните състояния на изходния автомат.
== Еквивалентни автомати ==
| |||