Linguagem formal - Formal language

Estrutura da frase em inglês sintaticamente bem formada, embora sem sentido, "Idéias verdes incolores dormem furiosamente" ( exemplo histórico de Chomsky 1957).

Em lógica , matemática , ciência da computação e linguística , uma linguagem formal consiste em palavras cujas letras são tiradas de um alfabeto e são bem formadas de acordo com um conjunto específico de regras.

O alfabeto de uma linguagem formal consiste em símbolos, letras ou tokens que se concatenam em cadeias de caracteres da linguagem. Cada string concatenado a partir símbolos deste alfabeto é chamado uma palavra, e as palavras que pertencem a uma linguagem formal particular, às vezes são chamados palavras bem formadas ou fórmulas bem formadas . Uma linguagem formal é freqüentemente definida por meio de uma gramática formal , como uma gramática regular ou gramática livre de contexto , que consiste em suas regras de formação .

O campo da teoria da linguagem formal estuda principalmente os aspectos puramente sintáticos de tais linguagens - isto é, seus padrões estruturais internos. A teoria da linguagem formal surgiu da linguística, como forma de compreender as regularidades sintáticas das línguas naturais . Na ciência da computação, as linguagens formais são usadas, entre outras, como base para definir a gramática das linguagens de programação e versões formalizadas de subconjuntos de linguagens naturais em que as palavras da linguagem representam conceitos que estão associados a significados ou semânticas particulares . Na teoria da complexidade computacional , os problemas de decisão são normalmente definidos como linguagens formais e as classes de complexidade são definidas como os conjuntos de linguagens formais que podem ser analisados ​​por máquinas com poder computacional limitado. Na lógica e nos fundamentos da matemática , as linguagens formais são usadas para representar a sintaxe dos sistemas axiomáticos , e o formalismo matemático é a filosofia de que toda a matemática pode ser reduzida à manipulação sintática de linguagens formais dessa maneira.

História

O primeiro uso da linguagem formal é considerado o Begriffsschrift 1879 de Gottlob Frege , que significa "redação de conceitos", que descreve uma "linguagem formal, modelada na aritmética, para o pensamento puro".

O primeiro sistema semi-Thue de Axel Thue , que pode ser usado para reescrever strings, foi influente nas gramáticas formais .

Palavras sobre um alfabeto

Um alfabeto , no contexto das linguagens formais, pode ser qualquer conjunto , embora muitas vezes faça sentido usar um alfabeto no sentido usual da palavra ou, mais geralmente, um conjunto de caracteres como ASCII ou Unicode . Os elementos de um alfabeto são chamados de letras . Um alfabeto pode conter um número infinito de elementos; entretanto, a maioria das definições na teoria da linguagem formal especifica alfabetos com um número finito de elementos, e a maioria dos resultados se aplica apenas a eles.

Uma palavra sobre um alfabeto pode ser qualquer sequência finita (isto é, string ) de letras. O conjunto de todas as palavras sobre um alfabeto Σ é geralmente denotado por Σ * (usando a estrela de Kleene ). O comprimento de uma palavra é o número de letras que a compõem. Para qualquer alfabeto, há apenas uma palavra de comprimento 0, a palavra vazia , que geralmente é denotada por e, ε, λ ou mesmo Λ. Por 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 em lógica , o alfabeto também é conhecido como vocabulário e as palavras são conhecidas como fórmulas ou frases ; isso quebra a metáfora da letra / palavra e a substitui por uma metáfora da palavra / frase.

Definição

Uma linguagem formal L sobre um alfabeto Σ é um subconjunto de Σ * , ou seja, um conjunto de palavras sobre esse alfabeto. Às vezes, os conjuntos de palavras são agrupados em expressões, enquanto regras e restrições podem ser formuladas para a criação de 'expressões bem formadas'.

Em ciência da computação e matemática, que geralmente não lidam 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 definição real do conceito de "linguagem formal" é apenas como acima: um conjunto (possivelmente infinito) de strings de comprimento finito composto de um determinado alfabeto, nem mais nem menos. Na prática, existem muitas linguagens que podem ser descritas por regras, como linguagens regulares ou linguagens livres de contexto . A noção de uma gramática formal pode estar mais próxima do conceito intuitivo de uma "linguagem", descrita por regras sintáticas. Por um abuso da definição, uma linguagem formal particular é freqüentemente considerada como equipada com uma gramática formal que a descreve.

Exemplos

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

  • Cada corda não vazio que não contém "+" ou "=" e não começa com "0" está em  L .
  • A string "0" está em  L .
  • Uma seqüência contendo "=" está em  L se e somente se houver exatamente um "=", e separa duas cadeias válidas de  L .
  • Uma seqüência contendo "+", mas não "=" está em  L se e somente se todos os "+" na cadeia separa duas cadeias válidas de  L .
  • Nenhuma string está em  L além das implícitas nas regras anteriores.

De acordo com essas regras, a string "23 + 4 = 555" está em  L , mas a string "= 234 = +" não está. Essa linguagem formal expressa números naturais , adições bem formadas e igualdades de adição bem formadas, mas expressa apenas sua aparência (sua sintaxe ), não o que significam ( semântica ). Por exemplo, em nenhum lugar dessas regras há qualquer indicação de que "0" significa o número zero, "+" significa adição, "23 + 4 = 555" é falso, etc.

Construções

Para linguagens finitas, pode-se enumerar explicitamente todas as palavras bem formadas. Por exemplo, podemos descrever uma linguagem  L como apenas L  = {a, b, ab, cba}. O caso degenerado dessa construção é a linguagem vazia , que não contém nenhuma palavra ( L  =  ).

No entanto, mesmo em um alfabeto finito (não vazio) como Σ = {a, b}, há um número infinito de palavras de comprimento finito que podem ser potencialmente expressas: "a", "abb", "ababba", " aaababbbbaab ", .... Portanto, as linguagens formais são tipicamente infinitas, e descrever uma linguagem formal infinita não é tão simples quanto 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 sobre os números naturais e "a n " significa "a" repetido n vezes (este é o conjunto de palavras que consiste apenas no símbolo "a");
  • o conjunto de programas sintaticamente corretos em uma dada linguagem de programação (cuja sintaxe é geralmente definida por uma gramática livre de contexto );
  • o conjunto de entradas sobre as quais uma certa máquina de Turing pára; ou
  • o conjunto de strings máximas de caracteres ASCII alfanuméricos nesta linha, ou seja, o conjunto {the, set, of, maximal, strings, alfanumérico, ASCII, characters, on, this, line, i, e}.

Formalismos de especificação de linguagem

Linguagens formais são usadas como ferramentas em várias disciplinas. No entanto, a teoria da linguagem formal raramente se preocupa com linguagens particulares (exceto como exemplos), mas se preocupa principalmente com o estudo de vários tipos de formalismos para descrever linguagens. Por exemplo, um idioma pode ser dado como

As perguntas típicas feitas sobre tais formalismos incluem:

  • Qual é o seu poder expressivo? (O formalismo X pode descrever todas as linguagens que o formalismo Y pode descrever? Ele pode descrever outras linguagens?)
  • 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 linguagens, uma descrita no formalismo X e outra no formalismo Y , ou em X novamente, são realmente a mesma linguagem?).

Surpreendentemente, muitas vezes, a resposta a esses problemas de decisão é "isso não pode ser feito de jeito nenhum" ou "é extremamente caro" (com uma caracterização de quão caro). Portanto, a teoria da linguagem formal é uma área de aplicação principal da teoria da computabilidade e da teoria da complexidade . As linguagens formais podem ser classificadas na hierarquia de Chomsky com base no poder expressivo de sua gramática gerativa, bem como na complexidade de seu autômato de reconhecimento . Gramáticas livres de contexto e gramáticas regulares fornecem um bom meio-termo entre expressividade e facilidade de análise e são amplamente utilizadas em aplicações práticas.

Operações em idiomas

Certas operações em idiomas são comuns. Isso inclui as operações do conjunto padrão, como união, interseção e complemento. Outra classe de operação é a aplicação elementar de operações de string.

Exemplos: suponha que e sejam idiomas sobre algum alfabeto comum .

  • A concatenação consiste em todas as strings da forma onde é uma string de e é uma string de .
  • A interseção de e consiste em todas as strings contidas em ambas as línguas
  • O complemento de em relação a consiste em todas as cadeias de caracteres que não estão em .
  • A estrela de Kleene : o idioma que consiste em todas as palavras que são concatenações de zero ou mais palavras no idioma original;
  • Reversão :
    • Seja ε a palavra vazia, então , e
    • para cada palavra não vazia (onde estão os elementos de algum alfabeto), deixe ,
    • em seguida, para uma linguagem formal , .
  • Homomorfismo de cordas

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

Propriedades de fechamento de famílias de idiomas ( Op onde e estão na família de idiomas fornecida pela coluna). Depois de Hopcroft e Ullman.
Operação Regular DCFL CFL IND CSL recursivo
União sim Não sim sim sim sim sim
Interseção sim Não Não Não sim sim sim
Complemento sim sim Não Não sim sim Não
Concatenação sim Não sim sim sim sim sim
Estrela de Kleene sim Não sim sim sim sim sim
(String) homomorfismo sim Não sim sim Não Não sim
homomorfismo ε-free (string) sim Não sim sim sim sim sim
Substituição sim Não sim sim sim Não sim
Homomorfismo inverso sim sim sim sim sim sim sim
Reverter sim Não sim sim sim sim sim
Cruzamento com uma linguagem regular sim sim sim sim sim sim sim

Formulários

Linguagens de programação

Um compilador geralmente possui dois componentes distintos. Um analisador léxico , às vezes gerados por uma ferramenta como lex, identifica os sinais da gramática da linguagem de programação, por exemplo, identificadores ou palavras-chave , literais numéricos e cordas, sinais de pontuação e operadores, que são eles próprios especificado por uma linguagem formal mais simples, geralmente por meio de regulares expressões . No nível conceitual mais básico, um analisador , às vezes gerado por um gerador de analisador semelhante yacc, tenta decidir se o programa fonte é sintaticamente válido, isto é, se está bem formado em relação à gramática da linguagem de programação para a qual o compilador foi construído.

Obviamente, os compiladores fazem mais do que apenas analisar o código-fonte - eles geralmente o traduzem em algum formato executável. Por causa disso, um analisador geralmente produz mais do que uma resposta sim / não, normalmente uma árvore de sintaxe abstrata . Isso é usado por estágios subsequentes do compilador para, eventualmente, gerar um executável contendo código de máquina que é executado diretamente no hardware ou algum código intermediário que requer uma máquina virtual para ser executado.

Teorias, sistemas e provas formais

Este diagrama mostra as divisões sintáticas dentro de um sistema formal . As cadeias de símbolos podem ser amplamente divididas em fórmulas sem sentido e bem formadas . O conjunto de fórmulas bem formadas é dividido em teoremas e não teoremas.

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 sistema lógico ) consiste em uma linguagem formal junto com um aparato dedutivo (também chamado de sistema dedutivo ). O aparato dedutivo pode consistir em um conjunto de regras de transformação , que podem ser interpretadas como regras válidas de inferência, ou um conjunto de axiomas , ou ter ambos. Um sistema formal é usado para derivar uma expressão de uma ou mais outras expressões. Embora uma linguagem formal possa ser identificada com suas fórmulas, um sistema formal não pode ser identificado da mesma forma por seus teoremas. Dois sistemas formais e podem ter as mesmas teoremas e ainda diferem de alguma forma à prova de teórico significativa (uma fórmula A pode ser uma consequência de uma sintática fórmula B em um, mas não uma outra, por exemplo).

Uma prova formal ou derivação é uma sequência finita de fórmulas bem formadas (que podem ser interpretadas como sentenças ou proposições ), cada uma das quais é um axioma ou segue das fórmulas precedentes na sequência por uma regra de inferência . A última frase da sequência é um teorema de um sistema formal. As provas formais são úteis porque seus teoremas podem ser interpretados como proposições verdadeiras.

Interpretações e modelos

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

O estudo das interpretações de linguagens formais é chamado de semântica formal . Na lógica matemática, isso geralmente é feito em termos da teoria do modelo . Na teoria do modelo, os termos que ocorrem em uma fórmula são interpretados como objetos dentro de estruturas matemáticas , e regras de interpretação composicional fixas determinam como o valor de verdade da fórmula pode ser derivado da interpretação de seus termos; um modelo para uma fórmula é uma interpretação de termos de forma que a fórmula se torne verdadeira.

Veja também

Notas

Referências

Citações

Fontes

Trabalhos citados
Referências gerais

links externos