Por que expressões regulares são definidas com operações de união, concatenação e estrela?

Uma expressão regular é definida recursivamente como

1. $a$ para alguns$a \in \Sigma$ é uma expressão regular,
2. $\varepsilon$ é uma expressão regular,
3. $\emptyset$ é uma expressão regular,
4. $(R_1 \cup R_2)$ onde$R_1$ e$R_2$ são expressões regulares é uma expressão regular,
5. $(R_1 \circ R_2)$ onde$R_1$ e$R_2$ são expressões regulares é uma expressão regular,
6. $(R_1)^*$ onde$R_1$ é uma expressão regular é uma expressão regular.

Esta definição é retirada da página 64 de

Sipser, Michael. Introdução à Teoria da Computação, 3ª edição. Cengage Learning, 2012.

Agora, tenho as seguintes perguntas.

• Por que a definição não contém as operações intersection, complementou reverse?
• Se mudarmos o quarto item para $R_1 \cap R_2$ , não temos uma definição equivalente, ou seja, para cada idioma regular, há uma expressão regular modificado e vice-versa?
• Sei que essa definição é completa e bem definida, mas por que é preferível a outras definições equivalentes, bem definidas e completas?

1) Se também permitirmos a interseção e o complemento, as expressões resultantes às vezes são chamadas de expressões regulares estendidas; como os idiomas regulares são fechados em operações booleanas, nada é ganho por eles. É apenas açúcar sintático. Uma conclusão semelhante vale para a operação reversa. Parte da razão pela qual, em primeira instância, todas as outras operações não são mencionadas é o objetivo de manter a definição o mais simples possível, para que as provas (indutivas) não precisem ser tratadas em muitos casos. Outra causa pode ser que, se permitirmos certas operações, mas outras não, em alguns casos resultam classes de linguagem muito distintas (subregulares), por exemplo, se considerarmos a expressão regular estendida sem o operador estrela, obteremos uma subclasse apropriada das regulares , os chamados idiomas sem estrelas ou aperiódicos, consulte a Wikipedia: idioma sem estrelas .

2) Se mantivermos os itens 1. - 6. mas apenas alterar o item 4. ao usar a interseção em vez da união, obtemos uma subclasse apropriada dos idiomas regulares. Por exemplo, não podemos mais descrever o idioma pois isso envolveria a união de { a } e { b $L = \{a,b\}$$\{a\}$$\{b\}$ (veja a prova abaixo). Se permitirmos a complementação, as coisas mudam à medida que temos a união de volta pelas leis de DeMorgan.

3) Isso foi parcialmente respondido por mim em 1), mas o que você quer dizer quando diz que essa definição é preferida? Sei definições onde 2. for omitido (como temos por 6. que ), ou 3. for omitido (como temos ∅ = L ( ¯ X * )), ou ambos são omitidos ; portanto, essa não é a definição mínima possível (ela também nos fornece algum açúcar sintático, pois temos símbolos extras para descrever { ε } e ∅ ).$L(\emptyset^{\ast}) = \{\varepsilon\}$$\emptyset = L(\overline{ X^{\ast} }$$\{\varepsilon\}$$\emptyset$

EDIT : Meu primeiro comentário mencionado em 2) estava errado, os idiomas no fechamento indutivo em , ∗ e ∩ não são necessariamente subconjuntos de x ∗ para alguns x ∈ X , por exemplo, considere L ( a ∘ b ) = { a b } . No entanto, temos que L = { a , b } não poderia ser descrito por essa expressão. Eu darei uma prova, ou seja, eu prova que se L = L ( R $\circ$$^{\ast}$$\cap$$x^{\ast}$$x \in X$$L(a\circ b) = \{ab\}$$L = \{a,b\}$$L = L(R)$ para alguma expressão com o quarto item modificado, então se (e, portanto, a ≠ $X = \{a,b\}$$a\ne b$ ) A prova vai por indução da expressão R . Para o caso base que detém vacuously, agora supor que detém para L ( R 1 ) , L ( R 2 ) . Se L = L ( R 1

$$\{a,b\} \subseteq L \Rightarrow ab \in L.$$ $R$$L(R_1), L(R_2)$ e { um , b } ⊆ L , em seguida, { um , b } ⊆ L ( R i ) , i = 1 , 2 , portanto, por hipótese de indução que têm um b ∈ L ( R 1 ) ∩ L ( R 2 ) . E se$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$$ab \in L(R_1) \cap L(R_2)$ , em seguida, como um = um ⋅ £ = £ ⋅ um devemos ter uma ∈ L ( R 1 ) e £ ∈ L ( R 2 ) ou vice-versa. Suponha o primeiro caso. Se b ∈ L $\{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)$ , em seguida, um b ∈ L ( R 1 ) por hipótese de indução, por conseguinte, um b = um b ⋅ £ ∈ L ( R 1 ) L ( R 2 ) . Agora, suponha que b ∈ L ( R 2 ) , então temos um ⋅ b ∈ L ( R 2 ) L ( R 2 ) pela definição de$b \in L(R_1)$$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)$ . Finalmente, se a , b ∈ L ( R ∗ 1 ) , então a ∈ L ( R 1 ) n e b ∈ L ( R 2 ) m para alguns n , m > 0 . Se n = m = 1 , encontramos a b ∈ L ( $L(R_1)L(R_2)$$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$ pela hipótese de indução, suponha n > 1 , mas isso dá$ab \in L(R_1)$$n > 1$$a \in L(R_1)$, similar either $m = 1$ or $m > 1$ gives $b \in L(R_1)$ and the induction hypothesis gives $ab \in L(R_1) \subseteq L(R_1^{\ast})$. $\square$

$a = uw$$u = a$$w = a$. This follows as $1 = |a| = |uw| = |u| + |w|$, hence $|u| = 0$ and $|w| = 1$ or $|u| = 1$ and $|w| = 0$. In the first case we have $u = \varepsilon$ and hence $a = w$.

The technical report that introduced regular languages, regular expressions, and finite automata asks your question on page 70:

The question may occur to the reader, why did we select the particular three operations $E\vee F$, $EF$, and $E*F$?

(Soon afterwards, it was noted that $E^*$ is a more convenient operator than $E*F$ and equivalent in power. So these days, we use $E^*$ instead.)

The answer occupies several pages. First, it is remarked that the answer must be sought in whether the resulting languages form an interesting class and how they compare with languages described by other means. On page 72, it is remarked that negation and conjunction are redundant: they do not add any expressive power. On page 80 and further, it is proved that the regular languages are exactly the languages recognized by finite state machines.

In other words: Stefan's answer can safely be considered conclusive, as it was already given in the report that first introduced these concepts.

A partir dessa seleção de operadores (união, concatenação e estrela), é possível construir um NFA com um tamanho linear ao tamanho da expressão. Por outro lado, se você adicionar interseção e complementação, o tamanho do autômato equivalente pode explodir de maneira não elementar, o que geralmente não é desejável.