utomatów
m odstawy m eoriiW ■
Automat skończony jest modelem matematycznym systemu o dyskretnych wejściach i wyjściach.
AS nie można na nim zrobić a'b' bo automat skończony nie umie liczyć.
NAS- niedeterministyczny automat skończony-to maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole słowa. Po przeczytaniu symbolu zmienia stan na stan będący elementem zbioru (stanów), który jest wartością funkcji przejścia. Jeśli po przeczytaniu słowa znajdujemy się w stanie akceptującym, czyli automat akceptuje dane słowo. NAS definiujemy jako (0,2,6,qO,F)
O- skończony zbiór stanów
2 - skończony alfabet wejściowy
6-funkcja przejść
q0 - stan początkowy
F - zbiór stanów akceptujących
DAS - deterministyczny automat skończony - maszyna o skończonej liczbie stanów, która zaczynając w stanie początkowym czyta kolejne symbole słowa. Po przeczytaniu symbolu zmienia stan na będący wartością funkcji iedneeo przeczytanego symbolu oraz stanu aktualnego. Jeśli po przeczytaniu słowa znajdujemy się w stanie akceptującym, czyli st?WQ natęży .dę języką r?atląm<m tiff rózpęznawgnfa którego jest zbudowany DAS. DAS definiujemy jako (2,Q,qO,F, 6) przyjmując że symbole znaczą to samo co w NAS.
Czyli DAS to taki ze z jednego stanu możesz po danej zmiennej alfabetu przejść tylko do jednego stanu, a w NAS może być tak że są dwie lub więcej dróg.
Twierdzenia o równoważności automatów NAS i DAS:
-Każdy DAS jest NAS.
-Dla każdego NAS można zbudować równoważny z nim DAS.
-Wniosek: NAS akceptuje tylko klasę języków regularnych.