Linguagem formal

Imagem: Portuguese_eyes · BY-SA · Openverse

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". O sistema Semi-Thue de Axel Thue, que pode ser usado para reescrever cadeias, foi influente em gramáticas formais .

Imagem: User:RobinK · BY-SA · Openverse

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.

Imagem: Jefferson Carlos De Bragança · BY-SA · Openverse

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.

Imagem: Pedro Ribeiro Simões from Lisboa, Portugal · BY · Openverse

As seguintes regras descrevem uma linguagem L formal sobre o alfabeto Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}: 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.

Imagem: Vitor Oliveira from Torres Vedras, PORTUGAL · BY-SA · Openverse

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:

Imagem: Pedro Ribeiro Simões from Lisboa, Portugal · BY · Openverse

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 Perguntas típicas feitas sobre tais formalismos incluem: 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.

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. 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.