NFA к теореме Р. Е. Клини

Question

Вот мой НФА:

Вот моя попытка.

• Создать новый начальный и конечный узлы
• Затем удалите 2-й узел слева, который дает мне
• Затем удалите 2-й узел справа, который дает мне ab*a
• Затем удалите 2-й узел слева, который дает мне abb*b
• Затем удалите 2-й узел справа, который дает мне b+ab*a

Что приводит к abbb (b + ab a) *

Это правильный ответ?

Answer 1

Нет, вы не правы:(

_{Вам не нужно создавать начальное состояние. первое состояние с} - _{знак является начальным состоянием. Также} a,b _{ярлык означает} a _{или же} b _{но нет} ab

_{есть теорема, названная теоремой Ардена, будет очень полезна для преобразования NFA в RE}

Что такое регулярное выражение для этого NFA?

В тебе NFA начальная часть ДФА:

шаг 1:

(-) --a,b-->(1)   

значит (а + б)

шаг 2: следующий от стат 1 до 2, состояние примечания 2 принимает окончательное состояние (имея + знак).

(1) --b--->(2+)

Так вам нужно (a+b)b достичь конечного состояния.

Шаг 3: Тот, в котором вы находитесь в конечном состоянии 2, любое количество b принимаются (любое число означает один или несколько). Это из-за самоконтроля состояния 2 с этикеткой b,

Так, b* принято на гос-2.

шаг 4:

На самом деле есть две петли на state-2,

• один самоконтроля с этикеткой b как я описал в шаге-3. Его выражение b*

• второй цикл в состоянии-2 через состояние-3.
  выражение для второго цикла в состоянии-2: aa*b
  почему выражение aa*b ?

  так как:

            a-  
            ||               ====>  aa*b
            ▼|   
  (2+)--a-->(3) --b-->(2+)   
  

Таким образом, на шаге 3 и шаге 4 из-за цикла в состоянии-2 запуск может быть возвращен через b помечены или через aa*b ===> (b + aa*b)*

Итак, регулярное выражение для вашего NFA:

(a+b)b(b + aa*b)*