Pok-2-wyk-Slajd25
NAS – Niedeterministyczny Automat Skończony(1)
Oto niedeterministyczny automat skończony dla wyrażenia aa*|bb* zbudowany nad alfabetem składającym się z symbolu „a” oraz symbolu „b”. Występują tu epsilon-przejścia, przedstawione jako krawędzie wychodzące ze stanu s0.
Warto zwrócić uwagę, iż przedstawiony na slajdzie graf przejść nie zawiera krawędzi dla wszystkich symboli alfabetu nad którym zbudowane zostało wyrażenie regularne. Oznaczone są jedynie ścieżki prowadzące do stanów akceptujących automatu skończonego. Jest to uproszczenie, które pozwala zmniejszyć liczbę wierzchołków oraz krawędzi grafu. Należy więc pamiętać, iż wystąpienie symboli alfabetu innych niż te oznaczone na krawędziach wychodzących z danego stanu jest jednoznaczne z brakiem akceptacji danych wejściowych przez automat skończony.
