Linguagem formal

Entende-se por linguagem formal estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos .

A importância dessa teoria na ciência da computação é dupla: ela tanto apoia outros aspectos teóricos da ciência da computação (decidibilidade, computabilidade, complexidade computacional, por exemplo), como fundamenta diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem de sistemas.

Para definir o que é a teoria das linguagens formais é preciso definir o que é linguagem e o que é linguagem formal. Inicialmente, de maneira bastante informal, podemos definir uma linguagem como sendo uma forma de comunicação. Elaborando um pouco mais esta definição, podemos definir uma linguagem como sendo "um conjunto de elementos (símbolos) e um conjunto de métodos (regras) para combinar estes elementos, usado e entendido por uma determinada comunidade". São exemplos as "linguagens naturais" (ou idiomas), "linguagens de programação" e os "protocolos de comunicação".

Assim, podemos dizer que "linguagens formais" são mecanismos formais para representação e especificação de linguagens, baseados na chamada "teoria da computação". As representações podem ser feitas por reconhecedores e geradores. Os reconhecedores são dispositivos formais que servem para verificar se uma frase pertence ou não à determinada linguagem. São os autômatos: autômatos finitos, autômatos de pilha e máquina de Turing. Os sistemas geradores são dispositivos formais que permitem a geração sistemática de todas as frases de uma linguagem. Os principais sistemas geradores disponíveis são as gramáticas, onde se destacam as gramáticas de Chomsky. Então, linguagens formais podem ser representadas de maneira finita e precisa através de sistemas com sustentação matemática.

História da linguagem não formal

Acredita-se que a primeira linguagem formal seja a utilizada por Gottlob Frege em seu Begriffsschrift (1879), que literalmente significa "escrita conceito", e que Frege descreveu como uma "linguagem formal do pensamento puro".^[1]

O sistema Semi-Thue de Axel Thue, que pode ser usado para reescrever cadeias, foi influente em gramáticas formais .

Palavras sobre um alfabeto

Um alfabeto, no contexto das linguagens formais, pode ser qualquer conjunto, embora, muitas vezes, faz sentido usar um alfabeto no sentido usual da palavra, ou, mais geralmente, um conjunto de caracteres, como ASCII ou Unicode. Alfabetos também podem ser infinitos, por exemplo, a lógica de primeira ordem é frequentemente expressa utilizando um alfabeto que, além de símbolos tais como ∧, ¬ ∀ e, entre parênteses, contém muitos elementos infinitamente x 0, x 1, x 2, ..., que desempenham o papel de variáveis. Os elementos de um alfabeto são chamados de suas letras.

Uma palavra sobre um alfabeto pode ser qualquer sequência finita, ou cadeia de caracteres ou letras, que por vezes podem incluir espaços, e são separados por caracteres de separação de palavras especificadas. O conjunto de todas as palavras sobre um alfabeto Σ é geralmente indicado por Σ *(usando o fecho de Kleene). O comprimento de uma palavra é o número de caracteres ou letras de que é composto. Para qualquer alfabeto só há uma palavra de comprimento 0, a palavra vazia, o que é muitas vezes denotado por e, ε ou λ. Por concatenação pode-se combinar duas palavras para formar uma nova palavra, cujo comprimento é igual à soma dos comprimentos das palavras originais. O resultado da concatenação de uma palavra com a palavra vazia é a palavra original.

Em algumas aplicações, especialmente na lógica, o alfabeto é também conhecido como o vocabulário e as palavras são conhecidas como fórmulas ou sentenças, isso quebra a letra/palavra metáfora e a substitui por uma palavra/sentença metáfora.

Definição

Uma linguagem formal de L sobre um alfabeto Σ é um subconjunto de Σ *, isto é, um conjunto de palavras sobre um alfabeto. Por vezes, os conjuntos de palavras são agrupados em expressões, que as regras e as constantes podem ser formuladas para a criação de "expressões bem formadas".

Em ciência e matemática de computador, que não costumam lidar com linguagens naturais, o adjetivo "formal" é frequentemente omitido como redundante.

Enquanto a teoria da linguagem formal, geralmente se preocupa com linguagens formais que são descritas por algumas regras sintáticas, a própria definição do conceito de "linguagem formal" é apenas como mencionado acima: um (possivelmente infinito) conjunto de cadeias de tamanho finito, composto de um determinado alfabeto, nem mais nem menos. Na prática, há muitas línguas que podem ser descritas pelas regras, tais como linguagens regulares e linguagens livres de contexto. A noção de uma gramática formal pode estar mais perto do conceito intuitivo de uma "linguagem", que é descrita por regras sintáticas. Por um abuso de definição, uma particular linguagem formal é muitas vezes considerada como sendo equipada com uma gramática formal que a descreve.

Exemplos

As seguintes regras descrevem uma linguagem L formal sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:

Cada cadeia não vazia que não contém "+" ou "=" e não começa com "0" está em L.
Uma sequência contendo "=" está em L se e somente se há exatamente um "=", e ela separa duas cadeias válidas de L.
Uma sequência contendo "+", mas não "=" está em L se e somente se todos os "+" na cadeia separam duas cadeias válidas de L.
Nenhuma cadeia está em L que não as sugeridas pelas regras anteriores.

Sob essas regras, a cadeia "23 +4 = 555" está em L, mas a cadeia "= 234 = +" não está. Esta linguagem formal expressa números naturais, declarações adição bem formadas, e igualdades adição bem formadas, mas estas exprimem apenas o que elas se parecem (sua sintaxe), não o que eles querem dizer (semântica). Por exemplo, em nenhuma parte destas regras existe qualquer indicação de que "0" significa o número zero, ou que "+" significa adição.

Construções

Para linguagens finitas, uma pode explicitamente enumerar todas as palavras bem formadas. Por exemplo, pode-se descrever uma língua L somente como L = {"a", "b", "b", "ABC".} O degenerado caso desta construção é a linguagem vazia, que não contém nenhuma palavra (L = ∅ ). No entanto, mesmo ao longo de um alfabeto (não-vazio) finito, como Σ = {a, b} existem infinitamente muitas palavras: "a", "abb", "ababba", "aaababbbbaab", .... Portanto, as linguagens formais são tipicamente infinitas, e descrever uma linguagem formal infinita não é tão simples como escrever L = {"a", "b", "ab", "cba"}. Aqui estão alguns exemplos de linguagens formais:

L = Σ *, o conjunto de todas as palavras sobre Σ;
L = {"a"} * = {"a" n}, onde n varia ao longo dos números naturais e "a" significa "a" repetido n vezes (isto é, o conjunto de palavras que consiste apenas de o símbolo "a" );
o conjunto de programas sintaticamente corretos em uma determinada linguagem de programação (a sintaxe do que é normalmente definido por uma gramática livre de contexto);
o conjunto de entradas nos quais uma determinada máquina de Turing para, ou
o conjunto de sequências máximas de caracteres alfanuméricos ASCII nesta linha, i.e., o conjunto {"o", " conjunto ", "de" , " sequências” ,"máximas", "cordas", "alfanumérico", "de", "caracteres", " alfanuméricos", " ASCII ", " nesta", "linha", "i", "e"}.

Formalismos de especificações de linguagens

A teoria da linguagem formal, raramente se preocupa com determinadas línguas (exceto como exemplos), mas está preocupada principalmente com o estudo de vários tipos de formalismos para descrever línguas. Por exemplo, uma linguagem pode ser dada como

aquelas cadeias de caracteres geradas por alguma gramática formal;
aquelas cadeias descritas ou acompanhadas por uma determinada expressão regular;
aquelas cadeias aceitas por alguns autômatos, como uma máquina de Turing ou autômato de estados finito;
aquelas cadeias para qual algum procedimento de decisão (um algoritmo que faz uma sequência de perguntas relacionadas a sim / não) produz a resposta SIM.

Perguntas típicas feitas sobre tais formalismos incluem:

Qual é o seu poder de expressão? (Pode formalismo X descrever todas as línguas que o formalismo Y pode descrever? Pode descrever outras línguas?)
Qual é a sua reconhecidabilidade? (Quão difícil é decidir se uma determinada palavra pertence a uma linguagem descrita pelo formalismo X?)
Qual é a sua comparabilidade? (Quão difícil é decidir se duas linguagens, uma descrita no formalismo X e um Y no formalismo, ou em X novamente, são na verdade a mesma língua?).

Surpreendentemente, muitas vezes, a resposta a esses problemas de decisão é "não pode ser feito de modo algum", ou "é extremamente custoso" (com uma caracterização de o quão custoso). Portanto, a teoria da linguagem formal é uma grande área de aplicação da teoria da computabilidade e teoria da complexidade. Linguagens formais podem ser classificadas na hierarquia de Chomsky com base no poder expressivo de sua gramática geradora, bem como a complexidade de seu autômato reconhecedor. Gramáticas livres de contexto e gramáticas regulares oferecem um bom compromisso entre expressividade e facilidade de análise, e são amplamente utilizadas em aplicações práticas.

Operações em linguagens

Certas operações em linguagens são comuns. Isto inclui as operações padrão de conjuntos, tais como união, interseção e complemento. Outra classe de operação é a de aplicação element-wise de operações de cadeia.

Exemplos:

suponha que L₁ e L₂ são linguagens sobre algum alfabeto comum:

A concatenação L₁L₂ consiste de todas as cadeias da forma vw onde v é uma sequência de L₁ e w é uma cadeia de L₂.
A interseção L₁ ∩ L₂ de L₁ e L₂ consiste de todas as cadeias que estão contidas em ambas as linguagens
O complemento ¬L de uma linguagem em relação a um dado alfabeto consiste de todas as cadeias sobre o alfabeto que não estão na língua.
O fecho de Kleene: a linguagem constituída de todas as palavras que são concatenações de 0 ou mais palavras na língua original;
Reversão:
- Seja e a palavra vazia, então e^R = e, e
- para cada palavra não vazia w = x₁…x_n sobre algum alfabeto, seja w^R = x_n…x₁,
- então, para uma linguagem L formal, L^R = {w^R | w ∈ L}.
Homomorfismo de cadeia

Tais operações de cadeia são usadas para investigar as propriedades de fechamento das classes de linguagem. A classe das linguagens é fechada sob uma operação em particular quando a operação, aplicada as linguagens na classe, sempre produz uma linguagem na mesma classe. Por exemplo, as linguagens livres de contexto são conhecidas por serem fechadas sob união, concatenação e intersecção com linguagens regulares, mas não fechadas sob interseção ou complemento. A teoria dos trios e famílias abstratas de linguagens estuda as propriedades mais comuns de fechamento de famílias de linguagens em seu próprio direito.

Aplicações

Linguagens de programação

Um compilador tem geralmente dois componentes distintos. Um analisador léxico, gerado por uma ferramenta como lex, que identifica os símbolos da gramática da linguagem de programação, por exemplo, identificadores ou palavras-chave, que são eles próprios expressos em uma linguagem formal mais simples, geralmente por meio de expressões regulares. No nível conceitual mais básico, um parser, geralmente gerado por um gerador de parser como yacc, tenta decidir se o programa fonte é válido, isto é, se ele pertence à linguagem de programação para que o compilador foi construído. Claro, compiladores fazem mais do que apenas analisar o código fonte, eles geralmente o traduzem em algum formato executável. Devido a isso, um analisador geralmente produz mais do que uma resposta sim / não, normalmente uma árvore de sintaxe abstrata, que é usado por etapas subsequentes do compilador para, eventualmente, gerar um executável contendo o código de máquina que roda diretamente no hardware, ou algum código intermediário que requer uma máquina virtual para executar.

Teorias formais, sistemas e provas

Na lógica matemática, uma teoria formal é um conjunto de sentenças expressas em uma linguagem formal.

Um sistema formal (também chamado de cálculo lógico, ou um sistema lógico) é constituído por uma linguagem formal, juntamente com um sistema dedutivo (também denominado aparato dedutivo). O sistema dedutivo pode consistir num conjunto de regras de transformação que possam ser interpretados como regras válidas de inferência ou um conjunto de axiomas, ou tem ambos. Um sistema formal é utilizado para derivar uma expressão de uma ou mais outras expressões. Embora uma linguagem formal possa ser identificada com as suas fórmulas, um sistema convencional pode não ser igualmente identificado pelos seus teoremas. Dois sistemas formais ${\mathcal {SF}}$ e ${\mathcal {SF'}}$ podem ter os mesmos teoremas e ainda diferirem em alguma significante prova teórica (uma fórmula A pode ser uma consequência de uma fórmula sintática B em um, mas não no outro, por exemplo).

A prova formal ou derivação é uma sequência finita de fórmulas bem formadas (que pode ser interpretado como proposições), cada um dos quais é um axioma ou resulta das fórmulas anteriores na sequência de uma regra de inferência. A última frase da sequência é um teorema de um sistema formal. Provas formais são úteis porque os seus teoremas podem ser interpretados como proposições verdadeiras.

Interpretações e modelos

Linguagens formais são totalmente sintáticas por natureza, mas podem ser dadas semânticas que dão sentido aos elementos da linguagem. Por exemplo, em matemática lógica, o conjunto de possíveis fórmulas de uma lógica particular é uma linguagem formal, e uma interpretação atribui um significado para cada uma das fórmulas, geralmente, um valor verdade.

O estudo das interpretações de linguagens formais é chamado de semântica formal. Na lógica matemática, esta é muitas vezes feito em termos de teoria dos modelos. Em teoria do modelo, os termos que ocorrem numa fórmula são interpretados como estruturas matemáticas, e regras fixas de interpretação de composição determinam como o valor verdade da fórmula pode ser derivado da interpretação de seus termos; um modelo para uma fórmula é uma interpretação de termos tais que a fórmula se torne verdade.

Ver também

Referências

↑ Martin Davis (1995). «Influences of Mathematical Logic on Computer Science». In: Rolf Herken. The universal Turing machine: a half-century survey. [S.l.]: Springer. p. 290. ISBN 978-3-211-82637-9

Leituras adicionais

Catarina Dutilh Novaes (2012), Formal Languages in Logic. A Philosophical and Cognitive Analysis, ISBN 978-1-139-10801-0, Cambridge University Press, Zbl 1270.03003, doi:10.1017/CBO9781139108010, Wikidata Q122759208
A. G. Hamilton, Logic for Mathematicians, Cambridge University Press, 1978, ISBN 0-521-21838-1.
Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0-7204-2506-9.
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 81-7808-347-7.
Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic 3rd ed. New York: Springer Science+Business Media. ISBN 978-1-4419-1220-6. doi:10.1007/978-1-4419-1221-3 .
Grzegorz Rozenberg, Arto Salomaa, Handbook of Formal Languages: Volume I-III, Springer, 1997, ISBN 3-540-61486-9.
Patrick Suppes, Introduction to Logic, D. Van Nostrand, 1957, ISBN 0-442-08072-7.
Andries van Renssen, Gellish, a Generic Extensible Ontological Language, Delft University Press, 2005, ISBN 90-407-2597-4.

Ligações externas

lâminas para curso de um semestre de duração de linguagens formais a nível de graduação

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

[Herken1995-1] Martin Davis (1995). «Influences of Mathematical Logic on Computer Science». In: Rolf Herken. The universal Turing machine: a half-century survey. [S.l.]: Springer. p. 290. ISBN 978-3-211-82637-9

[1]