Как построить NFA, который принимает все двоичные строки, которые начинаются с 0? - PullRequest
Новая
       27

Как построить NFA, который принимает все двоичные строки, которые начинаются с 0?

0 голосов
/ 01 ноября 2019

Просто нужна помощь или подсказка, как построить MFA, который начинается с 0

1 Ответ

1 голос
/ 01 ноября 2019

Недетерминированный конечный автомат (NFA) для всех двоичных строк (Alphabet = {0, 1}), которые начинаются с нуля (0), может быть построен следующим образом.

Во-первых, мы знаем, что NFA требуется начальное состояние. Все НФА нуждаются в начальном состоянии. Назовите это q0.

Когда мы изначально входим в состояние q0, мы еще не видели требуемый 0;пустая строка не начинается с 0. Поэтому начальное состояние q0 не принимается. Пока у нашего NFA нет принимающих государств. Это означает, что он еще ничего не принимает. В нашем языке есть строки, поэтому мы знаем, что любой NFA должен иметь больше, чем просто начальное непринятое состояние q0. Вызовите другое состояние, которое нам известно, нам нужно q1.

Мы ввели q1, потому что нам нужно состояние принятия. Начиная с q0, если мы видим символ 0, мы видим строку (действительно, самую короткую строку) на целевом языке. Переход от q0 к символу 0 должен завершиться в некотором принимающем состоянии. Мы могли бы также закончить в q1;Итак, добавим переход f (q0, 0) = q1.

Наш DFA теперь принимает конечный язык, состоящий из строки длины одна 0;L (M) = {0}. Мы пока не принимаем ничего другого. Однако язык, который мы хотим принять, содержит более длинные строки. Поэтому нам нужно больше вещей в нашем NFA. Мы знаем, что то, что мы добавили до сих пор, является логически обязательным, и любой правильный NFA для языка будет делать то, что мы уже сделали (по модулю пустых, эпсилон- или лямбда-переходов, которые никогда не нужны).

В частности, мы хотим принять больше строк, начинающихся с 0. Все строки, начинающиеся с 0, получат переход, который мы добавили из q0 в q1. Итак, в состоянии q1 нам нужно принять в основном все, что мы видим с этого момента. Если мы видим следующий 0, нам нужно приземлиться в принимающем состоянии;и если мы увидим 1 рядом, нам нужно приземлиться в принимающем состоянии - и так далее, навсегда. Поскольку на данном этапе нам не нужно различать какие-либо типы строк, мы можем просто добавить переходы от q1 к себе на 0 или 1.

Наш NFA пока выглядит примерно так: 

               +----+
               |    | 0, 1
               V    |
----->q0----->q1----+
          0

Вы должны быть в состоянии убедить себя, что этот NFA принимает намеченный язык, потому что:

  • самая короткая строка, которую он принимает, это 0
  • , если он принимаетстрока x, она принимает строки x0 и x1
  • все строки, начинающиеся с 0, могут быть построены с использованием вышеуказанных правил
  • никакая строка, не начинающаяся с 0, не может быть построена с использованием вышеуказанных правил
...