Tag: Ciência da Computação

Linguagens formais e Autômatos – 2

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.

Linguagens formais e Autômatos – 1

Teoria das linguagens Formais foi desenvolvida por volta de 1950 para desenvolver teorias relacionadas às linguagens naturais, porém viu-se que estas teorias também eram aplicáveis às linguagens artificiais, originárias da Ciência da Computação. Desde então houve um desenvolvimento significativo da Análise Léxica, Sintáxe de linguagens de programação, modelos de sistemas biológicos e, recentemente, até mesmo no tratamento de linguagens não-lineares, como Planares, Espaciais e n-Dimensionais.

A sintaxe trata das propriedades livres da linguagem, como por exemplo a verificação gramatical de programas, já a semântica é voltada à interpretação de uma linguagem, como por exemplo um significado ou valor para um determinado programa. Atualmente, a teoria da sintaxe possui construções matemáticas bem definidas e universalmente reconhecidas, como por exemplo as Gramáticas de Chomsky.

Uma linguagem de programação pode ser vista de duas formas:

  • Uma entidade livre, ou seja, sem qualquer significado associado;
  • Uma entidade juntamente à uma interpretação do seu significado;

Os formalismos das  linguagens lineares abstratas podem ser classificados nos seguintes tipos:

  • Operacional: Também conhecido como Reconhecedor, define-se um autômato ou uma máquina abstrata, baseada em estados, em instruções primitivas e na especificação de como cada instrução modifica cada estado.
  • Axiomático: Também conhecido como Gerador, associam-se regras às componentes da linguagem.
  • Denotacional: Também conhecido como Funcional, define-se uma função que caracteriza o conjunto de palavras admissíveis na linguagem.

Visto que estes formalismos são aplicados à qualquer modelo matemático, as bases que tomamos para iniciar o estudo das linguagens formais também são conhecidas da matemática convencional, são eles: A teoria dos Conjuntos, relações, funções, Lógica e Técnicas de Demonstração, bem como os conceitos de Alfabeto, Palavras, Linguagens e Gramáticas.

  • Conjunto: É uma coleção de zero ou mais objetos distintos, denominados Elementos do conjunto. Um elemento é uma entidade básica a qual não é definida formalmente. As operações dos conjuntos são: União, intersecção, diferença, complemento, conjunto das partes, produto cartesiano. Tais operações não serão detalhadas neste artigo.
  • Relações: É um subconjunto de um produto cartesiano. Existem quatro tipos de relações: Reflexiva, Simétrica, Antissimétrica, Transitiva.
  • Funções: É uma relação onde cada elemento do domínio está relacionado com, no máximo, um elemento do contra-domínio. Existem funções Injetoras, Sobrejetoras e Bijetoras ou Isomórficas.
  • Lógica: A lógica aqui tratada é referente à Lógica Booleana, que estuda os princípios e métodos usados para distinguir sentenças verdadeiras ou falsas.
  • Técnicas de Demonstração: Dado um teorema, partimos do ponto em que descobrimos hipótese e tese, então utilizamos técnicas para comprovar que a hipótese implica a tese. As principais técnicas de demonstração são:
    • Prova Direta: Simplesmente pressupõe verdadeira a hipótese e, a partir desta, prova ser verdadeira a tese.
    • Prova por Contraposição: parte do resultado que se A=>B então B=>A
    • Prova por Redução ao absurdo: Em latim, Reductio ad Absurdum, pressupõe falsa a hipótese, se não conseguir provar sua falsidade, portanto o teorema é verdadeiro.
    • Prova por indução: uma tese base é provada e uma regra de indução é usada para provar uma série de outras teses.
  • Alfabeto: É um conjunto finito de Símbolos, portanto pode ser um conjunto vazio.
  • Palavra: É uma seqüência finita de símbolos (do alfabeto) justapostos.
  • Gramáticas: É uma quádrupla ordenada G = (V,T,P,S) onde 
    • V: Conjunto finito de símbolos variáveis ou não-variáveis;
    • T: Conjunto finito de símbolos terminais disjuntos de V;
    • P: Conjunto finito de pares, denominados regras de produção tal que a primeira componente é palavra de (V U T)+ e a segunda componente é palavra de (V U T)*;
    • S: Elemento de V denominado variável inicial.

Com estes conceitos básicos podemos passar para o estudo das Linguagens Regulares