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.

Tribo do C.I.

Tribo do C.I.

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