Introdução à Teoria dos Compiladores/Linguagens Regulares e Autômatos Finitos

A linguagem regular pode ser descrita por :

• Autômatos finitos
• Gramáticas regulares
• Expressões regulares

Autômatos Finitos

Paradigma reconhecedor. Descrevem uma expressão regular. Podem ser classificados em:

Autômato Finito Determinístico: Representado pela quintupla ($\Sigma$,Q,$\delta$,q,F) que consite em:

• $\Sigma$: Alfabeto - Conjunto finito de símbolos de entrada
• Q: Conjunto finito de estados
• $\delta$: Função de transição ($\delta$: Q x $\Sigma \to$ Q)
• q: Estado inicial
• F: Conjunto de estados finais

Um autômato finito determinístico aceita uma cadeia de símbolos se após um estado inicial, mudando de estados por meio da função $\delta$ (que determina precisamente o próximo estado), consegue chegar à um estado final.

Regras:

• Todo estado deve conter uma e somente uma transição para cada símbolo do alfabeto.

Autômato Finito Não-Determinístico: Representado pela quintupla ($\Sigma$,Q,$\delta$,q,F), onde a função de transição $\delta$ pode conduzir à múltiplos estados ou até mesmo nenhum.

Regras:

• Não é necessário uma transição para cada símbolo do alfabeto;
• Pode haver várias transições partindo de um mesmo estado na leitura de um mesmo símbolo;
• Não é necessário mapear todas as possibilidades, mas somente o que valida a cadeia.

Gramáticas Regulares

Conhecida também como Tipo 3 da Hierarquia de Chomsky. Pode ser definida como gramática linear.

As gramáticas regulares caracterizam as linguagens regulares:

• Toda linguagem gerada por uma gramática regular é regular.

• Toda linguagem regular pode ser caracterizada por uma gramática linear a direita, e por uma gramática linear a esquerda.

Teorema 1: Se a linguagem L pode ser gerada por uma gramática regular, então L é regular.

Teorema 2: Se a linguagem L é regular, então L pode ser gerada por uma gramática linear a esquerda e por uma gramática linear a direita.

Expressões Regulares

Definição:

Trata-se de um paradigma gerador. Um modelo que denota qualquer linguagem regular de forma mais simples, verificando o conjunto de cadeias de símbolos permitidos na linguagem.

Aplicação:

• Sistemas de pesquisa de texto, geradores de analisadores léxicos.
• Algoritmos de reconhecimento de pouca complexidade, grande eficiência e de fácil implementação.
• Sistemas operacionais, protocolos, editores, compiladores.