fbpx
Wikipedia

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.

Índice

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 .

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.

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.

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.

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

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.

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 L1 e L2 são linguagens sobre algum alfabeto comum:
  • A concatenação L1L2 consiste de todas as cadeias da forma vw onde v é uma sequência de L1 e w é uma cadeia de L2.
  • A interseção L1L2 de L1 e L2 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 eR = e, e
    • para cada palavra não vazia w = x1xn sobre algum alfabeto, seja wR = xnx1,
    • então, para uma linguagem L formal, LR = {wR | wL}.
  • 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.

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 S F {\displaystyle {\mathcal {SF}}} e S F {\displaystyle {\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.

Referências

  1. Martin Davis (1995). «Influences of Mathematical Logic on Computer Science». In: Rolf Herken. . [S.l.]: Springer. p. 290. ISBN 978-3-211-82637-9

  1. Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome Herken1995

Linguagem formal
linguagem, formal, tipo, linguagem, normativa, idioma, língua, vigiar, editar, redirecionado, linguagens, formais, entende, linguagem, formal, estudo, modelos, matemáticos, possibilitam, especificação, reconhecimento, linguagens, sentido, amplo, palavra, suas,. Linguagem formal Tipo de linguagem normativa de um idioma Lingua Vigiar Editar Redirecionado de Linguagens formais Entende se por linguagem formal estudo de modelos matematicos que possibilitam a especificacao e o reconhecimento de linguagens no sentido amplo da palavra suas classificacoes estruturas propriedades caracteristicas e inter relacionamentos A importancia dessa teoria na ciencia da computacao e dupla ela tanto apoia outros aspectos teoricos da ciencia da computacao decidibilidade computabilidade complexidade computacional por exemplo como fundamenta diversas aplicacoes computacionais tais como processamento de linguagens reconhecimento de padroes modelagem de sistemas Para definir o que e a teoria das linguagens formais e preciso definir o que e linguagem e o que e linguagem formal Inicialmente de maneira bastante informal podemos definir uma linguagem como sendo uma forma de comunicacao Elaborando um pouco mais esta definicao podemos definir uma linguagem como sendo um conjunto de elementos simbolos e um conjunto de metodos regras para combinar estes elementos usado e entendido por uma determinada comunidade Sao exemplos as linguagens naturais ou idiomas linguagens de programacao e os protocolos de comunicacao Assim podemos dizer que linguagens formais sao mecanismos formais para representacao e especificacao de linguagens baseados na chamada teoria da computacao As representacoes podem ser feitas por reconhecedores e geradores Os reconhecedores sao dispositivos formais que servem para verificar se uma frase pertence ou nao a determinada linguagem Sao os automatos automatos finitos automatos de pilha e maquina de Turing Os sistemas geradores sao dispositivos formais que permitem a geracao sistematica de todas as frases de uma linguagem Os principais sistemas geradores disponiveis sao as gramaticas onde se destacam as gramaticas de Chomsky Entao linguagens formais podem ser representadas de maneira finita e precisa atraves de sistemas com sustentacao matematica Indice 1 Historia da linguagem nao formal 2 Palavras sobre um alfabeto 3 Definicao 4 Exemplos 5 Construcoes 6 Formalismos de especificacoes de linguagens 7 Operacoes em linguagens 8 Aplicacoes 8 1 Linguagens de programacao 8 2 Teorias formais sistemas e provas 8 2 1 Interpretacoes e modelos 9 Ver tambem 10 Referencias 11 Bibliografia 12 Ligacoes externasHistoria da linguagem nao formal EditarAcredita 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 gramaticas formais Palavras sobre um alfabeto EditarUm 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 tambem podem ser infinitos por exemplo a logica de primeira ordem e frequentemente expressa utilizando um alfabeto que alem de simbolos tais como e entre parenteses contem muitos elementos infinitamente x 0 x 1 x 2 que desempenham o papel de variaveis Os elementos de um alfabeto sao chamados de suas letras Uma palavra sobre um alfabeto pode ser qualquer sequencia finita ou cadeia de caracteres ou letras que por vezes podem incluir espacos e sao separados por caracteres de separacao de palavras especificadas O conjunto de todas as palavras sobre um alfabeto S e geralmente indicado por S usando o fecho de Kleene O comprimento de uma palavra e o numero de caracteres ou letras de que e composto Para qualquer alfabeto so ha uma palavra de comprimento 0 a palavra vazia o que e muitas vezes denotado por e e ou l Por concatenacao pode se combinar duas palavras para formar uma nova palavra cujo comprimento e igual a soma dos comprimentos das palavras originais O resultado da concatenacao de uma palavra com a palavra vazia e a palavra original Em algumas aplicacoes especialmente na logica o alfabeto e tambem conhecido como o vocabulario e as palavras sao conhecidas como formulas ou sentencas isso quebra a letra palavra metafora e a substitui por uma palavra sentenca metafora Definicao EditarUma linguagem formal de L sobre um alfabeto S e um subconjunto de S isto e um conjunto de palavras sobre um alfabeto Por vezes os conjuntos de palavras sao agrupados em expressoes que as regras e as constantes podem ser formuladas para a criacao de expressoes bem formadas Em ciencia e matematica de computador que nao costumam lidar com linguagens naturais o adjetivo formal e frequentemente omitido como redundante Enquanto a teoria da linguagem formal geralmente se preocupa com linguagens formais que sao descritas por algumas regras sintaticas a propria definicao do conceito de linguagem formal e apenas como mencionado acima um possivelmente infinito conjunto de cadeias de tamanho finito composto de um determinado alfabeto nem mais nem menos Na pratica ha muitas linguas que podem ser descritas pelas regras tais como linguagens regulares e linguagens livres de contexto A nocao de uma gramatica formal pode estar mais perto do conceito intuitivo de uma linguagem que e descrita por regras sintaticas Por um abuso de definicao uma particular linguagem formal e muitas vezes considerada como sendo equipada com uma gramatica formal que a descreve Exemplos EditarAs seguintes regras descrevem uma linguagem L formal sobre o alfabeto S 0 1 2 3 4 5 6 7 8 9 Cada cadeia nao vazia que nao contem ou e nao comeca com 0 esta em L Uma sequencia contendo esta em L se e somente se ha exatamente um e ela separa duas cadeias validas de L Uma sequencia contendo mas nao esta em L se e somente se todos os na cadeia separam duas cadeias validas de L Nenhuma cadeia esta em L que nao as sugeridas pelas regras anteriores Sob essas regras a cadeia 23 4 555 esta em L mas a cadeia 234 nao esta Esta linguagem formal expressa numeros naturais declaracoes adicao bem formadas e igualdades adicao bem formadas mas estas exprimem apenas o que elas se parecem sua sintaxe nao o que eles querem dizer semantica Por exemplo em nenhuma parte destas regras existe qualquer indicacao de que 0 significa o numero zero ou que significa adicao Construcoes EditarPara linguagens finitas uma pode explicitamente enumerar todas as palavras bem formadas Por exemplo pode se descrever uma lingua L somente como L a b b ABC O degenerado caso desta construcao e a linguagem vazia que nao contem nenhuma palavra L No entanto mesmo ao longo de um alfabeto nao vazio finito como S a b existem infinitamente muitas palavras a abb ababba aaababbbbaab Portanto as linguagens formais sao tipicamente infinitas e descrever uma linguagem formal infinita nao e tao simples como escrever L a b ab cba Aqui estao alguns exemplos de linguagens formais L S o conjunto de todas as palavras sobre S L a a n onde n varia ao longo dos numeros naturais e a significa a repetido n vezes isto e o conjunto de palavras que consiste apenas de o simbolo a o conjunto de programas sintaticamente corretos em uma determinada linguagem de programacao a sintaxe do que e normalmente definido por uma gramatica livre de contexto o conjunto de entradas nos quais uma determinada maquina de Turing para ou o conjunto de sequencias maximas de caracteres alfanumericos ASCII nesta linha i e o conjunto o conjunto de sequencias maximas cordas alfanumerico de caracteres alfanumericos ASCII nesta linha i e Formalismos de especificacoes de linguagens EditarA teoria da linguagem formal raramente se preocupa com determinadas linguas exceto como exemplos mas esta preocupada principalmente com o estudo de varios tipos de formalismos para descrever linguas Por exemplo uma linguagem pode ser dada como aquelas cadeias de caracteres geradas por alguma gramatica formal aquelas cadeias descritas ou acompanhadas por uma determinada expressao regular aquelas cadeias aceitas por alguns automatos como uma maquina de Turing ou automato de estados finito aquelas cadeias para qual algum procedimento de decisao um algoritmo que faz uma sequencia de perguntas relacionadas a sim nao produz a resposta SIM Perguntas tipicas feitas sobre tais formalismos incluem Qual e o seu poder de expressao Pode formalismo X descrever todas as linguas que o formalismo Y pode descrever Pode descrever outras linguas Qual e a sua reconhecidabilidade Quao dificil e decidir se uma determinada palavra pertence a uma linguagem descrita pelo formalismo X Qual e a sua comparabilidade Quao dificil e decidir se duas linguagens uma descrita no formalismo X e um Y no formalismo ou em X novamente sao na verdade a mesma lingua Surpreendentemente muitas vezes a resposta a esses problemas de decisao e nao pode ser feito de modo algum ou e extremamente custoso com uma caracterizacao de o quao custoso Portanto a teoria da linguagem formal e uma grande area de aplicacao da teoria da computabilidade e teoria da complexidade Linguagens formais podem ser classificadas na hierarquia de Chomsky com base no poder expressivo de sua gramatica geradora bem como a complexidade de seu automato reconhecedor Gramaticas livres de contexto e gramaticas regulares oferecem um bom compromisso entre expressividade e facilidade de analise e sao amplamente utilizadas em aplicacoes praticas Operacoes em linguagens EditarCertas operacoes em linguagens sao comuns Isto inclui as operacoes padrao de conjuntos tais como uniao intersecao e complemento Outra classe de operacao e a de aplicacao element wise de operacoes de cadeia Exemplos suponha que L1 e L2 sao linguagens sobre algum alfabeto comum A concatenacao L1L2 consiste de todas as cadeias da forma vw onde v e uma sequencia de L1 e w e uma cadeia de L2 A intersecao L1 L2 de L1 e L2 consiste de todas as cadeias que estao contidas em ambas as linguagens O complemento L de uma linguagem em relacao a um dado alfabeto consiste de todas as cadeias sobre o alfabeto que nao estao na lingua O fecho de Kleene a linguagem constituida de todas as palavras que sao concatenacoes de 0 ou mais palavras na lingua original Reversao Seja e a palavra vazia entao eR e e para cada palavra nao vazia w x1 xn sobre algum alfabeto seja wR xn x1 entao para uma linguagem L formal LR wR w L Homomorfismo de cadeia Tais operacoes de cadeia sao usadas para investigar as propriedades de fechamento das classes de linguagem A classe das linguagens e fechada sob uma operacao em particular quando a operacao aplicada as linguagens na classe sempre produz uma linguagem na mesma classe Por exemplo as linguagens livres de contexto sao conhecidas por serem fechadas sob uniao concatenacao e interseccao com linguagens regulares mas nao fechadas sob intersecao ou complemento A teoria dos trios e familias abstratas de linguagens estuda as propriedades mais comuns de fechamento de familias de linguagens em seu proprio direito Aplicacoes EditarLinguagens de programacao Editar Um compilador tem geralmente dois componentes distintos Um analisador lexico gerado por uma ferramenta como lex que identifica os simbolos da gramatica da linguagem de programacao por exemplo identificadores ou palavras chave que sao eles proprios expressos em uma linguagem formal mais simples geralmente por meio de expressoes regulares No nivel conceitual mais basico um parser geralmente gerado por um gerador de parser como yacc tenta decidir se o programa fonte e valido isto e se ele pertence a linguagem de programacao para que o compilador foi construido Claro compiladores fazem mais do que apenas analisar o codigo fonte eles geralmente o traduzem em algum formato executavel Devido a isso um analisador geralmente produz mais do que uma resposta sim nao normalmente uma arvore de sintaxe abstrata que e usado por etapas subsequentes do compilador para eventualmente gerar um executavel contendo o codigo de maquina que roda diretamente no hardware ou algum codigo intermediario que requer uma maquina virtual para executar Teorias formais sistemas e provas Editar Na logica matematica uma teoria formal e um conjunto de sentencas expressas em uma linguagem formal Um sistema formal tambem chamado de calculo logico ou um sistema logico e constituido por uma linguagem formal juntamente com um sistema dedutivo tambem denominado aparato dedutivo O sistema dedutivo pode consistir num conjunto de regras de transformacao que possam ser interpretados como regras validas de inferencia ou um conjunto de axiomas ou tem ambos Um sistema formal e utilizado para derivar uma expressao de uma ou mais outras expressoes Embora uma linguagem formal possa ser identificada com as suas formulas um sistema convencional pode nao ser igualmente identificado pelos seus teoremas Dois sistemas formais S F displaystyle mathcal SF e S F displaystyle mathcal SF podem ter os mesmos teoremas e ainda diferirem em alguma significante prova teorica uma formula A pode ser uma consequencia de uma formula sintatica B em um mas nao no outro por exemplo A prova formal ou derivacao e uma sequencia finita de formulas bem formadas que pode ser interpretado como proposicoes cada um dos quais e um axioma ou resulta das formulas anteriores na sequencia de uma regra de inferencia A ultima frase da sequencia e um teorema de um sistema formal Provas formais sao uteis porque os seus teoremas podem ser interpretados como proposicoes verdadeiras Interpretacoes e modelos Editar Ver artigos principais Semantica formal logica Interpretacao logica e Teoria dos modelos Linguagens formais sao totalmente sintaticas por natureza mas podem ser dadas semanticas que dao sentido aos elementos da linguagem Por exemplo em matematica logica o conjunto de possiveis formulas de uma logica particular e uma linguagem formal e uma interpretacao atribui um significado para cada uma das formulas geralmente um valor verdade O estudo das interpretacoes de linguagens formais e chamado de semantica formal Na logica matematica esta e muitas vezes feito em termos de teoria dos modelos Em teoria do modelo os termos que ocorrem numa formula sao interpretados como estruturas matematicas e regras fixas de interpretacao de composicao determinam como o valor verdade da formula pode ser derivado da interpretacao de seus termos um modelo para uma formula e uma interpretacao de termos tais que a formula se torne verdade Ver tambem EditarSintaxe Metodos formais Notacao matematica Vetor associativo Cadeia de caracteresReferencias 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 Bibliografia EditarA 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 Ligacoes externas Editarlaminas para curso de um semestre de duracao de linguagens formais a nivel de graduacaoTeoria de automatos linguagem formal e gramatica formalHierarquia Chomsky Gramatica Linguagem ReconhecedorTipo 0 Irrestrita Recursivamente enumeravel Maquina de Turing Recursiva Maquina de Turing que sempre paraTipo 1 Sensivel ao contexto Sensivel ao contexto Automato linearmente limitadoTipo 2 Livre de contexto Livre de contexto Automato com pilhaTipo 3 Regular Regular Automato finito 1 Erro de citacao Etiqueta lt ref gt invalida nao foi fornecido texto para as refs de nome Herken1995Obtida de https pt wikipedia org w index php title Linguagem formal amp oldid 60009122,