Дополнение регулярного выражения, как найти

Question

Дайте регулярное выражение для языка L над алфавитом {0,1}, дополнение которого представлено регулярным выражением 0*

Я думаю, что ответ 1^+, но я не могу доказать это, пожалуйста, помогите

Answer 1

Прежде всего, Даниэль прав, что ответ "все слова, которые содержат хотя бы один 1". Но как вы можете это доказать?

Дополнение к регулярному выражению легче всего построить с использованием конечного представления автоматизации. Смотрите следующее изображение:

В левом поле отображается DFA для 0*, Чтобы построить его дополнение, все, что вам нужно сделать, это сделать все неприемлемые состояния принимающими состояния и наоборот. Это сделано на правильном изображении.

Теперь вы на полпути, но теперь вам нужно построить регулярное выражение из него. Это наверняка объяснено в вашем учебнике или аналогичном, но если вы его не найдете, вот PDF-файл, описывающий алгоритм.

Используя предоставленный алгоритм с (A = состояние 1) и (F = состояние 2), вы получите:

R_11^0 = ɛ|0
R_12^0 = 1
R_21^0 = (empty set)
R_22^0 = ɛ|0|1

Переходя к R_ij^1, вы получите:

R_11^1 = (ɛ|0) | (ɛ|0)(ɛ|0)*(ɛ|0) = (ɛ|0)* = 0*
R_12^1 = 1 | (ɛ|0)(ɛ|0)*1 = 1 | 0+1 = 0*1
R_21^1 = (empty set) | (empty set)(ɛ|0)*(ɛ|0) = (empty set)
R_22^1 = (ɛ|0|1) | (empty set)(ɛ|0)*1 = (ɛ|0|1)

И последний этап:

R_11^2 = 0* | (0*1)(0|1)*(empty set) = 0*
R_12^2 = 0*1 | (0*1)(ɛ|0|1)*(ɛ|0|1) = (0*1)(0|1)* = 0*1(0|1)*   <------- !!! HERE !!!
R_21^2 = (empty set) | (ɛ|0|1)(ɛ|0|1)*(empty set) = (empty set)
R_22^2 = (ɛ|0|1) | (ɛ|0|1)(ɛ|0|1)*(ɛ|0|1) = (ɛ|0|1)

Теперь вы можете найти регулярное выражение, посмотрев на все результаты, которые имеют начальное состояние в качестве первого индекса и принимающее состояние в качестве последнего индекса. В нашем примере состояние 1 (A) является единственным начальным состоянием, а состояние 2 (F) является единственным принимающим состоянием, поэтому ваш результат R_12^2:

0*1(0|1)*

На простом английском это:

• Столько нулей, сколько хотите
• Один (!)
• И столько нулей или единиц, сколько вам нравится

Другими словами, это все слова, которые содержат хотя бы одно.

Answer 2

Дополнение к регулярному выражению можно определить, сделав NFA из регулярного выражения, а затем преобразовав его в DFA (если возможно, сделайте его минимальным DFA). Используйте теорему Ардена, чтобы найти регулярное выражение для не конечных состояний, и это ваше дополнение к языку.

Answer 3

Дополнение языка (^0*$) содержит пустое слово и все слова, состоящие только из нулей. Поэтому язык содержит все слова, не состоящие только из нулей, то есть содержащие хотя бы один. Следовательно, регулярное выражение для языка ^.*1.*$, Принимая во внимание алфавит и делая первый в регулярном выражении, это эквивалентно ^0*1(0|1)*$,