Estrela de Kleene
A estrela de Kleene , às vezes chamada de Kleene de fechamento ou fechamento iterativo é, na teoria da linguagem , um operador unário usado para descrever linguagens formais . O nome estrela vem da notação usada, um asterisco , e Kleene de Stephen Cole Kleene, que o introduziu.
A estrela de Kleene é um dos três operadores básicos usados para definir uma expressão regular , junto com a concatenação e a união de conjuntos .
Aplicado a um conjunto , resulta em linguagem , definida como:
X{\ displaystyle X}
X∗{\ displaystyle X ^ {*}}![X ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01924e6e5570e2631081fea6c6981b4872d3e04b)
- Se for um alfabeto , isto é, um conjunto de símbolos ou caracteres, então o conjunto de palavras terminou , incluindo a palavra vazia .X{\ displaystyle X}
X∗{\ displaystyle X ^ {*}}
X{\ displaystyle X}
ε{\ displaystyle \ varepsilon}![\ varejpsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
- Se for uma linguagem , então é a menor linguagem que a contém, que contém e que é estável por concatenação .X{\ displaystyle X}
X∗{\ displaystyle X ^ {*}}
ε{\ displaystyle \ varepsilon}![\ varejpsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
Exemplos
Para o alfabeto , temos
{no,b,vs}{\ displaystyle \ {a, b, c \}}![\{ABC\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75e9bc621ced3f02e87b1c40be37867929142bf4)
{no,b,vs}∗={ε,no,b,vs,nono,nob,novs,bno,bb,bvs,vsno,vsb,vsvs,nonono,...}{\ displaystyle \ {a, b, c \} ^ {*} = \ {\ varejpsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ ldots \}}![\ {a, b, c \} ^ {*} = \ {\ varepsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ ldots \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/043873f9c32f47897c270f7df86e580f24464d30)
Para a parte composta pelas duas palavras e sobre o alfabeto , obtemos
X={nono,b}{\ displaystyle X = \ {aa, b \}}
nono{\ displaystyle aa}
b{\ displaystyle b}
{no,b}{\ displaystyle \ {a, b \}}![\ {a, b \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8127b44bf0e5a64fdc9301e188852ab9b97a1fe8)
{nono,b}∗={ε,b,nono,bb,nonob,bnono,bbb,nononono,nonobb,bnonob,bbnono,bbbb,...}{\ displaystyle \ {aa, b \} ^ {*} = \ {\ varepsilon, b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, \ ldots \}}![\ {aa, b \} ^ {*} = \ {\ varepsilon, b, aa, bb, aab, baa, bbb, aaaa, aabb, baab, bbaa, bbbb, \ ldots \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edec0b8236f3980ea047b17c74e3b8ac74346ebe)
Definição
Chamamos estrela de Kleene uma parte de um monoid o submonoid gerado pelo . Este submonóide é observado . Como de costume para as operações de fechamento, pode ser definido de três maneiras equivalentes:
X{\ displaystyle X}
M{\ displaystyle M}
X{\ displaystyle X}
X∗{\ displaystyle X ^ {*}}![X ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01924e6e5570e2631081fea6c6981b4872d3e04b)
-
X∗{\ displaystyle X ^ {*}}
É a menor parte do recipiente e o elemento neutro e fechado para o funcionamento do .M{\ displaystyle M}
X{\ displaystyle X}
M{\ displaystyle M}
M{\ displaystyle M}![M](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
-
X∗{\ displaystyle X ^ {*}}
é a intersecção de todos os que contêm submonoids .M{\ displaystyle M}
X{\ displaystyle X}![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
-
X∗{\ displaystyle X ^ {*}}
é o conjunto de todos os produtos do formulário , para e .x1x2⋯xnão{\ displaystyle x_ {1} x_ {2} \ cdots x_ {n}}
não≥0{\ displaystyle n \ geq 0}
x1,x2,...,xnão∈X{\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X}![x_ {1}, x_ {2}, \ ldots, x_ {n} \ em X](https://wikimedia.org/api/rest_v1/media/math/render/svg/1de7ed4f897d271681a22cd47c68694e25955cf9)
Se for um conjunto gerador do monóide , temos em particular .
X{\ displaystyle X}
M{\ displaystyle M}
X∗=M{\ displaystyle X ^ {*} = M}![X ^ {*} = M](https://wikimedia.org/api/rest_v1/media/math/render/svg/fea4bb899d2eb205c340d96434875a8861052e8f)
Caso do monóide livre
No caso de um alfabeto , denotamos o conjunto de todas as palavras em . O conjunto é um monóide para a concatenação , e é gerado por (para ser bastante rigoroso, é gerado pelas palavras compostas por uma letra, que identificamos com as letras).
NO{\ displaystyle A}
NO∗{\ displaystyle A ^ {*}}
NO{\ displaystyle A}
NO∗{\ displaystyle A ^ {*}}
NO{\ displaystyle A}
NO∗{\ displaystyle A ^ {*}}![A ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44e23745a51c2c2d8d91fd98c1cf721573747ece)
Se faz parte de , então é um submonóide do qual pode ou não estar livre. É costume notar por todo
X{\ displaystyle X}
NO∗{\ displaystyle A ^ {*}}
X∗{\ displaystyle X ^ {*}}
NO∗{\ displaystyle A ^ {*}}
Xnão{\ displaystyle X ^ {n}}![X ^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/268db8293666fefd75cfb00513706171948edf09)
Xnão={x1x2⋯xnão∣x1,x2,...,xnão∈X}{\ displaystyle X ^ {n} = \ {x_ {1} x_ {2} \ cdots x_ {n} \ mid x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X \}}![X ^ {n} = \ {x_ {1} x_ {2} \ cdots x_ {n} \ mid x_ {1}, x_ {2}, \ ldots, x_ {n} \ em X \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0619e87825f65be6b1a2feb7859458815f916da8)
de todos os itens de produtos . Então temos a fórmula
não{\ displaystyle n}
X{\ displaystyle X}![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
X∗=⋃não≥0Xnão{\ displaystyle X ^ {*} = \ bigcup _ {n \ geq 0} X ^ {n}}![X ^ {*} = \ bigcup _ {{n \ geq 0}} X ^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0e766f13ec6a5ef2e0bd1ff059b3b7446c7dcc4c)
.
Se é um submonóide gerado livremente , ou seja, se cada palavra de
é produzida de forma única a partir de palavras de , dizemos que é um código ou que é uma base de .
X∗{\ displaystyle X ^ {*}}
X{\ displaystyle X}
X∗{\ displaystyle X ^ {*}}
X{\ displaystyle X}
X{\ displaystyle X}
X{\ displaystyle X}
X∗{\ displaystyle X ^ {*}}![X ^ {*}](https://wikimedia.org/api/rest_v1/media/math/render/svg/01924e6e5570e2631081fea6c6981b4872d3e04b)
Por exemplo, o conjunto é um código, e o conjunto não é um código porque a palavra tem ambas as fatorações
X={nono,b}{\ displaystyle X = \ {aa, b \}}
X={no,nob,bno}{\ displaystyle X = \ {a, ab, ba \}}
nobno{\ displaystyle aba}![aba](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfc6a0b7eaf6b60d8d3e6cdc5b75e057d9a1ed03)
aba = ab . a = a . ba .
Operator plus
O operador mais , também chamado de estrela adequada ou estrela positiva , é um operador análogo à estrela de Kleene. Associa-se com uma parte de uma meia-grupo do sub-meia-grupo gerado por , observou . Nós temos
X{\ displaystyle X}
M{\ displaystyle M}
X{\ displaystyle X}
X+{\ displaystyle X ^ {+}}![X ^ {+}](https://wikimedia.org/api/rest_v1/media/math/render/svg/18e0e7c566b554eafc1b5705551ac4e939074777)
X+=⋃não>0Xnão{\ displaystyle X ^ {+} = \ bigcup _ {n> 0} X ^ {n}}![X ^ {+} = \ bigcup _ {{n> 0}} X ^ {n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43656e0df731581e82b5c1ab344b8d3b2ee45b70)
.
Como de costume para a estrela, o operador mais pode ser definido de três maneiras equivalentes:
-
X+{\ displaystyle X ^ {+}}
é a menor parte do container e fechada para o funcionamento do .M{\ displaystyle M}
X{\ displaystyle X}
M{\ displaystyle M}![M](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
-
X+{\ displaystyle X ^ {+}}
é a interseção de todos os grupos contendo submetade .M{\ displaystyle M}
X{\ displaystyle X}![X](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
-
X+{\ displaystyle X ^ {+}}
é o conjunto de todos os produtos do formulário , para e .x1x2⋯xnão{\ displaystyle x_ {1} x_ {2} \ cdots x_ {n}}
não>0{\ displaystyle n> 0}
x1,x2,...,xnão∈X{\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n} \ in X}![x_ {1}, x_ {2}, \ ldots, x_ {n} \ em X](https://wikimedia.org/api/rest_v1/media/math/render/svg/1de7ed4f897d271681a22cd47c68694e25955cf9)
Em um monóide, temos as seguintes relações entre a estrela e o operador mais:
X∗=X+∪{ε}, X+=XX∗=X∗X.{\ displaystyle X ^ {*} = X ^ {+} \ cup \ {\ varepsilon \}, \ X ^ {+} = XX ^ {*} = X ^ {*} X.}![{\ displaystyle X ^ {*} = X ^ {+} \ cup \ {\ varepsilon \}, \ X ^ {+} = XX ^ {*} = X ^ {*} X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b47d86bdd3931b5bfb972fe26250f9fddbbb3ac6)
.
As relações entre a estrela e a estrela positiva têm sido objeto de inúmeras apresentações; um dos mais completos é de Brzozowski , Grant e Shallit
Repetição e complementação de estrelas
As duas operações em linguagens formais que são a estrela (positiva ou não) e a passagem para o complemento têm propriedades algébricas notáveis: a primeira é idempotente uma vez que para qualquer linguagem e a segunda é involutiva uma vez que na verdade o complemento do complemento de um idioma é o idioma inicial.
(eu∗)∗=eu∗{\ displaystyle (L ^ {*}) ^ {*} = L ^ {*}}
eu{\ displaystyle L}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
A repetição dessas duas operações, a partir de uma dada linguagem , não produz uma infinidade de linguagens, mas um número finito. Esse fenômeno, observado por David Peleg em 1984, deve ser colocado em relação a um resultado de topologia já antigo de Kuratowski , o teorema de fechamento / complementar de Kuratowski .
eu{\ displaystyle L}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
Para provar a afirmação, consideramos, portanto, as duas operações
eu↦eu∗{\ displaystyle L \ mapsto L ^ {*}}![{\ displaystyle L \ mapsto L ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a982d3902578c08ba60152adc47203627d2b018)
e
eu↦eu-{\ displaystyle L \ mapsto L ^ {-}}
estrela e complementação. Essas operações são escritas em notação pós-fixada. Temos em particular
eu∗∗=eu∗{\ displaystyle L ^ {**} = L ^ {*}}![{\ displaystyle L ^ {**} = L ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71dcb3f1e21a5cc9d31b3e60a2c1e8778a317b03)
(idempotência) e (involução).
eu--=eu{\ displaystyle L ^ {-} = L}![{\ displaystyle L ^ {-} = L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2cc01f4d8539b0b0910c773e411131d8441314a)
Uma série de operações pode, portanto, sempre ser simplificada pela substituição de operações iguais sucessivas, e somos levados de volta a uma alternância de estrelas e complementações. A proposição decorre da identidade
eu∗-∗-∗-∗=eu∗-∗{\ displaystyle L ^ {* - * - * - *} = L ^ {* - *}}![{\ displaystyle L ^ {* - * - * - *} = L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3603ed2c738fc35ad4eb4b48e454b8f6a3c036fd)
que diz que uma sequência de 8 operações pode ser substituída por uma sequência de apenas 4 operações (levando em consideração o fato de que uma sequência pode começar ou terminar com uma complementação).
Demonstração
Para provar esta fórmula, primeiro mostramos a inclusão
eu∗-∗-∗⊆eu∗(1){\ displaystyle L ^ {* - * - *} \ subseteq L ^ {*} \ qquad (1)}![{\ displaystyle L ^ {* - * - *} \ subseteq L ^ {*} \ qquad (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2235573b91ebda66118cca0e3701092ae47d227)
.
Esta inclusão é obtida a partir de
eu∗-⊆eu∗-∗{\ displaystyle L ^ {* -} \ subseteq L ^ {* - *}}![{\ displaystyle L ^ {* -} \ subseteq L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e40bda2935c790bac219ff1e6130f5340ecb7d2)
,
então, passando para o complementar:
eu∗--=eu∗⊇eu∗-∗-{\ displaystyle L ^ {* -} = L ^ {*} \ supseteq L ^ {* - * -}}![{\ displaystyle L ^ {* -} = L ^ {*} \ supseteq L ^ {* - * -}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4afa625b0d7b11955f93492775259b5f509c54a)
,
e finalmente, aplicando a estrela
eu∗∗=eu∗⊇eu∗-∗-∗{\ displaystyle L ^ {**} = L ^ {*} \ supseteq L ^ {* - * - *}}![{\ displaystyle L ^ {**} = L ^ {*} \ supseteq L ^ {* - * - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f98354dc28ba9715733f72475ad950ed7f9c1f1)
.
A equação (1) dá, aplicando o complemento e depois a estrela:
eu∗-∗-∗-∗⊇eu∗-∗{\ displaystyle L ^ {* - * - * - *} \ supseteq L ^ {* - *}}![{\ displaystyle L ^ {* - * - * - *} \ supseteq L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c79dbf973d406dd7f1abeb37eedcc262e209196)
.
Por outro lado, através da substituição por na equação (1), obtém-se:
eu∗-{\ displaystyle L ^ {* -}}
eu{\ displaystyle L}![eu](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
eu∗-∗-∗-∗⊆eu∗-∗{\ displaystyle L ^ {* - * - * - *} \ subseteq L ^ {* - *}}![{\ displaystyle L ^ {* - * - * - *} \ subseteq L ^ {* - *}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a59b9635e374aa75270b2546eda46792a0b3f6c)
.
As duas desigualdades fornecem o resultado desejado.
As extensões são apresentadas no artigo de Brzozowski, Grant e Shallit já citados.
Caso de linguagens racionais
As linguagens regulares ou regulares são descritas por expressões regulares , nas quais Kleene estrela está envolvida de uma forma essencial: é ela quem passou pelas linguagens infinitas. A construção correspondente em autômatos finitos determinísticos passa por uma etapa intermediária usando um autômato finito não determinístico . Se o autômato mínimo que reconhece a linguagem tem declarações, o autômato finito determinístico mínimo que reconhece pode, em princípio, aos estados. Ora, já se sabe há muito tempo que este número de estados é no máximo , e ainda, mais precisamente, no máximo , onde está o número de estados terminais que não são o estado inicial. Todo um conjunto de valores intermediários é possível.
eu{\ displaystyle L}
não{\ displaystyle n}
eu∗{\ displaystyle L ^ {*}}
2não{\ displaystyle 2 ^ {n}}
3/4⋅2não{\ displaystyle 3/4 \ cdot 2 ^ {n}}
2não-1+2não-1-k{\ displaystyle 2 ^ {n-1} + 2 ^ {n-1-k}}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Estrela de uma palavra
A família de linguagens formais obtida, a partir de linguagens que são a estrela de uma palavra, por operações de fechamento booleano, é uma família bastante restrita. Admite uma efetiva caracterização equacional, que permite decidir se uma dada língua pertence a esta família.
Notas e referências
-
Janusz Brzozowski , Elyot Grant e Jeffrey Shallit , “ Closures em linguagens formais e Kuratowski do teorema ”, International Journal of Fundamentos da Ciência da Computação , vol. 22, n o 02,2011, p. 301-321 ( ISSN 0129-0541 , DOI 10.1142 / S0129054111008052 , arXiv 0901.3761 )
-
David Peleg , “ Um fechamento generalizado e fenômeno do complemento, ” Discrete Mathematics , vol. 50,1984, p. 285-293 ( ISSN 0012-365X , DOI 10.1016 / 0012-365X (84) 90055-4 , ler online ).
-
Peleg 1984 , Lemma 3.1.
-
Matúš Palmovský, “ Kleene closure and state complexity ”, RAIRO-Theor. Inf. Appl. , vol. 50,2016, p. 251-261 ( DOI 10.1051 / ita / 2016024 ).
-
Laure Daviaud e Charles Paperman , “ Classes of languages generated by the Kleene star of a word ”, Information and Computation , vol. 262,2018, p. 90–109 ( ISSN 0890-5401 , DOI 10.1016 / j.ic.2018.07.002 ).
Bibliografia
- (pt) Stephen C. Kleene , "Representação de eventos em redes nervosas e autômatos finitos" , em Claude E. Shannon e John McCarthy (eds), Automata Studies , Princeton, Princeton University Press, col. "Annals of Mathematics Estudos" ( N O 34),1956, viii + 285 pág. ( ISBN 978-0691079165 ) , p. 3-41
- Jacky Akoka e Isabelle Comyn-Wattiau (editores), Enciclopédia de Computação e Sistemas de Informação , Paris, Vuibert ,2006, xxxv + 1941 p. ( ISBN 978-2-7117-4846-4 )
- Olivier Carton, Linguagens formais, computabilidade e complexidade: bacharelado e mestrado em matemática ou ciência da computação, opção ciência da computação da agregação da matemática , Paris, Vuibert ,2008, 237 p. ( ISBN 978-2-7117-2077-4 , apresentação online )
- Jacques Sakarovitch , Elementos da teoria dos autômatos , Vuibert ,2003, 816 p. ( ISBN 978-2-7117-4807-5 )
Veja também
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">