Mam problemy z „opisywaniem każdego kroku” podczas tworzenia NFA z wyrażenia regularnego. Pytanie brzmi:

Konwertuj następujące wyrażenie regularne na niedeterministyczny automat ze stanem skończonym (NFA), wyraźnie opisując kroki algorytmu, którego używasz: (b | a) * b (a | b)

Zrobiłem prostą maszynę 3-stanową, ale to bardzo wiele z intuicji. To pytanie z poprzedniego egzaminu napisanego przez mojego wykładowcę, który również napisał następujące wyjaśnienie algorytmu Thompsona:http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

Czy każdy może wyjaśnić, jak „jasno opisać każdy krok”? Wydaje się, że to raczej zestaw podstawowych reguł niż algorytm z krokami do naśladowania.

Może jest jakiś algorytm, który gdzieś przeleciałem, ale jak dotąd stworzyłem je z domysłem.