filipg/amu_automata_2011 — Issue #101: Zaimplementować algorytm sprawdzania, czy automat niedeterministyczny akceptuje dany napis, oparty na analizowanie bieżącego zbioru stanów.
Author: filipg
Created: 2011-10-19 06:30:45+00:00
State: open

Tzw. algorytm Thompsona - jest to algorytm podobny do tego, jak dla automatu deterministycznego, tylko zamiast stanu bieżącego rozpatrujemy bieżący zbiór stanów. Na przykład jeśli bieżącym zbiorem stanów jest {q1,q2}, pierwszym symbolem napisu jest a i mamy następujące przejścia: od q1 do q3 przez a, od q1 do q4 przez a, od q2 do q1 przez a, wówczas kolejnym bieżącym zbiorem stanów będzie {q1,q3,q4}. Innymi słowy: zamiast na stanach operujemy na zbiorach stanów.

Interfejs jak opisano w zadaniach #99 i #100, z tym, że tym razem trzeba uwzględnić epsilon-przejścia.