Construção de compiladores/Linguagens regulares e autômatos finitos

A linguagem regular pode ser descrita por [1][2][3]:

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

Autômatos Finitos

editar

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


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

  •  : Alfabeto - Conjunto finito de símbolos de entrada
  • Q: Conjunto finito de estados
  •  : Função de transição ( : Q x   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   (que determina precisamente o próximo estado), consegue chegar a 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 ( ,Q, ,q,F), onde a função de transição   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

editar

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

editar

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.

Referências

editar
  1. Roberto Claudino da Silva - http://www.claudino.unifei.edu.br/
  2. José Lucas Rangel - http://www.inf.puc-rio.br/~inf1302/
  3. http://teia.inf.ufrgs.br/cgi-bin/moore.pl?curso=LivroAnimado&estado=281