TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

Linguagens Formais Autômatos e Computabilidade

Por:   •  28/9/2015  •  Pesquisas Acadêmicas  •  3.570 Palavras (15 Páginas)  •  129 Visualizações

Página 1 de 15

Linguagens Formais, Autômatos e Computabilidade

- Linguagem: conjunto de palavras e regras gramaticais que permitem combinar palavras em sentenças sintaticamente corretas. A linguagem é formal quando pode ser representada por sustentação matemática.

A linguística formal compreende a representação da sintaxe (estrutura) e semântica (significado) das sentenças de uma linguagem.

- Alfabeto (vocabulário): conjunto finito de símbolos ou caracteres, podendo ser dígitos, letras, letras gregas, etc.

- Sentença (ou palavra definida sobre um alfabeto): qualquer sequência finita de símbolos do alfabeto. Ex: V = {0,1} → 001, 010011.

O tamanho da sentença é dado pelo número de símbolos que compõem a sentença. Ex: V = {a, b, c}; w = ab; |w| = 2.

- Sentença vazia: é aquela que não contem símbolos, tendo tamanho 0, representado por Ɛ. Ex: V* → conjunto de todas as sentenças compostas por símbolos de V, incluindo a sentença vazia → V+ = V* - (Ɛ). Ex: V = {0,1}; V* = {Ɛ, 0, 1, 00, 01, 10, 11, ...}; V+ = {0, 1, 00, 01, 10, 11, ...}.

- Linguagem (outra definição): qualquer conjunto de sentenças sobre um alfabeto, ou seja, uma linguagem L sobre um alfabeto V é um subconjunto de V*.

Conforme o número de sentenças, as linguagem se classificam em: finitas, vazias ou infinitas.

Uma linguagem pode ser representada:

  • Listando as palavras (só para linguagem finita)
  • Através da descrição algébrica. Ex: (anbncn | n>=1)
  • Definindo um algoritmo que determina se uma sentença pertence ou não à linguagem: Reconhecimento. Ex: autômato finito.
  • Definindo um mecanismo que gera sistematicamente as sentenças da linguagem. Ex: gramática.

Uma gramática serve para definir qual o subconjunto de sentenças que faz parte de uma determinada linguagem. Especifica uma linguagem potencialmente infinita de uma forma finita. Existem várias maneiras de representar a sintaxe das linguagens: BNF, diagrama de sintaxe, notação formal de gramática.

Ex: Backus Naur Form (BNF)

  • :: = ;
  • :: = BEGIN END
  • :: =

- Elementos:

  • Não-terminais ou variáveis =
  • Símbolos terminais = BEGIN; END
  • Produções = :: =
  • Símbolo inicial =

  • Notação Formal de Gramática

Uma gramática G é definida por uma quádrupla G = (N, T, P, S):

N → conjunto finito de não-terminais

T → conjunto finito de terminais

P → conjunto finitos de regras de produção

S → conjunto finito de

Obs: N ∩ T = Ø; V = N  T; S  N; P = {𝛼 𝛽 | 𝛼  V+ e 𝛽  V*}

Ex:

G = (N, T, P, I)

N = {I, D}

T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

P = {I → D, D → 0, D → 1, D → 2, D → 3, D → 4, D → 5, D → 6, D → 7, D → 8, D → 9)

  • Convenções

Para facilitar a compreensão das expressões, são adotadas, sempre que possível, as seguintes convenções:

  • N = {A, B, C, ..., T}  letras maiúsculas do início do alfabeto para símbolos não-terminais.
  • T = {a, b, c, ..., t}  letras minúsculas do início do alfabeto para símbolos terminais.
  • T* = {u,v, ...,z}  letras minúsculas do fim do alfabeto para sequências de terminais.
  • (N  T) = {𝛼, 𝛽, 𝛾, ...}  letras gregas para sequencias de variáveis e terminais.
  • N  T = {U, V, ..., Z}   letras maiúsculas do fim do alfabeto para um símbolo terminal ou não terminal.

- Derivação: é uma equação de substituição efetuada de acordo com as regras de produção da gramática. Representa-se esta operação pelo símbolo . Logo:

...

Baixar como (para membros premium)  txt (19.2 Kb)   pdf (372.6 Kb)   docx (30.8 Kb)  
Continuar por mais 14 páginas »
Disponível apenas no TrabalhosGratuitos.com