Pok-2-wyk-Slajd18
Automaty skończone(2)
Funkcję przejść f można określić za pomocą tabeli lub grafu.
Aby przedstawić obie te reprezentacje wykorzystane zostanie wyrażenie regularne ab*a.
Funkcja przejść w postaci tabeli zawiera w każdym polu stan do którego ma przejść automat skończony jeśli w stanie określonym poprzez nagłówek kolumny natrafi na wejściu na symbol będący nagłówkiem wiersza.
W przypadku reprezentacji grafowej stany są reprezentowane poprzez wierzchołki grafu skierowanego. Krawędzie natomiast oznaczają symbole, które mogą wystąpić na wejściu.
Aby w pełni zdefiniować automat skończony oprócz funkcji przejścia należy podać stan początkowy oraz zbiór stanów końcowych.
Przyjmijmy więc, że stanem początkowym jest stan s0. Na grafie został on oznaczony zgodnie z konwencją strzałką. Zbiór stanów końcowych zawiera dla przykładowego wyrażenia jedynie stan s2. Węzeł grafu odpowiadający temu stanowi oznaczony został dodatkowym okręgiem.
