Artigo Final

Autômatos Finitos e Expressões Regulares George Henrique Queiroga de Abrantes, Luiz Carlos de Coutinho Campos, Rafael Henrique dos Anjos Monteiro, Thiago Igor Oliveira de Medeiros [email protected], [email protected], [email protected], [email protected]

RESUMO Este trabalho se propõe a apresentar uma modelagem relacional entre os mecanismos reconhecedores de linguagens conhecidos como os Autômatos Finitos Determinísticos (AFD) e as Expressões Regulares (ER), bem como alcançando ainda a seara das Expressões Regulares Estendidas (ERE), presentes no mesmo universo dos supracitados conjuntos identificadores. Serão definidos os aspectos marcantes que caracterizam o perfil de uma expressão regular, de expressões regulares estendidas, assim como o de autômatos finitos determinísticos, fazendo uso, para tanto, de uma abordagem metodológica descritiva de seus elementos componentes empregados na construção de cada um. Verifica-se também a preocupação com a conversão entre os mencionados mecanismos. No decorrer do exame aqui abordado, observa-se o desenvolvimento de uma natural percepção voltada ao esclarecimento do melhor uso dos referidos recursos de reconhecimento, ensejando a consolidação de tamanho arcabouço em um cenário sintético-analítico enquadrando a colocação dos pontos favoráveis e desvantajosos de uns em relação aos demais, ou seja, será de escopo da conclusão deste material a exibição dos fundamentos positivos e negativos dos AFDs, ERs e EREs quanto a sua adoção para a melhor aplicabilidade. Palavras-chave: mecanismos, linguagens, autômatos finitos determinísticos, expressões regulares, expressões regulares estendidas, perfil, conversão, pontos favoráveis, fundamentos negativos. INTRODUÇÃO É de notório conhecimento o destaque atribuído à disciplina de Linguagens Formais. Presente nas mais diversas vertentes de cursos de Computação, bem como nas mais variadas faculdades, a referida cadeira absorveu traços indeléveis amplamente divulgados, e não seria à toa: a grande parte dos graduandos que tiveram contato com a matéria não poupou um antagonismo imediato, em função não apenas do constante rigor no emprego do formalismo característico, mas pesando ainda o alto grau de abstração requerido, o que automaticamente orienta os professores a incorporar desde ilustrações a cadeias de caracteres nos exemplos; por outro lado, a repercussão também se vale de um caráter deveras louvável, qual seja a importância pragmática do assunto.

O estudo das Linguagens Formais teve seu foco voltado para o desenvolvimento da Teoria das Linguagens Naturais a partir da década de 50, o que aos poucos foi sendo desviado, adquirindo um interesse peculiar nas Linguagens Artificiais, mas especificamente aquelas inerentes à Computação. Aos poucos se observou uma dedicação maior nas áreas de analisadores léxicos e sintáticos das linguagens de programação, além, por exemplo, da modelagem de circuitos lógicos e redes lógicas. Tamanho grau de valor e níveis de aplicabilidade demanda das pessoas envolvidas uma familiaridade particular com a gama de conceitos não diretamente ligados à realidade sensível, panorama esse melhor enxergado sob a óptica de uma bipolarização: vinculados a como fazer o melhor uso de suas potencialidades, através de um prisma comparativo exposto claramente na conclusão deste trabalho, encontra-se a conceituação acerca do que venha a ser um Autômato Finito, ou uma especificação deste, um Autômato Finito Determinístico, ou mesmo uma Expressão Regular, considerando-se ainda os formatos de conversão entre os mesmos, todos discutidos mais adiante. 1. Autômatos Finitos Pode-se dizer que este grupo de reconhecimento de seqüências envolve a dinâmica própria de uma máquina de estados modelando um comportamento (composto por estados, com suas respectivas transições e ações) baseado no armazenamento de informações ou dados que se deslocam de um estado para outro, sob a condição de específicas regras de validação para a ocorrência de cada transição, até alcançar o estado final, implicando no reconhecimento da entrada submetida ao sistema. Formalmente, autômato finito é uma quíntupla definida por M = sendo: • Q = conjunto finito de estados • Σ = alfabeto de entrada • s0 = estado inicial • δ = função de transição • F = conjunto de estados finais 1.1. Autômatos Finitos Determinísticos Esta modalidade de autômato consiste em certas regras restritivas das transições dos estados, onde, a partir do estado atual, quando é lido um símbolo, o sistema se encarrega de transitar para outro estado ou permanecer no mesmo, contanto que: as transições de um estado para outro obedeçam ao critério de singularidade, ou seja, há tão somente uma transição em cada estado para um

determinado símbolo, além de não se verificar transições vazias e constatar-se o alcance de um estado final unicamente a partir de um inicial. Vale lembrar ainda que outra categoria se mostra pertinente a um pequeno esclarecimento de distinção da acima destacada: os autômatos finitos não-determinísticos, os quais apresentam duas ou mais transições, porém agora para o mesmo símbolo. 2. Expressões Regulares Sabe-se que gramáticas do tipo três são apropriadas no momento em que se representa detalhes específicos de linguagens de programação, determinando, por exemplo , o formato de constantes, identificadores e palavras da linguagem. A expressão de uma gramática definidora de identificadores pode ser apresentada conforme o seguinte exemplo: G = ({letra, dígito}, {IDENT, REST}, P, IDENT). Deve-se considerar, continuando a demonstração, que P represente o conjunto de produções abaixo descrito: • •

IDENT -> letra | letra REST REST -> letra | dígito | letra REST | dígito REST

Assim, as Expressões Regulares são o veículo adequado para o estabelecimento de símbolos ou sentenças gerados por gramáticas do tipo três. Em consonância com o que acima foi disposto, torna-se imprescindível acrescentar que três são os operadores empregados em expressões regulares: concatenação, “|” e “*”. De acordo com o exemplo relacionado descrito há pouco, a expressão regular referente a um identificador é: letra(letra | digito)*. Salientar que as expressões regulares possuem um adendo por vezes mencionado como Expressão Regular Estendida (ERE) merece uma maior atenção, posto que a mesma é formada pelas unidades essenciais vistas nas expressões regulares básicas, contudo, adquire a qualidade de estendida em função da presença de um leque mais abrangente de alternativas de produções. 3. Conversões No intuito de promover uma melhor interação entre as ferramentas reconhecedoras até aqui descritas, dispõe-se a seguir um algoritmo responsável pela conversão de um AFD para uma ER, assim como de uma ER para um AFND (e deste para o AFD).

Figura 1 – Convertendo um AFD para uma ER § Remova um a um os estados do autômato, substituindo o estado removido por novas transições cujos rótulos são os das transições de todos os possíveis caminhos passando por aquele nó. § Verifique quais os possíveis caminhos que passam por aquele nó e crie novas transições ligando os estados restantes. § Em alguns momentos nós precisamos representar caminhos circulares usando a operação de fecho de Kleene e fazer parceiros intermediários. § Continue os passos até que sobre apenas um estado inicial e um estado final e escreva a expressão regular representando os laços com operações de fecho. Conversão de ER para AFND e, em seguida, para AFD – respectivamente, uso do Algoritmo de Thompson e depois Método da Construção de Subconjuntos Procedimento do Algoritmo de Thompson Passo I: dada a expressão regular sob análise (que se pretende converter), primeiro decompõe-se a mesma nas unidades básicas, isto é, os entes envolvidos serão chamados de “R1”,”R2”,...,”Rn” (caso a expressão regular seja composta por somente “a” e “b”, por exemplo, então R1=a e R2=b). Passo II: identifica-se qual a estrutura composta mais imediatamente ligada as unidades básicas, ou seja, caso se tenha algo como “(a/b)*a”, aplicar-se-ia o Passo 1 e, em

seguida, observa-se a presença da estrutura composta “OU” (representada como expressão regular sob a forma de “R1 + R2” ou “R1 / R2”), assim, seguindo o caso logo acima apresentado, tem-se “(R1 / R2)*R1” – lembrando que há ainda a “concatenação” (R1.R2 ou simplesmente R1R2) e a “iteração” (R1*) como estruturas compostas, todas com suas respectivas representações clássicas no formato de autômatos finitos. Passo III: nesse momento, já se torna possível construir graficamente uma conversão, posto que já se tem 6 estados (os quais seguem uma ordem numérica crescente), isto é, 1 para 2 – conseguindo-se “a”, 3 para 4, conseguindo-se “b”, um estado inicial 5 indo tanto para 1 quanto para 3, bem como um final 6 concentrando o que vem de 2 e de 4(representando o “OU”), e então injeta-se 2 novos estados finais e iniciais, respectivamente 8 e 7, ligados aos seus predecessores, o que representa, nesse momento, a figura da “iteração”, constituindo a expressão “(a/b)*”. Em seguida, basta adicionar mais um estado para concatenar com R1 a direita do asterisco, tornando-se o definitivo estado final (mais uma vez, para o caso em tela). Vale lembrar que a orientação a partir dos passos pode modificar-se apenas em função da complexidade da expressão regular, mas a essência de identificação das unidades básicas regulares e a devida substituição pelas representações em autômatos finitos permanece. Procedimento do Método da Construção de Subconjuntos I. Obter estado inicial: o estado inicial do AFD é definido como a ε* do conjunto contendo apenas o estado inicial do AFND. II. Obter novos estados e transições: cada estado obtido para o AFD é analisado para descobrir, para cada símbolo do alfabeto, suas transições de saída e novos estados que são gerados. III. Marcar estados finais: cada estado do AFD que contenha em seu subconjunto um estado final do AFND será um estado final do AFD. CONCLUSÃO Conforme doutrina amplamente consolidada nas questões em tela aqui tratadas, faz-se mister trazer à tona o fato de que definir diferenças ou semelhanças entre Expressões Regulares e Autômatos Finitos implica citar seu inevitável entrelaçamento. É o caso, por exemplo, dos Analisadores Léxicos, onde os símbolos básicos (conhecidos como “tokens”) de uma linguagem de programação geralmente podem ser especificados de maneira muito eficiente empregando-se expressões regulares, levando-se em consideração que o tempo de computação e a ocupação de memória dependem do comprimento da expressão regular e do comprimento da cadeia a reconhecer. Tal ER pode ser automaticamente convertida em AFDs, os quais, apesar de possuírem uma implementação trivial, representam de maneira menos natural algumas linguagens regulares. Outra aplicação comumente utilizada seriam as operações de busca e substituição de cadeias de caracteres em editores de texto, operação essa eficazmente desempenhada por AF quando a cadeia é expressa em termos de ERs, cuja conversão de ER para AF ocorre de forma automática e transparente para o usuário.

Enfim, a relação entre ambos é intrínseca e de uso naturalmente bastante diversificado, indo desde segurança de arquivos e compressão de dados, além dos supracitados casos, até modelagem de redes neurais. REFERÊNCIAS Apostilas em HTML de Introdução a Software de Sistema. Disponível em . Acessado em 04/09/2009. CRESPO, Rui Gustavo. (1998) “Processadores de linguagens: da concepção à implementação”, IST Press. MENEZES, Paulo Blauth. (1997) “Linguagens formais e autômatos”, UFRGS, Sagra Luzzatto.