Почему регулярные выражения определяются с помощью операций объединения, конкатенации и звездочек?

Регулярная expresssion определяется рекурсивно

1. $a$ для некоторых - это регулярное выражение,$a \in \Sigma$
2. $\varepsilon$ - это регулярное выражение,
3. $\emptyset$ - это регулярное выражение,
4. $(R_1 \cup R_2)$ где и - регулярные выражения, регулярное выражение,$R_1$$R_2$
5. $(R_1 \circ R_2)$ где и - регулярные выражения, регулярное выражение,$R_1$$R_2$
6. $(R_1)^*$ где - это регулярное выражение.$R_1$

Это определение взято со страницы 64

Сипсер, Майкл. Введение в теорию вычислений, 3-е издание. Cengage Learning, 2012.

Теперь у меня есть следующие вопросы.

• Почему не определение содержит intersection, complementили reverseоперации?
• Если мы изменим 4-й элемент на , получим ли мы эквивалентное определение, то есть для каждого регулярного языка есть измененное регулярное выражение и наоборот?$R_1 \cap R_2$
• Я знаю, что это определение является полным и четко определенным, но почему оно предпочтительнее других эквивалентных, четко определенных и полных определений?

1) Если мы также позволяют пересечение и дополнение, то полученные выражения иногда называют расширенные регулярные выражения; поскольку обычные языки закрыты под логическими операциями, они ничего не получают. Это просто синтаксический сахар. Аналогичное заключение справедливо и для обратной операции. Частично причина, по которой в первом случае все другие операции не упоминаются, заключается в том, чтобы сделать определение как можно более простым, чтобы (индуктивные) доказательства не приходилось заботиться о многих случаях. Другая причина может заключаться в том, что если мы разрешаем определенные операции, а другие нет, то в некоторых случаях получаются очень разные (субрегулярные) языковые классы, например, если мы рассмотрим расширенное регулярное выражение без оператора звезды, то мы получим надлежащий подкласс регулярных , так называемые звездообразными бесплатно или апериодические языки см википедии: звезда свободного языка .

2) Если мы сохраним пункты 1. - 6., но просто изменим пункт 4. при использовании пересечения вместо объединения, мы получим надлежащий подкласс обычных языков. Например , мы уже не могли описать язык , поскольку это повлечет за собой объединение и (доказательство см ниже). Если мы допускаем комплементации, все меняется , как мы накидной обратно по законам де Моргана.{ a } { b $L = \{a,b\}$$\{a\}$$\{b\}$

3) Я частично ответил на это в 1), но что вы имеете в виду, когда говорите, что это определение предпочтительнее? Я знаю определения, где 2. опущено (как мы имеем 6., что ), или 3. опущено (как у нас есть )), или оба опущены; так что это не минимально возможное определение (оно также дает нам некоторый синтаксический сахар, поскольку у нас есть дополнительные символы для описания и ).∅ = L ( ¯ X ∗ { ε } $L(\emptyset^{\ast}) = \{\varepsilon\}$$\emptyset = L(\overline{ X^{\ast} }$$\{\varepsilon\}$$\emptyset$

EDIT : Мой первый вышеупомянутый комментарий в 2) был неправ, языками в индуктивном закрытии под , и делать провайдер блокирует не являются подмножествами для некоторых , например , рассмотрим . Тем не менее , мы имеем , что не может быть описано с помощью такого выражения. Я дам доказательство, а именно I доказательство , что если , для некоторого выражения с модифицированным 4 - й пунктом, а затем , если (и , следовательно ) доказательство идет по индукции по выражению* ∩ х * х ∈ Х L ( ∘ б ) = { Ь } L = { , Ь } L = L ( R ) X = { , Ь } ≠ Ь { , Ь } ⊆ L ⇒ б ∈ L . R L ( R 1$\circ$$^{\ast}$$\cap$$x^{\ast}$$x \in X$$L(a\circ b) = \{ab\}$$L = \{a,b\}$$L = L(R)$$X = \{a,b\}$$a\ne b$

$$\{a,b\} \subseteq L \Rightarrow ab \in L.$$ $R$ . Для базового случая он держит бессодержательно, теперь предположим , что имеет место для . Если и , то , следовательно , по предположению индукции мы имеем . Если , то , как мы должны иметь и или наоборот. Предположим, первый случай. Если , а затем путем индукции, следовательно ,L = L ( R 1 ∩ R 2 ) = L ( R 1 ) ∩ L ( R 2 ) { a , b } ⊆ L { a , b } ⊆ L ( R i ) , i = 1 , 2 a b ∈ L ( R 1 ) $L(R_1), L(R_2)$$L = L(R_1 \cap R_2) = L(R_1) \cap L(R_2)$$\{a,b\} \subseteq L$$\{a,b\} \subseteq L(R_i), i = 1,2${ , Ь } ⊆ L ( R 1 ∘ R 2 ) = L ( R 1 ) L ( R 2 ) = ⋅ & epsi ; = & epsi ; ⋅ ∈ L ( R 1 ) & epsi ; ∈ L ( R 2 ) b ∈ L ( R 1 ) $ab \in L(R_1) \cap L(R_2)$$\{a,b\} \subseteq L(R_1\circ R_2) = L(R_1)L(R_2)$$a = a\cdot \varepsilon = \varepsilon\cdot a$$a\in L(R_1)$$\varepsilon \in L(R_2)$$b \in L(R_1)$б = б ⋅ & epsi ; ∈ L ( R 1 ) L ( R 2 ) б ∈ L ( R 2 ) ⋅ б ∈ L ( R 2 ) L ( R 2 ) L ( R 1 ) L ( R 2 ) a , b ∈ $ab \in L(R_1)$$ab = ab\cdot \varepsilon \in L(R_1)L(R_2)$ . Теперь предположим , что , то мы имеем по определению . И, наконец , если , то и для некоторого . Если мы находим , по предположению индукции, поэтому предположим , но это дает , аналогичный либо или дает и предположение индукции дает$b \in L(R_2)$$a\cdot b \in L(R_2)L(R_2)$$L(R_1)L(R_2)$a ∈ L ( R 1 ) n b ∈ L ( R 2 ) m n , m > 0 n = m = 1 a b ∈ L ( R 1 ) n > 1 a ∈ L ( R 1 ) m = 1 m > 1 b ∈ L ( R $a,b \in L(R_1^{\ast})$$a \in L(R_1)^n$$b \in L(R_2)^m$$n,m > 0$$n = m = 1$$ab \in L(R_1)$$n > 1$$a \in L(R_1)$$m = 1$$m > 1$a b ∈ L ( R 1 ) ⊆ L ( R ∗ 1 ) $b \in L(R_1)$$ab \in L(R_1) \subseteq L(R_1^{\ast})$, $\square$

Замечание: один из наиболее часто используемых выводов: если , то или . Это следует какследовательно, и или и . В первом случае мы имеем и, следовательно, .u = a w = a 1 = | а | = | ты ж | = | ты | + | ш | | ты | = 0 | ш | = 1 | ты | = 1 | ш | = 0 u = ε a = $a = uw$$u = a$$w = a$$1 = |a| = |uw| = |u| + |w|$$|u| = 0$$|w| = 1$$|u| = 1$$|w| = 0$$u = \varepsilon$$a = w$

Технический отчет, в котором представлены регулярные языки, регулярные выражения и конечные автоматы, задает ваш вопрос на странице 70:

Читателю может возникнуть вопрос: почему мы выбрали три конкретные операции , E F и E ∗ F ?$E\vee F$$EF$$E*F$

(Вскоре после этого было отмечено, что $E^*$ является более удобным оператором, чем $E*F$ и эквивалентен по мощности. Поэтому в наши дни мы используем вместо него $E^*$ .)

Ответ занимает несколько страниц. Во-первых, отмечается, что нужно искать ответ в том, образуют ли полученные языки интересный класс и как они сравниваются с языками, описанными другими способами. На странице 72 отмечается, что отрицание и соединение избыточны: они не добавляют никакой выразительной силы. На странице 80 и далее доказано, что обычные языки - это в точности языки, распознаваемые конечными автоматами.

Другими словами: ответ Стефана можно смело считать окончательным, поскольку он уже был приведен в докладе, в котором впервые были представлены эти концепции.

Из этого отбора операторов (объединения, конкатенации и звезды) можно построить НКА с размером линейной к размеру выражения. С другой стороны, если вы добавите пересечение и комплементацию, размер эквивалентного автомата может привести к взрыву, не элементарно, который, как правило, не желательно.