Teoria de Linguagens

Neste trabalho é possível testar palavras para um automato finito determinístico derivado da expressão regular 7(0b + 9a)+7 através de arquivos em formato especifico ou por inputs individuais. Dessa maneira, é possível verificar se as palavras testadas são aceitas ou não pelo autômato. Todo o conteúdo para obter o AFD a partir da ER pode ser verificado logo a seguir.

Conteúdo

Expressões Regulares

Toda linguagem regular pode ser descrita por uma ER, pois ela é um formalismo denotacional (gerador) e é definida a partir de conjuntos (linguagens) básicos, concatenação e união. Em compiladores, por exemplo, ao projetar linguagens de programação, as ER são úteis no processo de análise sintática. Além de serem adequadas para a comunicação entre humanos ou de humanos com as máquinas.
ER
ER Linguagem Gerada
aa Somente a palavra aa
ba* Palavras iniciadas em b, seguido por zero ou mais a
(a + b)* Todas as palavras sobre { a, b }
(a + e)(b + ba)* Todas as palavras que não possuem dois a consecutivos

AFN com Mov. Vazio

A computação de um AFN-e é análoga à de um AFN, assim, ele é também não-determinístico assumindo simultaneamente mais de um estado. No caso do processamento de uma transição vazia ele assume ao mesmo tempo os estados destino e origem, e a sua leitura não consome nenhum simbolo da fita.
AFN_e
afne qf qf qi q0 q0 qi->q0 q1 q1 q0->q1 7 q2 q2 q1->q2 0b, 9a q2->qf 7 q2->q1 ℰ
AFN
afn qf qf qi q0 q0 qi->q0 q1 q1 q0->q1 7 q2 q2 q1->q2 0b, 9a q2->qf 7 q2->q1 0b, 9a q2->q2 0b, 9a

Autômato Finito Não Determinístico

Contudo, é possível construir um AFN a partir de um AFN-e, de maneira simplificada as seguintes etapas foram seguidas:
  • Quais serão os estados finais?
    • O único estado final será 'qf'.
  • Fecho vazio de cada estado?
    • O único estado com transição vazia é o estado 'q2', assim seu fecho vazio corresponde a (q2,ε)∪((q2,ε),{9a, 0b, 7,ε}) = {q1, q2}
  • Substituição das transições vazias
    • O estado q2 lendo os símbolos {9a, 0b} tem como destino o próprio q2 e o estado q1, assim a substituição da transição vazia resulta em um self-loop para q2, e uma aresta para q1.

Autômato Finito Determinístico

A partir de um AFN qualquer é possível construir um AFD que realiza as mesmas combinações, fazendo com que o segundo simule o primeiro. Os estados do AFD simulam combinações de estados alternativos do AFD, assim, é possível verificar através de uma tabela as combinações necessárias para que o autômato AFD seja gerado. Além disso, é preciso destacar que diferentemente do AFN, o AFD não assume simultaneamente mais de um estado.
Tabela de Transformação
Símbolos
Estados 7 0b 9a
q0 q1 -- --
q1 -- q2 q2
q2 qf* q1q2 q1q2
q1q2 qf* q1q2 q1q2
qf* -- -- --

Implementação do AFD

Nesta seção é possível interagir com o AFD implementado de duas maneiras:
  • Arquivo de Entrada: 1 palavra por linha.
  • Inputs de uma palavra por vez.
Observe que os símbolos da palavra devem ser separados por vírgula.
O alfabeto deste automato é {7, 0b, 9a}, assim uma entrada válida seria: 7,0b,7.
AFD
afd qf qf qi q0 q0 qi->q0 q1 q1 q0->q1 7 q2 q2 q1->q2 0b, 9a q2->qf 7 q1q2 q1q2 q2->q1q2 0b, 9a q1q2->qf 7 q1q2->q1q2 0b, 9a