Lenguaige formal

De Biquipédia
Saltar pa: nabegaçon, percura
Question book.svg
Este aneixo ó seçon nó cita nanhue fuonte ó refréncia, l que cumpromete sue credibelidade (zde júnio de 2010).
Por fabor, melhore este artigo probidenciando fuontes fiables i andependientes, anserindo-las ne l cuorpo de l testo por meio de notas de rodapie. Ancontre fuontes: Googleamboras, libros, académicoScirusBing. Beija cumo referenciar i citar las fuontes.

Antende-se por Teorie de las Lenguaiges Formales i de ls Outómatos (LFA) l studo de modelos matemáticos que possibelitan la specificaçon i l reconhecimiento de lenguaiges (ne l sentido amplo de la palabra), sues classeficaçones, struturas, propiadades, caratelísticas i anter-relacionamientos.

L'amportança dessa teorie na Ciéncia de la Cumputaçon ye dupla: eilha tanto apóia outros aspetos teóricos de la Ciéncia de la Cumputaçon (decidibelidade, cumputabelidade, cumplexidade cumputacional, por eisemplo), cumo fundamenta dibersas aplicaçones cumputacionales tales cumo processamiento de lenguaiges, reconhecimiento de padrones, modelaige de sistemas.

Para defenir l que ye la Teorie de las Lenguaiges Formales ye necessairo defenir l que ye lenguaige i l que ye lenguaige formal. Einicialmente, de maneira bastante anformal, podemos defenir ua lenguaige cumo sendo ua forma de quemunicaçon. Eilaborando un pouco mais esta defeniçon, podemos defenir ua lenguaige cumo sendo "un cunjunto d'eilemientos (simblos) i un cunjunto de métodos (regras) para cumbinar estes eilemientos, ousado i antendido por ua detreminada quemunidade". San eisemplos las "lenguaiges naturales" (ó lénguas), "lenguaiges de porgramaçon" i ls "protocolos de quemunicaçon".

Assi, podemos dezir que "Lenguaiges formales" son macanismos formales para repersentaçon i specificaçon de lenguaiges, baseados na chamada "Teorie de la Cumputaçon". Las repersentaçones puoden ser feitas por reconhecedores i geradores. Ls reconhecedores son çpositibos formales que serben para berificar se ua sentença pertence ó nun a la detreminada lenguaige. San ls outómatos: outómatos fenitos, outómatos de pilha i Máquina de Turing. Ls sistemas geradores son çpositibos formales que permiten la geraçon sistemática de todas las sentenças dua lenguaige. Ls percipales sistemas geradores çponibles son las gramáticas, adonde se çtacan las gramáticas de Chomsky. Anton, lenguaiges formales puoden ser repersentadas de maneira fenita i percisa atrabeç de sistemas cun sustentaçon matemática.

Ligaçones sternas[eiditar | editar código-fonte]

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito