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 | 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 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 | 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]- ↑ 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