Kleene estrela

Em lógica matemática e ciência da computação, o Estrela de Kleene (ou Operador de Kleene ou Fechamento de Kleene) é uma operação unária, seja em conjuntos de strings ou em conjuntos de símbolos ou caracteres. Em matemática, é mais comumente conhecido como a construção monoide livre. A aplicação da estrela Kleene para um conjunto VNão. é escrito como V∗ ∗ Não. V^{*}}. É amplamente utilizado para expressões regulares, que é o contexto em que foi introduzido por Stephen Kleene para caracterizar certos autômatos, onde significa "zero ou mais repetições".

1. Se VNão. é um conjunto de strings, então V∗ ∗ Não. V^{*}} é definido como o menor superconjunto de VNão. que contém a string vazia ε ε - Sim. e é fechado sob a operação de concatenação de cadeia de caracteres.
2. Se VNão. é um conjunto de símbolos ou caracteres, então V∗ ∗ Não. V^{*}} é o conjunto de todas as cordas sobre símbolos em VNão., incluindo a string vazia ε ε - Sim..

O conjunto V∗ ∗ Não. V^{*}} também pode ser descrito como o conjunto contendo a string vazia e todas as cadeias de caracteres de comprimento finito que podem ser geradas concatenando elementos arbitrários de VNão., permitindo o uso do mesmo elemento várias vezes. Se VNão. é o conjunto vazio the ou o conjunto singleton (ε ε ?{displaystyle {varepsilon }}, então V∗ ∗ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(ε ε ?Não. V^{* Sim.; se VNão. é qualquer outro conjunto finito ou conjunto contável infinito, então V∗ ∗ Não. V^{*}} é um conjunto contável infinito. Como consequência, cada linguagem formal sobre um alfabeto finito ou contável infinito Σ Σ Não. Sim. é contável, uma vez que é um subconjunto do conjunto contável infinito Σ Σ ∗ ∗ Não. Sigma ^{*}}.

Os operadores são usados em regras de reescrita para gramáticas generativas.

Definição e notação

Dado um conjunto VNão.definição

V0= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(ε ε ?Não. V^{0}={varepsilon Sim. (a linguagem que consiste apenas na string vazia),

V1= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =VNão. V^{1}

e definir recursivamente o conjunto

VEu...+1= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(O quê?v:O quê?∈ ∈ VEu...ev∈ ∈ V?Não. V^{i+1}={wv:win V^{i}{text{ e }}vin V}}}} para cada 0}" xmlns="http://www.w3.org/1998/Math/MathML">Eu...>0- Sim.0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f49f2878fd68a89c3da37eb537198e887cf0293" style="vertical-align: -0.338ex; width:5.063ex; height:2.176ex;"/>.

Se VNão. é uma linguagem formal, então VEu...Não. V^{i}}, o Eu...Não.-o poder do conjunto VNão., é uma abreviatura para a concatenação do conjunto VNão. com si mesmo Eu...Não. tempos. Isso é, VEu...Não. V^{i}} pode ser entendido como o conjunto de todas as cordas que podem ser representadas como a concatenação de Eu...Não. strings in VNão..

A definição de Kleene star em VNão. o

V∗ ∗ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =⋃ ⋃ Eu...≥ ≥ 0VEu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =V0Telecomunicações Telecomunicações V1Telecomunicações Telecomunicações V2Telecomunicações Telecomunicações V3Telecomunicações Telecomunicações V4Telecomunicações Telecomunicações ⋯ ⋯ .Não. V^{*}=bigcup _{igeq 0}V^{i}=V^{0}cup V^{1}cup V^{2}cup V^{3}cup V^{4}cup cdots.}

Isso significa que o operador estrela Kleene é um operador indevido idempotente: (V∗ ∗ )∗ ∗ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =V∗ ∗ (V^{*})^{*}=V^{*}} para qualquer conjunto VNão. de caracteres ou caracteres, como (V∗ ∗ )Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =V∗ ∗ (V^{*})^{i}=V^{*}} para todos Eu...≥ ≥ 1- Sim..

Kleene plus

Em alguns estudos formais de linguagem (por exemplo, teoria da AFL) uma variação na operação estrela Kleene chamada de Kleene mais é usado. O Kleene mais omite o V0Não. V^{0}} termo na união acima. Em outras palavras, o Kleene mais sobre VNão. o

V+= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =⋃ ⋃ Eu...≥ ≥ 1VEu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =V1Telecomunicações Telecomunicações V2Telecomunicações Telecomunicações V3Telecomunicações Telecomunicações ⋯ ⋯ .Não. V^{+}=bigcup Gerenciamento de contas 1}V^{i}=V^{1}cup V^{2}cup V^{3}cup cdots.}

ou

V+= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =V∗ ∗ VNão. V^{+}=V^{*

Exemplos

Exemplo de estrela Kleene aplicada a um conjunto de strings:

Não.^* = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc",...}.

Exemplo de Kleene plus aplicado ao conjunto de caracteres:

"A", "b", "c"}⁺ = { "a", "b", "c", "aaa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab",...}.

Estrela Kleene aplicada ao mesmo conjunto de caracteres:

"A", "b", "c"}^* = { ε, "a", "b", "c", "aaa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab",...}.

Exemplo de estrela Kleene aplicada ao conjunto vazio:

∅^* - Não.

Exemplo de Kleene plus aplicado ao conjunto vazio:

∅⁺ ∅ ∅^* - Não.

onde a concatenação é um produto associativo e não comutativo.

Exemplo de Kleene plus e Kleene star aplicados ao conjunto singleton contendo a string vazia:

Se V= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(ε ε ?- Sim. Sim., então também VEu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(ε ε ?Não. V^{i}={varepsilon Sim. para cada Eu...Não., consequentemente V∗ ∗ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =V+= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(ε ε ?Não. V^{*}=V^{+}={varepsilon Sim..

Generalização

Strings formam um monóide com concatenação como a operação binária e ε o elemento identidade. A estrela Kleene é definida para qualquer monóide, não apenas para strings. Mais precisamente, seja (M, ⋅) um monóide, e S ⊆ M. Então S^* é o menor submonóide de M contendo S; isto é, S^* contém o elemento neutro de M, o conjunto S, e é tal que se x,y ∈ S^*, então x⋅y ∈ S^*.

Além disso, a estrela de Kleene é generalizada incluindo a operação * (e a união) na própria estrutura algébrica pela noção de semi-anel estrela completo.