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

Fonte: Wikiversidade
Saltar para a navegação Saltar para a pesquisa

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

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

Autômatos Finitos[editar | editar código-fonte]

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 à 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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

  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
  4. Pedro Paulo Balage Filho - http://pet.icmc.usp.br/~pedrobalage/