Discussão:Fecho de Kleene

Aplicabilidade do Fecho de Kleene

Faria algum sentido aplicar o operador num conjunto que não fosse uma linguagem formal ou um alfabeto? Se não, porque não manter a definição mais explícita? Sds, --Leonardo Stabile ^msg 05h42min de 6 de agosto de 2009 (UTC)

Olá Leonardo.

Sim, faz sentido sim. O Fecho de Kleene é um operador que pode ser aplicado a conjuntos de qualquer tipo, sem discriminação. Representando a concatenação de zero ou mais elementos deste conjunto. Inclusive, Linguagens formais e alfabetos são conjuntos.

Na minha opinião, o artigo precisa ser expandido pois o conceito está muito fechado a Teoria das Linguagens Formais e dos Autômatos (e isso se deve ao fato da Teoria dos Conjuntos estar "embutida" neste assunto).

Por exemplo, de forma estritamente matemática, poderíamos considerar o conjunto dos Números Naturais N como um caso especial do Fecho de Kleene sobre o conjunto dos algarismos:

$A=\left\{0,1,2,3,4,5,6,7,8,9\right\}\,\!$

$\mathbb {N} =A\cup A^{\star }=A^{+}$

Embora a concatenação pareça uma operação admissível apenas sobre cadeias de caracteres (veja que até este meu exemplo pode ser entendido como tal), é preciso entender bem o que é uma cadeia: uma cadeia é uma n-upla de símbolos (ênuplas, sequências, listas ou tuplas são palavras variantes do mesmo termo).

As n-uplas possuem diversas definições, embora a mais comum seja feita através da recursão de pares ordenados, mesmo assim, e de um modo bastante simplificado, pode-se dizer que elas diferem dos conjuntos apenas pelo fato de serem ordenadas e por admitirem valores repetidos. No entanto, se observarmos a definição formal, veremos que um par ordenado também é um conjunto, descrito da seguinte forma:

$12=\left(1,2\right)=\left\{1,\left\{1,2\right\}\right\}$

recursivamente temos:

$123=\left(1,2,3\right)=\left(1,\left(2,3\right)\right)=\left\{1,\left\{1,2\right\},\left\{\left\{1,2\right\},3\right\}\right\}$

e assim por diante.

O problema é que esta definição só é encontrada nas literaturas mais antigas ou que se aprofundam mais no assunto. Para não dificultar o entendimento, os livros mais novos partem da idéia que n-uplas e conjuntos são conceitos distintos, quando, na verdade, não são.

Bom, espero não ter sido inconveniente com toda essa discussão (acho que estou empolgado hoje, hehehe). Mas talvez até dê para adaptar algo que eu escrevi aqui para um artigo. :-)

Um abraço.--Diego Queiroz (discussão) 16h50min de 6 de agosto de 2009 (UTC)

Até aí tudo bem, em nenhum momento questionei que não se aplica a conjuntos. O assunto está especializado em linguagens formais justamente por ali encontrar sua origem, aplicabilidade. Por exemplo, aquele conjunto A que demonstrou é um perfeito alfabeto, chamá-lo assim depende somente do contexto. Alfabeto não é o mesmo que caractere, a definição antiga não deixava entender se aplicar somente a cadeias de caracteres. Nada contra expandir o artigo, mas esse contexto então deve estar explícito. A definição anterior deveria ser adaptada. Algo como "(...) no contexto de liguagens formais, a operação é aplicada em linguagens ou alfabetos (...)". --Leonardo Stabile ^msg 22h15min de 8 de agosto de 2009 (UTC)

Olá novamente Leaonardo.

Realmente, você me deixou com uma pulga atrás da orelha. De fato, como você mesmo disse, um alfabeto não é o mesmo que um caractere, mas deve-se levar em consideração que, em expressões regulares, vários autores (veja Sipser M., Lewis H. e Papadimitriou C.) interpretam um caractere como sendo uma cadeia, isto é, um conjunto contendo apenas um caractere e aplicam o Fecho de Kleene a este caractere isolado.

Até entendo que a aplicabilidade da operação esteja totalmente ligada à Linguagens Formais, mas acho que isso acontece da mesma forma que a Teoria dos Conjuntos está. Observe que o conceito do Fecho de Kleene nada tem a ver com reconhecedores de linguagens, computabilidade ou complexidade computacional. Concordo que é conveniente criar um tópico mostrando a importância do operador na Teoria da Computação, mas acho incorreto deixar explícito que sua funcionalidade é "limitada" a alguns tipos especiais de conjuntos (linguagens e alfabetos, neste caso), apenas porque a aplicabilidade mais comum é esta.

Um abraço.--Diego Queiroz (discussão) 04h35min de 9 de agosto de 2009 (UTC)

Por mim, essa definição (ou visão) de alfabeto está limitada, por si só ela já serviria para definir a operação. Mas de forma alguma está errado atualmente, no fim são todos conjuntos. Essa sugestão alternativa de se criar um tópico para a área me parece suficiente. Tentarei alguma coisa quando sobrar um tempo. --Leonardo Stabile ^msg 02h15min de 10 de agosto de 2009 (UTC)