Преобразование регулярных выражений a * b * + b * a * в конечные автоматы

Question

Вопрос заключался в том, чтобы дать регулярное выражение для всех As, появляющихся перед любым из B, или всех B, появляющихся перед любым из As.

Я получил регулярное выражение в виде * b * + b * a *.

Я не уверен, сделал ли я это правильно. Буду признателен за любую помощь, спасибо.

Answer 1

Если вам нужен недетерминированный конечный автомат c, вы можете использовать алгоритм, который выполняет преобразование на основе операций в регулярном выражении:

• + превращается в недетерминированный c ветвящиеся эпсилон-переходы
• конкатенация превращается в последовательный переход из состояния в состояние
• Звезда Клини превращается в петли

Ваш NDA будет выглядеть примерно так:

        a        b
        ^        ^
q0--e-->q1--e-->q2
 |
 e
 |
 V
q4--e-->q5
v      v
b      a

Если вы хотите определить c конечный автомат, вы можете определить не определенный c, используя известный алгоритм. В противном случае мы можем запустить Myhill-Nerode в обратном порядке, чтобы найти классы эквивалентности по отношению неразличимости; это даст нам состояния минимального DFA.

• e может сопровождаться любой строкой в ​​L, и на нашем языке; этот класс [e] соответствует начальному состоянию q ₀ , которое принимает
• a, за которым может следовать только a b ; a находится в языке, поэтому класс [a] соответствует принимающему состоянию q ₁
• b, за которым может следовать только b a ; b на языке, поэтому класс [b] соответствует принимающему состоянию q ₂
• ab, за которым может следовать только b *; [ab], q, принятие
• ba может сопровождаться только *; [ба], q ₄ , принимая
• аба, баба не на языке и никогда не может быть исправлена; [aba], q ₅ , не принимает
• все остальные строки длины 3 неотличимы от уже увиденных строк; мы закончили

Итак, есть DFA с 6 состояниями - 1 начальное (q ₀ ), 5 принимающих и 1 мертвое (q ₅ ) - который принимает язык. Вы можете выяснить переходы следующим образом: каждое состояние достигается после любой строки, которая принадлежит его классу эквивалентности. Обратите внимание, что мертвое состояние q ₅ должно иметь две самопетли в качестве своих переходов.

Answer 2

Опишите своими словами, какие строки принимаются, затем опишите, какие строки принимаются после ввода a или b. Для каждого различного набора принятых строк, которые не идентичны, вы создаете состояние. Если набор принятых строк содержит пустую строку, то состояние является принимающим состоянием.

Набор принятых строк, принятых строк после ввода a и принятых строк после ввода b отличается, поэтому необходимо как минимум три состояния. (после a * b * следует b * a *).