Início > autômatos finitos, Computer Theory, Linguagens Formais, maquina de estado finito, Teoria da Computação > Expressões regulares, autômato finito não determinístico e autômato finito determinístico

Expressões regulares, autômato finito não determinístico e autômato finito determinístico


 

Introdução

 

No desenvolvimento de um programa (http://www.braga.eti.br/ca/) para exibir quaisquer das 256 regras de autômatos celulares (ACs) propostos pelo incrível Stephen Wolfram, em seu volumoso livro “A New Kind of Science” deparou-se com a questão, simples, de como tratar as possíveis combinações de entrada, do referido programa, já que o usuário poderia:

  1. Pedir o AC de uma única regra (x, onde 0 \leq x \geq 255);
  2. Pedir um conjunto de ACs no seguinte formato: xy, onde x, y \leq 255\,\,e\,\,x < y;
  3. Pedir vários ACs, combinando as duas alternativas anteriores separadas por vírgula (,), em um número finito (e, arbitrário) de vezes.

Este artigo trata das etapas necessárias para que se possa implementar, de forma correta, o tratamento da entrada do programa proposto. Tais etapas são: (a) a construção da expressão regular, (b) a transformação da expressão regular em um autômato finito não determinístico (NFA), (c) a redução do NFA para um autômato finito determinístico (DFA) e, (d) a implementação propriamente dita.

 

Expressão Regular

 

Na literatura de computação, principalmente, os trabalhos de pessoas que lidam com inseguridade como, por exemplo, LANGSEC: Language-theoretic Security recomendam, insistentemente, o uso de linguagens regulares para tratar as entradas de um programa. Nesta direção, se considerado que nos itens de 1 a 3 das especificações acima, as variáveis x e y (diferentes entre si) são números de 0 a 255 pode-se adotar tais números como símbolos, e com as abstrações admissíveis usar a letra (ou símbolo!) n para representá-los e, adicionalmente reconhecer, que dois outros símbolos como pré-requisitos, (, e ), as seguintes combinações de entrada são possíveis:

  • n
  • n, n-n
  • n, n-n, n, …,n, n-n, …
  • n-n, …, n, …,n, n-n, …
  • etc

De tais combinações, depois de um pequeno esforço mental é possível identificar a expressão regular que responde ao desejado:

(n\mid nn)(,n\mid,nn)^*

A noção de abstração aplicada à formulação da expressão regular implica que serão deixadas para a implementação, as questões limitantes do uso do símbolo n e da representação infinita do *.

Dada a expressão regular, a próxima etapa é a construção do NFA.

 

Autômato finito não determinístico (NFA)

 

Construir um NFA a partir de uma expressão regular utilizando-se do algoritmo disponível em várias referências é uma tarefa extremamente agradável, muito embora, um pouco trabalhosa. em determinados casos. Entretanto, na Internet existem diversos ambientes para construção do NFA, de forma automática. Um deles é o Regular Expression to NFA. Usando-o, obtemos o NFA exibido na Figura 1.

 

nfa-erca

Figura 1. NFA obtido automaticamente. Fonte: Regular Expression to NFA.

 

Autômato finito determinístico (DFA)

 

O mesmo construtor do NFA, fornece o DFA, imediatamente, conforme visto na Figura 2.

 

dfa-erca

Figura 2. DFA produzido a partir do NFA da Figura 1. Fonte: Regular Expression to NFA.

 

 

Implementação

 

No Capítulo 10, “Patterns, Automata, and Regular Expressions”, do livro de Al Aho e Jeff Ullman, imperdível e disponível na Internet em Foundations of Computer Science, exibe um algoritmo de implementação de um autômato, extremamente simples, como se pode verificar. Foi usado aquele algoritmo para a implementação e, na oportunidade garantindo as restrições sobre a expressão regular lembradas acima.

  1. Nenhum comentário ainda.
  1. No trackbacks yet.

Deixe uma resposta

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: