3813100544

maszyny; jeśli w maszynie istnieje przejście ze stanu s do stanu s' przy wejściu a, to diagram przejść zawiera luk prowadzący ze stanu s do s' opatrzony etykietą a.

Przy rysowaniu diagramu używa się następujących oznaczeń:

1. Stany maszyny oznaczamy okręgiem.

2. Przejścia są reprezentowane przez zaetykietowane krawędzie skierowane pomiędzy wierzchołkami (stanami).

Jedna krawędź może mieć kilka etykiet, np. jeśli t G T(s, a) i t E T(s, b), to krawędź z s do t ma dwa podpisy: a i b.

3. Dołączając strzałkę po lewej stronie okręgu symbolizującego stan wskazujemy, że dany stan jest stanem początkowym.

Przykład 1.3.

Niech £ = {a, 6} będzie alfabetem. Oto przykłady maszyn niedeterministycznych oraz ich diagramów przejść.

1. [3, zmodyfikowany przez autorkę] A\ = (<Si,ii,Ti), gdzie

•    Si = {so,Sl> S2,S3> s₄,s₅};

•    h = {so};

•    przejścia maszyny A\ opisuje diagram przedstawiony na poniższym rysunku.

Niedeterminizm maszyny A\ objawia się tym, że nie dla wszystkich stanów oraz symboli alfabetu istnieją przejścia tej maszyny.