В этой статье я рассмотрю несколько методов преобразования автоматов в регулярные выражения. Метод удаления состояний Алгоритм, известный как метод исключения состояний, первоначально разработанный Бжозовским и Маккласки, работает непосредственно с автоматом. Он заключается в подавлении состояний в атомате, одно за другим, при преобразовании меток переходов, так что язык, распознаваемый получающимся автоматом, остается неизменным. На левой диаграмме показано состояние q, которое нужно подавить,...

Перед началом: Так как образовательная платформа нашего вуза не работает по непонятным мне причинам, я начну с самого конца. Будет много непонятных на первый взгляд определений, но, думаю, суть алгоритма уловить получится. Минимальная теория: Условимся называть Регулярное выражение - РВ. А конечный автомат - КА. Известно, что можно строить разные РВ и для этих РВ существуют свои КА. Существует теоремка как раз про это. Теорема Для любого РВ существует эквивалентный ему КА. ...