Języki, automaty i obliczenia/Ćwiczenia 3: Automat skończenie stanowy

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

ĆWICZENIA 3

Ćwiczenie 1

Dla jakich słowo należy do języka akceptowanego przez automat z rysunku 1.

Rysunek 1
Rozwiązanie

Ćwiczenie 2

Opisz słownie język akceptowany przez poniższy automat.
Rysunek 2
Rozwiązanie

Ćwiczenie 3

Wyznacz prawą kongruencję automatową dla trzystanowego automatu z rysunku 2 (patrz ćwiczenie 2).

Rozwiązanie

Ćwiczenie 4

Uzupełnij poniższy rysunek w ten sposób, by uzyskany 4-stanowy automat nie akceptował żadnego słowa nad alfabetem , w którym dwie litery występują obok siebie.

Rysunek 3


Rozwiązanie

Ćwiczenie 5

Sprawdź, czy następujące automaty są równoważne.
Rysunek 5


Rozwiązanie

Ćwiczenie 6

Wyznacz automat (nad alfabetem ), którego reprezentacja spełnia następujące warunki:

  • (),

Czy automat ten jest wyznaczony jednoznacznie?

Rozwiązanie

Ćwiczenie 7

Określ monoid przejść automatu zadanego grafem

Rysunek 6

Jakie języki akceptują automaty dla , zadane grafem z rysunku 6, jeśli stanem początkowym jest , a zbiór stanów końcowych ?


Rozwiązanie

Ćwiczenie 8

Rozważmy automat synchronizujący , gdzie jest -elementowym zbiorem stanów, a dowolnym, skończonym alfabetem (definicja automatu synchronizującego podana jest w wykładzie nr 3). Dla automatu synchronizującego jego najkrótsze słowo synchronizujące nazywamy minimalnym słowem synchronizującym, a jego długość oznaczamy przez . Niech oznacza zbiór wszystkich -stanowych automatów synchronizujących i tylko takich.

Udowodnij, że

Wskazówka
Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 9

Sprawdź, które z poniższych słów należą do języka akceptowanego przez automat z ćwiczenia 1 (patrz ćwiczenie 1.)

(1) ,
(2) ,
(3) ,
(4) ,
(5) .

Ćwiczenie 10

Sprawdź, czy następujące automaty są równoważne.
Rysunek 7


Ćwiczenie 11

Wyznacz monoid przejść następującego automatu:
Rysunek 8


Ćwiczenie 12

Określ automat akceptujący język