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

51 байтове добавени ,  преди 13 години
м
references
м (Робот Добавяне: lv:Galīgais automāts)
м (references)
 
== Описание ==
 
Крайните автомати четат редица от символи (от ''входна азбука''), наречена ''входна дума'', и извеждат също редица от символи (от ''изходна азбука''), наречена ''изходна дума''. Множеството от всички входни думи се нарича език, разпознаван от автомата.
 
* Т е множеството на преходите между състоянията на автомата: (p, x, q) ∈ T където (p, q) ∈ TxT и x ∈ Σ
* I е множеството на началните състояния <ref>Някои автори дават дефиниция само с едно начално състояние, но често се срещат автомати с няколко начални състояния. Поради тази причина тук даваме множество от начални състояния.</ref> I⊆S
* A е множеството на крайните състояния на автомата. Това са състояния, които позволяват "излизане"„излизане“ от автомата. A⊆S
 
Крайният автомат може да се представи като насочен (ориентиран) [[Граф_(математика)|граф]] с етикети на ребрата. Състоянията, представени с две концентрични окръжности са крайните състояния на автомата.
Нека имаме един недетерминиран краен автомат <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}
 
== ω-автомати ==
Друг вид крайни автомати са т.нар. '''Омега-автомати''' (ω-автомати), при които входната дума се състои от безкраен брой символи. При този модел разпознаването на дадена дума се описва чрез множеството от състояния, които се посещават безкраен брой пъти.
 
== Автомат с ε-преходи ==
Това е автомат в който някои от преходите са с празни (ε) етикети, т.е. преминаването през даден преход не променя думата. За да елиминираме ε-преходите, първо трябва да наситим автомата с ε-преходи и след това да ги заместим със съответните преходи с букви. Това действие се използва например в конкатенацията на два автомата.
Например ако вземем трансдуктора от картинката, за думата bbaa ще получим 0110.
 
Има два вида трансдуктори - [[автомат на Мили]] и [[автомат на Мур]].
 
== Регулярни езици ==
Множеството на [[Регулярен език|регулярните езици]] е равно на множеството на езиците, разпознавани от крайни автомати, т.е. всеки език, разпознаван от краен автомат, е регулярен (теорема на Клини (Kleene)). Това означава, че всеки [[регулярен израз]] може да се представи като краен автомат и обратното. Това именно е основният принцип, залегнал в работата на програмата [[grep]].
 
== Забележки ==
<references />