Tabela przejść między stanami - State-transition table
W teorii automatów i układ sekwencyjny , A tabela stan przejściowy jest tabelą pokazującą co państwo (lub państwa członkowskie, w przypadku niedeterministyczny automat skończony ) A automat skończony będzie przemieszczać się, w oparciu o aktualnie wejść państwowe i inne. Zasadniczo jest to tablica prawdy, w której wejścia zawierają bieżący stan wraz z innymi wejściami, a wyjścia zawierają kolejny stan wraz z innymi wyjściami.
Tablica przejść stanów jest jednym z wielu sposobów określania maszyny skończonej. Inne sposoby obejmują diagram stanu .
Wspólne formy
Jednowymiarowy
Tabele stanów przejść są czasami tablicami jednowymiarowymi, zwanymi również tablicami charakterystycznymi . Bardziej przypominają tablice prawdy niż ich dwuwymiarową formę. Pojedynczy wymiar wskazuje wejścia, stany bieżące, stany następne i (opcjonalnie) wyjścia związane z przejściami stanów.
| Wejście | Stan obecny | Następny stan | Wynik |
|---|---|---|---|
| ja 1 | S 1 | S i | O x |
| ja 2 | S 1 | S j | O ja |
| … | … | … | … |
| I n | S 1 | S k | O z |
| ja 1 | S 2 | S i′ | O x′ |
| ja 2 | S 2 | S j ' | O ja |
| … | … | … | … |
| I n | S 2 | S k′ | O z′ |
| … | … | … | … |
| ja 1 | S m | S ja” | O x” |
| ja 2 | S m | S j " | O ja” |
| … | … | … | … |
| I n | S m | S k″ | O oo " |
Dwuwymiarowe
Tabele przejść między stanami są zazwyczaj tabelami dwuwymiarowymi. Istnieją dwa popularne sposoby ich układania.
W pierwszym przypadku jeden z wymiarów wskazuje stan aktualny, a drugi wejścia. Przecięcia wierszy/kolumn wskazują kolejne stany i (opcjonalnie) wyjścia związane z przejściami stanów.
|
Wejście
Stan obecny
|
ja 1 | ja 2 | … | I n |
|---|---|---|---|---|
| S 1 | S I / O x | S J / O r | … | S k / O oo |
| S 2 | Si ′ /Ox ′ | S j′ /O y′ | … | S k′ /O z′ |
| … | … | … | … | … |
| S m | Si ” /O x” | S J " I / O Z" | … | S k " I / O Z" |
W drugim przypadku jeden z wymiarów wskazuje stany bieżące, a drugi stany kolejne. Przecięcia wierszy/kolumn wskazują wejścia i (opcjonalnie) wyjścia związane z przejściami stanów.
|
Następny stan
Stan obecny
|
S 1 | S 2 | … | S m |
|---|---|---|---|---|
| S 1 | I I / O x | — | … | — |
| S 2 | — | — | … | Ja j /O y |
| … | … | … | … | … |
| S m | — | ja k /O z | … | — |
Inne formy
Jednoczesne przejścia w wielu maszynach skończonych można przedstawić w formie n-wymiarowej tabeli stanów przejść, w której pary wierszy odwzorowują (zestawy) stanów bieżących na stany następne. Jest to alternatywa dla przedstawiania komunikacji pomiędzy oddzielnymi, współzależnymi maszynami skończonymi.
Z drugiej strony, oddzielne tabele zostały użyte dla każdego przejścia w obrębie pojedynczej maszyny skończonej: „tabele AND/OR” są podobne do niekompletnych tabel decyzyjnych, w których decyzja dla istniejących reguł jest domyślnie aktywacją powiązane przejście.
Przykład
Przykład tablicy stanów przejść wraz z odpowiadającym jej diagramem stanów dla maszyny skończonej podano poniżej:
|
Wejście
Stan obecny
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | S 1 | S 2 |
|
W tabeli przejść stanów wszystkie możliwe dane wejściowe do automatu skończonego są wyliczane w kolumnach tabeli, podczas gdy wszystkie możliwe stany są wyliczane w wierszach. Jeśli maszyna jest w stanie S 1 (pierwszy rząd) i otrzyma dane wejściowe 1 (druga kolumna), maszyna pozostanie w stanie S 1 . Teraz, jeśli maszyna jest w stanie S 1 i otrzyma dane wejściowe 0 (pierwsza kolumna), przejdzie do stanu S 2 .
Na diagramie stanu pierwszy jest oznaczony strzałką zapętloną od S 1 do S 1 oznaczoną 1, a drugi strzałką od S 1 do S 2 oznaczoną 0. Proces ten można opisać statystycznie za pomocą Łańcuchy Markowa .
W przypadku niedeterministycznej maszyny skończonej , dane wejściowe mogą powodować, że maszyna jest w więcej niż jednym stanie, stąd jej niedeterminizm . Jest to oznaczone w tabeli stanów przejściowych przez zbiór wszystkich stanów docelowych zawartych w parze nawiasów klamrowych {}. Przykład tablicy stanów przejść wraz z odpowiadającym jej diagramem stanów dla niedeterministycznego automatu skończonego podano poniżej:
|
Wejście
Stan obecny
|
0 | 1 |
|---|---|---|
| S 1 | S 2 | S 1 |
| S 2 | {S 1 , S 2 } | S 2 |
|
Jeśli maszyna znajduje się w stanie S 2 i otrzyma dane wejściowe 0, będzie jednocześnie w dwóch stanach, stanach S 1 i S 2 .
Transformacje z/do diagramu stanu
Możliwe jest narysowanie diagramu stanów z tabeli stanów przejść. Poniżej podana jest sekwencja łatwych do wykonania kroków:
- Narysuj kółka reprezentujące podane stany.
- Dla każdego ze stanów przeskanuj odpowiedni wiersz i narysuj strzałkę do stanów docelowych. Może istnieć wiele strzałek dla znaku wejściowego, jeśli maszyna skończona jest niedeterministyczna.
- Wyznacz stan jako stan początkowy . Stan początkowy jest podany w formalnej definicji maszyny skończonej.
- Wyznacz jeden lub więcej stanów jako stan akceptujący . Jest to również podane w formalnej definicji maszyny skończonej.
Zobacz też
Bibliografia
Dalsza lektura
- Michael Sipser: Wprowadzenie do teorii obliczeń . PWS Publishing Co., Boston 1997 ISBN 0-534-94728-X