NFA принять следующий язык - PullRequest
Новая
       97

NFA принять следующий язык

1 голос
/ 29 марта 2020

Мне нужно создать NFA (или DFA) для распознавания следующего языка: L = {w | w mod 3 = 1}. Поэтому я попытался сделать так, чтобы NFA распознал числа, делимые на 3, а затем просто добавил к ним 1, но этот подход намного сложнее, чем кажется (если не невозможен?). Мне удалось только сделать NFA, чтобы распознать числа, делимые на 3.

1 Ответ

1 голос
/ 30 марта 2020

Я буду считать, что w следует интерпретировать как десятичное представление (без начальных нулей) неотрицательного целого числа.

Учитывая это, мы можем использовать Myhill-Nerode для итеративного определения необходимых нам состояний:

  1. за пустой строкой может следовать любая строка в L, чтобы добраться до строки в L. Мы вызовем класс эквивалентности для этого [e]. Обратите внимание, что этот класс эквивалентности соответствует начальному состоянию минимального DFA для L (если он существует). Также обратите внимание, что начальное состояние не принимается, поскольку пустая строка не является допустимым десятичным представлением неотрицательного целого числа.

  2. за строкой 0 не может следовать никакая строка, чтобы получить строку в L ; это приводит к мертвому состоянию, соответствующему классу эквивалентности [0].

  3. строки 1, 4 и 7 находятся в L, поэтому они должны соответствовать новому состоянию. Мы будем называть класс эквивалентности для этих [1].

  4. строки 2, 5 и 8 не находятся в L; однако не все строки в L приводят их к строкам в L. Они должны соответствовать новому классу эквивалентности, который мы назовем [2].

  5. строки 3, 6 и 9 не являются в L; но за ними может следовать что угодно в L, чтобы получить строку в L. Это то же самое, что и пустая строка, поэтому нам не нужен новый класс или состояние эквивалентности: класс эквивалентности равен [e].

  6. можно проверить, что каждая десятичная строка с двумя числами git неотличима от некоторой десятичной строки с одним числом git выше. поэтому, новые классы или состояния эквивалентности не нужны.

Чтобы определить переходы, просто добавьте символ перехода к представительному элементу класса эквивалентности и посмотрите, к какому классу эквивалентности относится полученная строка: это будет то, где переход заканчивается. Например, есть переход с [e] на [0] в 0, с [e] на [1] в 1, et c.

, потому что 10 = 1 (mod 3), добавление новый di git до конца десятичной строки приведет к тому, что новое значение по модулю 3 будет суммой значения исходного числа по модулю 3 со значением нового di git по модулю 3: 

x = a (mod 3)
y = b (mod 3)
x * 10 = x * 1 (mod 3) since 10 = 1 (mod 3)
x . y = x * 10 + y = x * 1 + y = x + y (mod 3)

Заполнение переходов оставлено в качестве упражнения.

...