Linguagem formal

Entende-se por Teoria das Linguagens Formais e dos Autômatos (LFA) o 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 é necessário 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 sentença 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 sentenças 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

A primeira linguagem formal é dita ser aquela usada por Gottlob Frege in sua Begriffsschrift (1879), literalmente significando "o conceito da escrita", e que Frege descreveu como uma "linguagem formal do pensamento puro".

Palavras sobre um alfabeto

Um alfabeto, no contexto de 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. Alfabetos também podem ser infinitos, por exemplo, lógica de primeira ordem é muitas vezes expressa através de um alfabeto que, além de símbolos como ∧, ¬, ∀ e parênteses, contém elementos infinitos x0, x1, x2, ..., 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 letras. O conjunto de todas as palavras sobre um alfabeto Σ é geralmente denotada por Σ * (usando a estrela Kleene). Para qualquer alfabeto só há uma palavra de comprimento 0, a palavra vazia, que é frequentemente denotado por e, ε ou λ. Pela concatenação pode-se combinar duas palavras para formar uma nova palavra, cujo comprimento é a 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 conhecidos como fórmulas ou sentenças; isto quebra a metáfora de letra/palavra e a substitui pela metáfora palavra/sentença.

Definição

A linguagem formal L sobre um alfabeto Σ é um subconjunto de Σ*, isto é, um conjunto de palavras sobre esse alfabeto. Em ciência da computação e matemática, que não costuma lidar com as linguagemnaturais, o adjetivo "formal" é muitas vezes omitido por ser redundante. Enquanto a teoria da linguagem formal geralmente se preocupa com linguagens formais que são descritas por algumas regras sintáticas, a atual definição do conceito de "linguagem formal" é apenas como: O (possivelmente infinito) conjunto de sequências de comprimento finito, sem mais nem menos. Na prática, há muitas linguagemque podem ser descritas por regras, tais como linguagens regulares, ou lineares ou linguagens de contexto livre. A noção de uma gramática formal pode estar mais perto do conceito intuitivo de uma "linguagem", descrita por regras sintáticas. Por uma queixa da definição, uma determinada linguagemformal é frequentemente considerada como sendo equipada com uma gramática formal que a descreve.

Formalismos de especificação de linguagem

Teoria da linguagem formal, raramente se preocupa com linguagens particulares (exceto como exemplos), mas está preocupado principalmente com o estudo de vários tipos de formalismos para descrever linguagens. Por exemplo, uma líinguagem pode ser dado como

• as cadeias de caracteres geradas por alguma gramática formal;
• as cadeias descritas ou combinadas por uma expressão regular específica;
• as cadeias aceitas por alguns autômatos, tal como uma máquina de Turing ou autômato finito;
• as cadeias para que alguns procedimentos de decisão(um algoritmo que pede uma seqüência de perguntas sim / não relacionadas) produz a resposta SIM

Questões típicas sobre esses formalismos incluem :

• Qual é o seu poder de expressão? (Pode o formalismo X descrever cada linguagem que o formalismo Y pode descrever? Pode descrever outras línguas?)
• Qual é a sua reconhecibilidade? (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 línguas, uma descrita no formalismo X e uma no formalismo y , ou em X de novo, na verdade são a mesma língua?).

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

                                                   EXEMPLOS

LINGUAGEM INFORMAL : MÃE TÔ INDO LÁ NA PADARIA PRA COMPRAR PÃO

LINGUAGEM FORMAL : MÃE ESTOU INDO PARA A PADARIA COMPRAR PÃO

Aplicações

Linguagens de Programação

Um compilador tem dois componentes distintos. Um analisador léxico, gerado por uma ferramenta como o lex, que identifica os tokens da gramática da linguagem de programação, i.e. Identificadores ou palavras-chave, os quais são eles mesmos expressados em uma linguagem formal mais simples, usualmente por significados de expressões regulares. No nível conceitual mais básico, a análise, usualmente gerada por um gerador de análise como o yacc, tenta decidir se o programa-fonte é válido, isto é, se ele pertence à linguagem de programação para o qual o compilador foi construído. Obviamente, compiladores fazem mais do que somente analisar o código-fonte – eles geralmente o traduzem em algum formato executável. Em virtude disso, um analisador normalmente estabelece saídas que são mais do que respostas do tipo sim/não, tipicamente uma árvore sintática abstrata, a qual é usada por estados subsequentes do computador que eventuamente geral um executável contendo um código de máquina que roda diretamente no hardware, ou alguns códigos intermediários que requerem 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 um cálculo lógico, ou um sistema lógico) consiste de uma linguagem formal em conjunto com um aparato dedutivo (também chamado de um sistema dedutivo). O aparato dedutivo pode ser constituído de um conjunto de regras de transformação que pode ser interpretado como regras válidas de inferência ou um conjunto de axiomas, ou ambos. Um sistema formal é usado para derivar uma expressão de uma ou mais expressões. Apesar de uma linguagem formal poder ser identificada com as suas fórmulas, um sistema formal não pode ser também identificado por seus teoremas. Dois sistemas formais podem ter todos os mesmos teoremas e ainda assim diferem em alguma maneira prova-teórica significativa (uma fórmula A, pode ser uma conseqüência sintática de uma fórmula em um B, mas não outra, 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 segue a partir das fórmulas anteriores na seqüência por uma regra de inferência. A última frase na sequência é um teorema de um sistema formal. Provas formais são úteis porque seus teoremas podem ser interpretadas como proposições verdadeiras.

Interpretações e Modelos

Linguagens formais são inteiramente sintáticas na sua natureza, mas podem ser tidas como semânticas, as quais dão significado para elementos da linguagem. Por exemplo, na lógica matemática, 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 de interpretações de linguagens formais é chamado de semântica formal. Na lógica matemática, ele é geralmente feito em termos de teoria de modelo. Nessa teoria, os termos que aparecem em uma fórmula são interpretados como estruturas matemáticas, e regras de interpretações composicionais fixas determinam como o valor verdade de uma fórmula pode ser derivado de uma interpretação desses termos; um modelo para uma fórmula é uma interpretação de termos os quais fazem a fórmula se tornar verdadeira.

Ligações externas

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

Bibliografia

• COHEN, D. I. A. Introduction to Computer Theory. New York: John Wiley & Sons, 1997.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997.