3582317286

utomatów

P TA

m odstawy m eoriiW ■

1. NAS, DAS, definicje, różnice

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.