Linguagens Formais: Gramáticas e Autômatos Finitos

Conceitos Fundamentais

Autômatos são reconhecedores de Linguagens Formais. As palavras de uma linguagem formal são geradas por uma gramática.

• Linguagem Formal: É um conjunto de palavras sobre um alfabeto.
• Gramática: Utilizada para gerar as palavras de uma linguagem formal.
• Reconhecedor (Autômato): Utilizado para reconhecer automaticamente as palavras de uma linguagem formal.
• Alfabeto: É um conjunto de símbolos finito e não vazio.
• Palavra: É uma sequência finita de símbolos de algum alfabeto.

Gramáticas Formais

Gramáticas são geradores de palavras de uma linguagem formal, representadas pela 4-upla:

G = (V, T, P, S)

• V: Conjunto de variáveis. São símbolos intermediários que não pertencem ao alfabeto da linguagem.
• T: Conjunto dos símbolos terminais, que pertencem ao alfabeto da linguagem.
• P: Conjunto de regras de produção, que têm como objetivo a geração das palavras pertencentes à linguagem.
• S: Símbolo inicial (S ∈ V), que dá início à geração da palavra.

Árvores de Derivação

São utilizadas para representar graficamente a derivação de palavras em compiladores, sendo uma forma de denotar as palavras de uma linguagem.

Hierarquia de Chomsky e Linguagens Regulares

A Hierarquia de Chomsky é a classificação de linguagens formais em 4 níveis, descrita em 1959 pelo linguista Noam Chomsky. Essa classificação é de grande interesse para a computação, principalmente porque os seus níveis são muito utilizados na descrição de linguagens de programação e na implementação de interpretadores e compiladores.

Uma linguagem formal é dita regular quando pode ser gerada por uma gramática regular e reconhecida por um autômato finito.

Uma gramática é regular se for uma Gramática Linear à Direita ou uma Gramática Linear à Esquerda.

Autômatos Finitos

Um autômato finito pode ser visto como uma máquina constituída por três partes:

• Fita: O dispositivo de entrada.
• Unidade de Controle: Reflete o estado atual da máquina e possui uma unidade de leitura (cabeça da fita) que:
  • Acessa uma célula da fita de cada vez.
  • Movimenta-se exclusivamente para a direita.
• Programa ou Função de Transição: Comanda as leituras e define o estado da máquina.

É formalmente representado por uma 5-upla:

M = (Σ, Q, δ, q0, F)

Onde:

• Σ: Alfabeto de símbolos de entrada.
• Q: Conjunto de estados possíveis.
• δ: Função programa ou função de transição (δ: Q x Σ → Q).
• q0: Estado inicial (q0 ∈ Q).
• F: Conjunto de estados finais (F ⊆ Q).