Разлика между версии на „Краен автомат“

м
Bot: Automated text replacement (-едно единствено +едно-единствено); козметични промени
м (whitespaces)
м (Bot: Automated text replacement (-едно единствено +едно-единствено); козметични промени)
 
 
== Дефиниция ==
[[КартинкаФайл:DFA_example_multiplies_of_3.svg|thumbмини|300px|Граф на краен детерминиран автомат]]
Математически, крайните автомати са представени като <math>\mathcal{M}=(S,\Sigma,T,I,A)</math>, където:
* S е множеството на състоянията на автомата
* A е множеството на крайните състояния на автомата. Това са състояния, които позволяват „излизане“ от автомата. A⊆S
 
Крайният автомат може да се представи като насочен (ориентиран) [[Граф_Граф (математика)|граф]] с етикети на ребрата. Състоянията, представени с две концентрични окръжности са крайните състояния на автомата.
 
== Детерминизъм ==
Крайните автомати биват ''детерминирани'' и ''недетерминирани''. При детерминираните може да има най-много по един преход от дадено състояние за всяка буква от азбуката на автомата, докато при недетерминираните са възможни няколко различни прехода за една и съща буква. Също така детерминираните крайни автомати имат едно -единствено начално състояние.
 
Всеки недетерминиран автомат може да се преобразува в детерминиран, като последният може да има най-много <math>2^n</math> или <math>Card(\mathcal{P}(S))</math> състояния, където <math>n=Card(S)</math>.
 
'''Пример за детерминиране:'''
[[FileФайл:Afn_exemple.png|мини|200п|Недетерминиран краен автомат]]
Нека имаме един недетерминиран краен автомат <math>\mathcal{M}=(S,\Sigma,T,I,A)</math> такъв, че:
* S = {1,2,3}
| {1}
|}
[[FileФайл: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>
 
== Автомат трансдуктор ==
[[FileФайл:Transductor_automata.png|мини|250п|Автомат трансдуктор]]
'''Трансдуктор''' се нарича автомат, който за всеки входящ символ, връща съответстващ изходящ.