Introdução à Teoria dos Compiladores/Linguagens Regulares e Autômatos Finitos
A linguagem regular pode ser descrita por [1][2][3][4]:
- Autômatos finitos
- Gramáticas regulares
- Expressões regulares
Autômatos Finitos
editarParadigma 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
editarConhecida 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
editarDefiniçã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- ↑ Roberto Claudino da Silva - http://www.claudino.unifei.edu.br/
- ↑ José Lucas Rangel - http://www.inf.puc-rio.br/~inf1302/
- ↑ http://teia.inf.ufrgs.br/cgi-bin/moore.pl?curso=LivroAnimado&estado=281
- ↑ Pedro Paulo Balage Filho - http://pet.icmc.usp.br/~pedrobalage/