Discussão:Fecho de Kleene
Adicionar tópicoAspeto
Último comentário: 10 de agosto de 2009 de Leonardo.stabile no tópico Aplicabilidade do Fecho de Kleene
Aplicabilidade do Fecho de Kleene[editar código-fonte]
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:
- 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:
- recursivamente temos:
- 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)