Języki, automaty i obliczenia/Ćwiczenia 6: Automat niedeterministyczny. Lemat o pompowaniu

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 6

Ćwiczenie 1

Skonstruuj automat niedeterministyczny akceptujący język , a następnie określ równoważny automat deterministyczny przy pomocy algorytmu Determinizacja.

Rozwiązanie

Ćwiczenie 2

Zastosuj algorytm Determinizacja podany na wykładzie do

determinizacji automatu z rysunku 2.
Rysunek 2
Rozwiązanie

Ćwiczenie 3

Dla dowolnego skonstruuj -stanowy automat niedeterministyczny nad 3-elementowym alfabetem w ten sposób, by automat deterministyczny posiadał dokładnie stanów.

Rozwiązanie

Automat z pustymi przejściami

Podamy procedurę przetwarzającą niedeterministyczny automat skończony z pustymi przejściami w równoważny niedeterministyczny automat skończony bez pustych przejść.

Niech będzie niedeterministycznym automatem z p-przejściami. Dla stanu zbiór

nazywamy pustym domknięciem stanu .

Zbiór DOM jest zbiorem wszystkich stanów, do których można dojść ze stanu przechodząc po ścieżce etykietowanej słowem pustym 1. Zauważmy także, że dla dowolnego zachodzi warunek , gdyż ze stanu do niego samego można przejść pod wpływem słowa o długości 0, a .

Dla dowolnego określamy


Algorytm UsuńPustePrzejścia - buduje niedeterministyczny automat bez p-przejść równoważny danemu niedeterministycznemu automatowi z p-przejściami



  1  Wejście:  - automat niedeterministyczny z p-przejściami.
  2  Wyjście:  - automat niedeterministyczny bez p-przejść
taki, że . 3 for each do 4 DOM ; DOM jest zbiorem 5 for to do 6 DOM DOM; bardziej efektywne jest użycie IFS 7 end for 8 end for 9 ; 10 ; 11 ; rozpocznij od zbioru pustego 12 for each do 13 if DOM then 14 ; 15 end if 16 end for 17 for each do 18 for each do 19 DOM; stosujemy wzór (1) 20 for each do 21 DOM; 22 end for 23 end for 24 endfor 25 return ;



Ćwiczenie 4

Przy pomocy podanego algorytmu dla automatu określonego na rysunku 4 skonstruuj równoważny automat bez pustych przejść.
Rysunek 4
Rozwiązanie

Ćwiczenie 5

Udowodnij, że dla każdego automatu z p-przejściami istnieje automat z p-przejściami o jednoelementowym zbiorze stanów początkowych .

Rozwiązanie

Ćwiczenie 6

Niech będzie automatem z p-przejściami o następującej własności:

Załóżmy ponadto, że oraz są dowolnymi niepustymi podzbiorami oraz że w dla każdego istnieje dokładnie jedna para stanów taka, że . Jaki język akceptuje automat ?

Rozwiązanie

Ćwiczenie 7

Niech . Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są akceptowane:

  1. , gdzie dla

Słowo nazywamy odbiciem zwierciadlanym słowa .

Rozwiązanie

Ćwiczenie 8

Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są akceptowane:

  1. ,
  2. .
Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 9

Dla następujących automatów określ równoważne automaty deterministyczne.
Rysunek 6
Rysunek 7
Rysunek 8

Ćwiczenie 10

Ustalmy oraz . Udowodnij, że automat deterministyczny (obliczony algorytmem determinizacji z wykładu) równoważny automatowi niedeterministycznemu z rysunku 9, rozpoznającemu język

, posiada tyle samo stanów co .
Rysunek 9

Wskazówka

Porównaj ćwiczenie 1 (patrz ćwiczenie 1) Wynika to wprost z algorytmu determinizacji. Oznaczmy zbiór stanów automatu niedeterministycznego przez . Niech . Wystarczy zauważyć, że w -tym kroku działania, tzn. w momencie dodawania -tego stanu w budowanym automacie deterministycznym , pozostałe stany mają etykiety , , ..., , a funkcja przejść określona na nich ma postać: , jeśli , , jeśli (). Ten fakt można w prosty sposób dowieść indukcyjnie ze względu na . Dla dodawanego -szego stanu funkcja przejść będzie natomiast zdefiniowana następująco: . Zatem w ostatnim, kroku, automat deterministyczny będzie miał stanów, czyli tyle samo co automat . Algorytm zakończy w tym momencie działanie. Automat deterministyczny przedstawiony jest na rysunku 10.

Rysunek 10

Ćwiczenie 11

Niech będzie automatem deterministycznym dla automatu niedeterministycznego . Czy zbiór stanów automatu deterministycznego obliczonego za pomocą algorytmu Determinizacja zależy od:

  1. wyboru w stanu początkowego ,
  2. wyboru w zbioru stanów końcowych ?

Ćwiczenie 12

Używając algorytmu UsuńPustePrzejścia, przekształć automat z rysunku 11 w równoważny automat niedeterministyczny bez p-przejść, a następnie zdeterminizuj go przy

użyciu algorytmu Determinizacja.
Rysunek 11

Ćwiczenie 13

Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są akceptowane:

  1. ,
  2. ,
  3. ,
  4. ,
  5. dla dowolnego alfabetu ,
  6. dla dowolnego alfabetu .