Tribo do C.I.

Só mais um blog de informática (só que não)

Linguagens formais e Autômatos – 2

novembro 30th, 2010

Para ver a primeira parte clique aqui

Linguagens Regulares – Sistemas de Estados Finitos:

Um Sistema de Estados Finitos é um modelo matemático de sistema com entradase e saídas discretas. Pode assumir um número finito e pré-definido de estados. Cada estado resume somente as informações do passado necessárias para determinar as ações para a próxima entrada.

Autômato Finito – AFD (Autômato Finito Determinístico) é uma 5-upla:

  • \, Q é um conjunto finito não vazio de estados do autômato;
  • \,\Sigma é um conjunto de símbolos, denominado alfabeto de entrada do autômato;
  • \,\delta:Q \times \Sigma \to Q é a função de transição de estados do autômato e seu papel é o de indicar as transições possíveis em cada configuração do autômato. Esta função fornece para cada par “estado e símbolo de entrada” um novo estado para onde o autômato deverá mover-se.
  • \,q_{0}\in\, Q é denominado estado inicial do autômato finito. É o estado para o qual o reconhecedor deve ser levado antes de iniciar suas atividades.
  • F\subseteq Q é um subconjunto do conjunto Q dos estados do autômato, e contém todos os estados de aceitação ou estados finais do autômato finito. Estes estados são aqueles em que o autômato deve terminar o reconhecimento das cadeias de entrada que pertencem à linguagem que o autômato define. Nenhuma outra cadeia deve ser capaz de levar o autômato a qualquer destes estados.

Autômato Finito Não-Determinístico (AFN) – Autômatos finitos não determinísticos diferem dos Autômatos finitos determinísticos quanto à regra de transição entre estados. Dada uma combinação de um estado atual e um símbolo de entrada, pode não haver estados especificados para os quais o estado atual deve conduzir o processamento, bem como pode haver vários estados resultantes da leitura do símbolo. Portanto, para uma função de transição ? definida em Q \times \Sigma \,\!, o seu valor não deve ser um elemento de Q (como acontece com os autômatos determinísticos), mas um subconjunto de Q (incluindo o conjunto vazio). Ou seja, o processamento de \delta(q, a)\,\! leva à um conjunto de estados em que a máquina pode legalmente se encontrar após estar em um estado q lendo um símbolo de entrada a.

Equivalência entre AFD e AFN – Embora um AFN seja somente um acréscimo ao AFD, na verdade não aumenta seu poder computacional, sendo assim, para cada AFN é possível construir um AFD equivalente que realiza o mesmo processamento. O contrário também é verdadeiro.

Autômato Finito com Movimentos Vazios – Movimentos vazios constituem uma generalização dos modelos de máquinas não-determinística, é um movimento determinado por uma simples mudança de estado.  Uma das vantagens dos autômatos Finitos com Movimentos Vazios no estudo das linguagens Formais é o fato de facilitar algumas construções e demonstrações relacionadas com os autômatos.

Equivalência entre AFN e AFe – Analogamente ao não-determinístico, os movimentos vazios não aumentam o poder computacional dos autõmatos finitos. Assim, para cada AFe, é possível construir um AFN que realiza o mesmo processamento. O contrário é trivialmente verdadeiro.

Minimização de um autômato Finito

Alguns autômatos possuem estados que são funcionalmente os mesmos. O algorítmo de minimização tem como objetivo unir estes estados em um único.

Pré-requisitos do algorítmo de Minimização

  • O autômato deve ser determinístico;
  • Todos os estudos devem ser alcançados iniciando do estado inicial;

Algorítmo

  • Construa uma tabela, marcando os elementos que são por definição funcionalmente diferentes (estado inicial e final)
  • Dois a dois, os outros estados marcados e que são funcionalmente diferentes.
  • Unir  os estados equivalentes.

Com estes conceitos básicos podemos passar para o estudo das Expressões Regulares

Autômatos finitos não determinísticos diferem dos Autômatos finitos determinísticos quanto à regra de transição entre estados. Dada uma combinação de um estado atual e um símbolo de entrada, pode não haver estados especificados para os quais o estado atual deve conduzir o processamento, bem como pode haver vários estados resultantes da leitura do símbolo. Portanto, para uma função de transição ? definida em Q \times \Sigma \,\!, o seu valor não deve ser um elemento de Q (como acontece com os autômatos determinísticos), mas um subconjunto de Q (incluindo o conjunto vazio). Ou seja, o processamento de \delta(q, a)\,\! leva à um conjunto de estados em que a máquina pode legalmente se encontrar após estar em um estado q lendo um símbolo de entrada a. Assim, podemos definir um autômato finito não determinístico matematicamente como se segue.
Sobre Sheldon Led:
Desenvolvedor e palestrante desde 2009. Já trabalhou com sistemas legados e software de gestão, mas hoje atua somente com web. Já participou do desenvolvimento de alguns portais governamentais e sites utilizando a plataforma Joomla e WordPress. Apesar de ser um desenvolvedor full-stack, tem focado seus estudos em tecnologias front-end e busca apoiar e colaborar em projetos envolvendo Software Livre, seja em eventos, material para estudo ou contribuição de código.