Я делаю рукописный лексер. Мне нужно нарисовать один недетерминированный конечный автомат, который содержит три конечных автомата, которые были сделаны ранее. Я сделал их для таких ключевых слов, как самолет, облако, взлетно-посадочные полосы. Мне нужна помощь, как построить общие автоматы для этих трех автоматов. Мне нужен пример, как это сделать? Если вы знаете, пожалуйста, помогите мне ??построить недетерминированные конечные автоматы
Нарисуйте самолет, облако и автомагистрали ВПП, оставив некоторое пространство перед стартовыми состояниями. Теперь стереть их первое состояние. Нарисуйте новое, сингл перед ним. Подключите его к «ирландским» автоматам с «a» переходом/ребер, «r» к «unway» и к «c» к «громкому». Вот и все. Готово.
Для более общего случая это сложнее: Сначала нарисуйте каждый из ваших автоматов (например, самолет, облако и взлетно-посадочную полосу), оставив некоторое пустое пространство туда, где они начинаются. Затем нарисуйте состояние до того места, где они начинаются, и подключите его к началу старта стартового состояния самолета, облака и стартового пула с помощью свободных краев. (Свободные ребра также называются ε-ребрами, ребрами epsilon, λ-ребрами или лямбдами).
Далее вы выполняете на них алгоритм построения подмножества, на котором вы можете найти видеоуроки для youtube. Также есть online subset construction algorithm tool, который преобразует недетерминированные конечные автоматы в детерминированные конечные автоматы (DFA) для вас. Этот процесс называется детерминизацией.
Как только у вас есть DFA, вы используете его для построения таблиц состояния, действия и поиска, которые управляют сканером. Это его собственная банда червей. Обычно люди используют генератор сканера, такой как Lex или Flex, для автоматизации этого. Аналогичный, удобный инструмент, который вы можете использовать онлайн, - the Online Scanner Generator. Вы можете использовать его, чтобы сделать график, предоставляя следующий вход:
airplane:airplane
cloud:cloud
runway:runway
Это даст вам DFA для этого, например, так: 