README.md

PyTomaton - инструмент для построения НКА, ДКА, и минимальных ДКА по регулярному выражению

Для запуска программы введите:

python3 main.py '[регулярное выражение]'

Никаких дополнительных зависимостей не требуется!

Пример работы:

>>>  python3 main.py '(A;B)*CA*'

Полученный по регулярному выражению НКА:
A | 2 -> [3]  |  11 -> [12]
B | 4 -> [5]
C | 8 -> [9]
EPSILON | 0 -> [1, 7]  |  1 -> [2, 4]  |  3 -> [6]  |  5 -> [6]  |  6 -> [1, 7]  |  7 -> [8]  |  9 -> [10]  |  10 -> [11, 13]  |  12 -> [11, 13]
Final states: [13]
--------------------
ДКА полученный по НКА (не минимальный): 
A | 0 -> [4]  |  1 -> [2]  |  2 -> [2]  |  3 -> [4]  |  4 -> [4]
B | 0 -> [3]  |  3 -> [3]  |  4 -> [3]
C | 0 -> [1]  |  3 -> [1]  |  4 -> [1]
Final states: [1, 2]
--------------------
Минимальный ДКА:
A | 0 -> [0]  |  1 -> [1]
B | 0 -> [0]
C | 0 -> [1]
Final states: [1]
--------------------

На данный момент поддерживаются операции:

1. * - Повторение символа 0 и более раз (A* => AAAA...AA, A*C=> C)
2. + - Аналогично *, но символ должен появится хотя бы один раз (A+ => A, A+ => AAA...AAA)
3. # - Обобщенная итерация. A#B = A(BA)*
4. ; - Альтернация (A;B => A, A;B => B, (A;B)* => ABABABABABABBB)
5. , - Конкатенация (A,B => AB). Ставится по умолчанию между всеми символами и группами слов и имеет наименьший приоритет (вместо (A,B)*,D,(F)* достаточно написать (AB)*DF*)