897 357
редакции
Разлика между версии на „Краен автомат“
Направо към навигацията
Направо към търсенето
м
Bot: Automated text replacement (-едно единствено +едно-единствено); козметични промени
м (whitespaces) |
м (Bot: Automated text replacement (-едно единствено +едно-единствено); козметични промени) |
||
|
== Дефиниция ==
[[
Математически, крайните автомати са представени като <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>.
'''Пример за детерминиране:'''
[[
Нека имаме един недетерминиран краен автомат <math>\mathcal{M}=(S,\Sigma,T,I,A)</math> такъв, че:
* S = {1,2,3}
| {1}
|}
[[
Получаваме детерминиран краен автомат <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>
== Автомат трансдуктор ==
[[
'''Трансдуктор''' се нарича автомат, който за всеки входящ символ, връща съответстващ изходящ.
| |||