b'\n_START_ARTICLE_\nLinguagem formal\n_START_PARAGRAPH_\nEntende-se por linguagem formal estudo de modelos matem\xc3\xa1ticos que possibilitam a especifica\xc3\xa7\xc3\xa3o e o reconhecimento de linguagens (no sentido amplo da palavra), suas classifica\xc3\xa7\xc3\xb5es, estruturas, propriedades, caracter\xc3\xadsticas e inter-relacionamentos ._NEWLINE_A import\xc3\xa2ncia dessa teoria na ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o \xc3\xa9 dupla: ela tanto apoia outros aspectos te\xc3\xb3ricos da ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o (decidibilidade, computabilidade, complexidade computacional, por exemplo), como fundamenta diversas aplica\xc3\xa7\xc3\xb5es computacionais tais como processamento de linguagens, reconhecimento de padr\xc3\xb5es, modelagem de sistemas._NEWLINE_Para definir o que \xc3\xa9 a teoria das linguagens formais \xc3\xa9 preciso definir o que \xc3\xa9 linguagem e o que \xc3\xa9 linguagem formal. Inicialmente, de maneira bastante informal, podemos definir uma linguagem como sendo uma forma de comunica\xc3\xa7\xc3\xa3o. Elaborando um pouco mais esta defini\xc3\xa7\xc3\xa3o, podemos definir uma linguagem como sendo "um conjunto de elementos (s\xc3\xadmbolos) e um conjunto de m\xc3\xa9todos (regras) para combinar estes elementos, usado e entendido por uma determinada comunidade". S\xc3\xa3o exemplos as "linguagens naturais" (ou idiomas), "linguagens de programa\xc3\xa7\xc3\xa3o" e os "protocolos de comunica\xc3\xa7\xc3\xa3o"._NEWLINE_Assim, podemos dizer que "linguagens formais" s\xc3\xa3o mecanismos formais para representa\xc3\xa7\xc3\xa3o e especifica\xc3\xa7\xc3\xa3o de linguagens, baseados na chamada "teoria da computa\xc3\xa7\xc3\xa3o". As representa\xc3\xa7\xc3\xb5es podem ser feitas por reconhecedores e geradores._NEWLINE_Os reconhecedores s\xc3\xa3o dispositivos formais que servem para verificar se uma frase pertence ou n\xc3\xa3o \xc3\xa0 determinada linguagem. S\xc3\xa3o os aut\xc3\xb4matos: aut\xc3\xb4matos finitos, aut\xc3\xb4matos de pilha e m\xc3\xa1quina de Turing. Os sistemas geradores s\xc3\xa3o dispositivos formais que permitem a gera\xc3\xa7\xc3\xa3o sistem\xc3\xa1tica de todas as frases de uma linguagem. Os principais sistemas geradores dispon\xc3\xadveis s\xc3\xa3o as gram\xc3\xa1ticas, onde se destacam as gram\xc3\xa1ticas de Chomsky. Ent\xc3\xa3o, linguagens formais podem ser representadas de maneira finita e precisa atrav\xc3\xa9s de sistemas com sustenta\xc3\xa7\xc3\xa3o matem\xc3\xa1tica.\n_START_SECTION_\nHist\xc3\xb3ria da linguagem n\xc3\xa3o formal\n_START_PARAGRAPH_\nAcredita-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"._NEWLINE_O sistema Semi-Thue de Axel Thue, que pode ser usado para reescrever cadeias, foi influente em gram\xc3\xa1ticas formais .\n_START_SECTION_\nPalavras sobre um alfabeto\n_START_PARAGRAPH_\nUm 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\xc3\xa9m podem ser infinitos, por exemplo, a l\xc3\xb3gica de primeira ordem \xc3\xa9 frequentemente expressa utilizando um alfabeto que, al\xc3\xa9m de s\xc3\xadmbolos tais como \xe2\x88\xa7, \xc2\xac \xe2\x88\x80 e, entre par\xc3\xaanteses, cont\xc3\xa9m muitos elementos infinitamente x 0, x 1, x 2, ..., que desempenham o papel de vari\xc3\xa1veis. Os elementos de um alfabeto s\xc3\xa3o chamados de suas letras._NEWLINE_Uma palavra sobre um alfabeto pode ser qualquer sequ\xc3\xaancia finita, ou cadeia de caracteres ou letras, que por vezes podem incluir espa\xc3\xa7os, e s\xc3\xa3o separados por caracteres de separa\xc3\xa7\xc3\xa3o de palavras especificadas. O conjunto de todas as palavras sobre um alfabeto \xce\xa3 \xc3\xa9 geralmente indicado por \xce\xa3 *(usando o fecho de Kleene). O comprimento de uma palavra \xc3\xa9 o n\xc3\xbamero de caracteres ou letras de que \xc3\xa9 composto. Para qualquer alfabeto s\xc3\xb3 h\xc3\xa1 uma palavra de comprimento 0, a palavra vazia, o que \xc3\xa9 muitas vezes denotado por e, \xce\xb5 ou \xce\xbb. Por concatena\xc3\xa7\xc3\xa3o pode-se combinar duas palavras para formar uma nova palavra, cujo comprimento \xc3\xa9 igual \xc3\xa0 soma dos comprimentos das palavras originais. O resultado da concatena\xc3\xa7\xc3\xa3o de uma palavra com a palavra vazia \xc3\xa9 a palavra original._NEWLINE_Em algumas aplica\xc3\xa7\xc3\xb5es, especialmente na l\xc3\xb3gica, o alfabeto \xc3\xa9 tamb\xc3\xa9m conhecido como o vocabul\xc3\xa1rio e as palavras s\xc3\xa3o conhecidas como f\xc3\xb3rmulas ou senten\xc3\xa7as, isso quebra a letra/palavra met\xc3\xa1fora e a substitui por uma palavra/senten\xc3\xa7a met\xc3\xa1fora.\n_START_SECTION_\nDefini\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nUma linguagem formal de L sobre um alfabeto \xce\xa3 \xc3\xa9 um subconjunto de \xce\xa3 *, isto \xc3\xa9, um conjunto de palavras sobre um alfabeto. Por vezes, os conjuntos de palavras s\xc3\xa3o agrupados em express\xc3\xb5es, que as regras e as constantes podem ser formuladas para a cria\xc3\xa7\xc3\xa3o de "express\xc3\xb5es bem formadas"._NEWLINE_Em ci\xc3\xaancia e matem\xc3\xa1tica de computador, que n\xc3\xa3o costumam lidar com linguagens naturais, o adjetivo "formal" \xc3\xa9 frequentemente omitido como redundante._NEWLINE_Enquanto a teoria da linguagem formal, geralmente se preocupa com linguagens formais que s\xc3\xa3o descritas por algumas regras sint\xc3\xa1ticas, a pr\xc3\xb3pria defini\xc3\xa7\xc3\xa3o do conceito de "linguagem formal" \xc3\xa9 apenas como mencionado acima: um (possivelmente infinito) conjunto de cadeias de tamanho finito, composto de um determinado alfabeto, nem mais nem menos. Na pr\xc3\xa1tica, h\xc3\xa1 muitas l\xc3\xadnguas que podem ser descritas pelas regras, tais como linguagens regulares e linguagens livres de contexto. A no\xc3\xa7\xc3\xa3o de uma gram\xc3\xa1tica formal pode estar mais perto do conceito intuitivo de uma "linguagem", que \xc3\xa9 descrita por regras sint\xc3\xa1ticas. Por um abuso de defini\xc3\xa7\xc3\xa3o, uma particular linguagem formal \xc3\xa9 muitas vezes considerada como sendo equipada com uma gram\xc3\xa1tica formal que a descreve.\n_START_SECTION_\nLinguagens de programa\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nUm compilador tem geralmente dois componentes distintos. Um analisador l\xc3\xa9xico, gerado por uma ferramenta como lex, que identifica os s\xc3\xadmbolos da gram\xc3\xa1tica da linguagem de programa\xc3\xa7\xc3\xa3o, por exemplo, identificadores ou palavras-chave, que s\xc3\xa3o eles pr\xc3\xb3prios expressos em uma linguagem formal mais simples, geralmente por meio de express\xc3\xb5es regulares. No n\xc3\xadvel conceitual mais b\xc3\xa1sico, um parser, geralmente gerado por um gerador de parser como yacc, tenta decidir se o programa fonte \xc3\xa9 v\xc3\xa1lido, isto \xc3\xa9, se ele pertence \xc3\xa0 linguagem de programa\xc3\xa7\xc3\xa3o para que o compilador foi constru\xc3\xaddo. Claro, compiladores fazem mais do que apenas analisar o c\xc3\xb3digo fonte, eles geralmente o traduzem em algum formato execut\xc3\xa1vel. Devido a isso, um analisador geralmente produz mais do que uma resposta sim / n\xc3\xa3o, normalmente uma \xc3\xa1rvore de sintaxe abstrata, que \xc3\xa9 usado por etapas subsequentes do compilador para, eventualmente, gerar um execut\xc3\xa1vel contendo o c\xc3\xb3digo de m\xc3\xa1quina que roda diretamente no hardware, ou algum c\xc3\xb3digo intermedi\xc3\xa1rio que requer uma m\xc3\xa1quina virtual para executar.\n_START_SECTION_\nTeorias formais, sistemas e provas\n_START_PARAGRAPH_\nNa l\xc3\xb3gica matem\xc3\xa1tica, uma teoria formal \xc3\xa9 um conjunto de senten\xc3\xa7as expressas em uma linguagem formal._NEWLINE_Um sistema formal (tamb\xc3\xa9m chamado de c\xc3\xa1lculo l\xc3\xb3gico, ou um sistema l\xc3\xb3gico) \xc3\xa9 constitu\xc3\xaddo por uma linguagem formal, juntamente com um sistema dedutivo (tamb\xc3\xa9m denominado aparato dedutivo). O sistema dedutivo pode consistir num conjunto de regras de transforma\xc3\xa7\xc3\xa3o que possam ser interpretados como regras v\xc3\xa1lidas de infer\xc3\xaancia ou um conjunto de axiomas, ou tem ambos. Um sistema formal \xc3\xa9 utilizado para derivar uma express\xc3\xa3o de uma ou mais outras express\xc3\xb5es. Embora uma linguagem formal possa ser identificada com as suas f\xc3\xb3rmulas, um sistema convencional pode n\xc3\xa3o ser igualmente identificado pelos seus teoremas. Dois sistemas formais  e  podem ter os mesmos teoremas e ainda diferirem em alguma significante prova te\xc3\xb3rica (uma f\xc3\xb3rmula A pode ser uma consequ\xc3\xaancia de uma f\xc3\xb3rmula sint\xc3\xa1tica B em um, mas n\xc3\xa3o no outro, por exemplo)._NEWLINE_A prova formal ou deriva\xc3\xa7\xc3\xa3o \xc3\xa9 uma sequ\xc3\xaancia finita de f\xc3\xb3rmulas bem formadas (que pode ser interpretado como proposi\xc3\xa7\xc3\xb5es), cada um dos quais \xc3\xa9 um axioma ou resulta das f\xc3\xb3rmulas anteriores na sequ\xc3\xaancia de uma regra de infer\xc3\xaancia. A \xc3\xbaltima frase da sequ\xc3\xaancia \xc3\xa9 um teorema de um sistema formal. Provas formais s\xc3\xa3o \xc3\xbateis porque os seus teoremas podem ser interpretados como proposi\xc3\xa7\xc3\xb5es verdadeiras.\n_START_SECTION_\nInterpreta\xc3\xa7\xc3\xb5es e modelos\n_START_PARAGRAPH_\nLinguagens formais s\xc3\xa3o totalmente sint\xc3\xa1ticas por natureza, mas podem ser dadas sem\xc3\xa2nticas que d\xc3\xa3o sentido aos elementos da linguagem. Por exemplo, em matem\xc3\xa1tica l\xc3\xb3gica, o conjunto de poss\xc3\xadveis f\xc3\xb3rmulas de uma l\xc3\xb3gica particular \xc3\xa9 uma linguagem formal, e uma interpreta\xc3\xa7\xc3\xa3o atribui um significado para cada uma das f\xc3\xb3rmulas, geralmente, um valor verdade._NEWLINE_O estudo das interpreta\xc3\xa7\xc3\xb5es de linguagens formais \xc3\xa9 chamado de sem\xc3\xa2ntica formal. Na l\xc3\xb3gica matem\xc3\xa1tica, esta \xc3\xa9 muitas vezes feito em termos de teoria dos modelos. Em teoria do modelo, os termos que ocorrem numa f\xc3\xb3rmula s\xc3\xa3o interpretados como estruturas matem\xc3\xa1ticas, e regras fixas de interpreta\xc3\xa7\xc3\xa3o de composi\xc3\xa7\xc3\xa3o determinam como o valor verdade da f\xc3\xb3rmula pode ser derivado da interpreta\xc3\xa7\xc3\xa3o de seus termos; um modelo para uma f\xc3\xb3rmula \xc3\xa9 uma interpreta\xc3\xa7\xc3\xa3o de termos tais que a f\xc3\xb3rmula se torne verdade.'