Matemática

...

[pic 3]

-

Diagrama de autômato finito determinístico

Com as informações que obtivemos no passo anterior criaremos o autômato, ele representará o caminho que o visitante irá percorrer para poder entrar para a visita.

[pic 4]

Podemos ver que na chegada ao presidio já tem é onde começa a primeira etapa do processo onde ele poderá retornar (passa do q0 para q1, ou retorna para q0) ou passará para a próxima sala, na segunda sala se o detector de metais não acusar nada a porta se abrirá e ele poderá seguir adiante caso contrário ele deverá retornar (passando do q2 para o q3, ou voltando ao q2), no próximo passo ele já está dentro do presido onde ele já poderá visitar o detento, passando o cartão ele já terá acesso a umas das salas de visita.

Para a máquina de leitura do cartão magnético temos um mecanismo próprio onde ela fará a leitura do cartão e indicará a porta que a visita deverá se dirigir. As portas são identificadas de A à E.

[pic 5]

O ponto inicial é o Q0, quando passado o cartão a máquina começa a operar e lê a fita com as letras correspondentes as das portas e então inicia o processo, por exemplo ela lê a letra D então ela chegará ao Q4 onde entenderá que a porta E deverá ser aberta.

2.1 Relatório 2: Diagrama do autômato finito não determinístico e autômato finito não determinístico com Pilha do controle de abrir e fechar as portas de acesso aos setores.

Um AFN, similarmente a um AFD, lê uma cadeia de símbolos de entrada. Para cada símbolo da entrada há uma transição para um novo estado, até que todos os símbolos de entrada sejam lidos, porém existe pelo menos um estado tal que ao ler um mesmo símbolo há mais de uma possibilidade de estado destino. Assim, o próximo estado é um elemento do conjunto das partes dos estados.

Aceitação. Uma cadeia é aceita por um AFN se testando-se todas as transições

Possíveis à medida que se lê a cadeia, o AFN pára em um estado final após ler toda a cadeia para algum caminho das transições. Assim, o não-determinismo do próximo estado pode ser interpretado como um teste de todas as possibilidades.

Rejeição. Uma cadeia é rejeita por um AFN se nenhum caminho de transições leva o autômato a um estado final após ler toda a cadeia.

Definição Formal

O AFN é definido como uma 5-upla, M = (S , Q, d, q0, F), onde:

• S : alfabeto de símbolos finito de entrada

• Q: conjunto finito de estados possíveis para M

• d: função transição ou função programa definida em Q x S ? P(Q)

• q0: estado inicial de M, sendo q0 ?Q

• F: conjunto de estados finais, tal que F? Q

P(Q) representa o conjunto das partes de Q.

O AFN com transições e (também conhecido como AFN-epsilon ou AFN-lambda) é definido por uma 5-upla extremamente semelhante, porém, a função de transição é substituída por uma que permite a cadeia vazia e como uma entrada possível. Desse modo, sua função de transição é dada por:

d: Q x (S U {e}) ? P(Q)

A máquina começa no estado inicial especificado e lê uma cadeia de símbolos do seu alfabeto. O autômato usa a função de transição de estado para determinar o próximo estado usando o estado atual e o símbolo que acabou de ser lido. Entretanto, "o próximo estado de um AFN não depende somente do evento atual, mas também de um número arbitrário de eventos subsequentes de entradas. Até esses eventos subsequentes ocorrerem, não é possível determinar onde a máquina de estados está".

Para todo AFN pode ser encontrada um AFD que aceite a mesma linguagem. Portanto, é possível converter um AFN existente em um AFD, a máquina AFD terá 2n estados, onde n é o número de estados da máquina AFN.

Vantagens e Desvantagens

AFDs são equivalentes em poder de expressão a Autômatos finitos não determinísticos (NFDs). Isso se dá porque, primeiramente qualquer AFD é também um AFN, então AFNs podem expressar o que AFDs expressam. Além disso, dado um AFN, através de uma Construção do conjunto das partes é possível construir um AFD que reconhece a mesma linguagem que um determinado AFN, apesar de o AFD poder precisar de um número muito maior de estados que o AFN . Por outro lado, autômatos de estado finito de potência são estritamente limitados nas linguagens que podem reconhecer. Muitas linguagens simples, incluindo qualquer problema que requeira mais que espaço constante para resolver, não podem ser reconhecidos por um AFD.

2.2. Analisando as portas de entrada.

Os visitantes entrarão e sairão pela mesma porta por isso criaremos um modelo de controle para que seja o mesmo número de vezes que se entrar tem de ser o mesmo número de vezes que saiu, para garantirmos a integridade e bom funcionamento de todo o sistema.

Para esse controle na hora que o visitante passar o cartão magnético na porta será contabilizado um visitante e ao sair será contado menos um visitante, se outro visitante for passar para visitar o mesmo presidiário será negado o acesso até que a outra visitante saia.

Então toda vez que o sistema identificar que o número de visitantes for diferente de 0 a porta não se abrirá pois a um outro visitante na sala.

2.3 Diagrama de autômato finito não determinístico

Agora apresentaremos o diagrama do autômato finito não determinístico.