регулярное выражение - максимум две пары последовательных

Question

Я беру курс по вычислениям, который также учит регулярным выражениям. Есть сложный вопрос, на который я не могу ответить.

Найти регулярное выражение для языка, который принимает слова, содержащие не более двух пар последовательных нулей. Алфавит состоит из 0 и 1.

Во-первых, я создал NFA языка, но не могу преобразовать его в GNFA (который позже будет преобразован в регулярное выражение). Как я могу найти этот регулярный экспрессин? С преобразованием в GNFA или без него?

Answer 1

(Так как это домашняя проблема, я предполагаю, что вы просто хотите получить достаточную помощь для начала, а не полностью проработанное решение?)

Ваш пробег может отличаться, но я не знаю't очень рекомендую попытаться преобразовать NFA в регулярное выражение.Эти два теоретически эквивалентны, и любой из них может быть преобразован в другой алгоритмически, но, по моему мнению, это не самый интуитивный способ построить любой из них.

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

• Нет пар последовательных нулей вообще;то есть за каждым нулем, кроме конца строки, должен стоять один.Таким образом, строка состоит из смешанной последовательности 1 и 01, за которой необязательно следует 0:

  (1|01)*(0|ε)
  

• Ровно одна пара последовательных нулей в концестроки.Это очень похоже на предыдущее:

  (1|01)*00
  

• Ровно одна пара последовательных нулей, не в конце строки - и, следовательно, обязательно следуетодним.Это также очень похоже на первый:

  (1|01)*001(1|01)*(0|ε)
  

Чтобы продолжить этот подход, вы должны расширить вышеприведенное для поддержки двух пар последовательных нулей;и, наконец, вы бы объединили все это в одно регулярное выражение.

Answer 2

(0 + 1) * 00 (0 + 1) * 00 (0 + 1) * + (0 + 1) * 000 (0 + 1) *

Answer 3

содержит не более двух пар последовательных 0

(1|01)*(00|ε)(1|10)*(00|ε)(1|10)*