Регулярное выражение для DFA, которое принимает как пустую строку, так и другие строки

Для следующих DFA NFA

введите здесь описание изображения

Я произвел RE

(a + b)(ab)*

Однако затем я понял, что мой RE не принимает пустую строку, поскольку он принимает только строки, начинающиеся с a или b, однако DFA NFA также принимает пустую строку, поскольку начальное состояние — это принимающее государство.

Что такое действительный RE для этого DFA NFA? Я бы подумал что-то вроде

Ø + (a + b)(ab).*

но я сомневаюсь, что этот синтаксис принят.

ИЗМЕНИТЬ

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


regex dfa finite-automata nfa
person KOB    schedule 06.03.2017    source источник

Ответы (2)


arrow_upward
0
arrow_downward

(a + b)* будет ответом на то, что вы упомянули в заголовке вопроса. Знак * означает, что у вас может быть пустая строка. a+b означает, что вы можете выбрать a или b. Итак, наконец, вы можете выбрать a или b несколько раз.

person Bipin Paudel    schedule 06.03.2017
comment
Но (a+b)* примет строку aaa, а NFA — нет. - person KOB; 06.03.2017

arrow_upward
0
arrow_downward

Как насчет следующего выражения?

^(|[ab](ab)*)$

Это принимает либо пустую строку, либо последовательность ни одного или более раз ab, перед которой стоит a или b.

Но это зависит от точного диалекта регулярного выражения, если это решит вашу проблему.

person SQB    schedule 06.03.2017
comment
... или больше раз - взять один раз: ab. Эта строка не принимается NFA. a переходит от P0 к P1, но b не определено на P1. - person KOB; 06.03.2017
comment
@KOB Лучше? Вероятно, это не формальное регулярное выражение, которое, похоже, ищет OP. - person SQB; 06.03.2017