ATPS Teoria da Computação

Prévia do material em texto

FAV - Faculdade Anhanguera de Valinhos
Teoria da Computação
Atividades Praticas Supervisionadas
Alessandro Fiori R.A.7682748636
Valinhos
2015
Alessandro Fiori R.A.7682748636
Atividades Práticas Supervisionadas
Atividades Praticas Supervisionadas apresentadas como exigência para aprovação na disciplina de Teoria da Computação do grau de Bacharelado de Ciência da Computação da FAV - Faculdade Anhanguera de Valinhos.
Orientador: Plinio Vilela
Valinhos
2015
RESUMO
Nessa ATPS está descrito uma breve instrução de como o autômato do software de segurança para liberação de visitantes a um presidio deve funcionar, ao decorrer das etapas serão expostas as minhas soluções encontradas para determinar se um visitante poderá ao não seguir ate a sessão desejada. 
Palavras-chave: autômato, finito, determinístico, entradas, estados, alfabeto, funções de transição, estados finais, estado inicial, presidio, atps, execução, teoria da computação, computação, máquina.
ABSTRACT
That ATPS is described a brief statement of how the automaton of security software for release of visitors to a presidio should work, the course of the steps my solutions found will be exhibited to determine if a visitor can not follow up to the desired session.
Keywords: automaton, finite, deterministic, inputs, states, alphabet, transition functions, final states, initial state, presidio, ATPs, execution, theoretical computer science, computing, machine
LISTA DE FIGURAS
Figura 1 - Automato Finito Determinístico do sistema	8
LISTA DE TABELAS
Tabela 1 - Funções de Transição	9
SUMÁRIO
HYPERLINK \l "_Toc431473103" 1 INTRODUÇÃO	7
HYPERLINK \l "_Toc431473104" 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	8
HYPERLINK \l "_Toc431473105" 3 CONCLUSÃO	11
HYPERLINK \l "_Toc431473106" REFERÊNCIAS	12
12
1 INTRODUÇÃO
A atividade proposta nessa ATPS trata-se de um modelo de sistema de liberação para visitantes nos presídios brasileiros. O sistema deve liberar ou não a entrada das pessoas, primeiramente mediante verificação inicial por detector de metais logo na entrada do presidio. Após a liberação da porta de entrada o visitante deve encaminhar-se para um dos policiais atendentes que fará um cadastro e entregará um cartão magnético com um código que liberará a porta correspondente a sessão que ele poderá ir.
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
O autômato abaixo esboça como será o sistema de liberação de visitantes no presídio:
Figura Erro! Indicador não definido. - Autômato Finito Determinístico do sistema
Fonte: Autoria própria.
As características do autômato acima é definido da seguinte forma:
Estados da maquina: q0 - que representa a porta de entrada
			 q1 - Saguão das portas das sessões
			 q2 - Sessão 1
			 q3 - Sessão 2
			 q4 - Sessão 3
			 q5 - Sessão 4
			 q6 - Sessão 5
Alfabeto: 0,1,a,b,c,d,e
Estado inicial: q0
Estados Finais: q2, q3, q4, q5, q6
Funções de Transição:
Tabela 1 - Funções de Transição
Estado
Dado
Ação
q0
0
q0
q0
1
q1
q0
a
q0
q0
b
q0
q0
c
q0
q0
d
q0
q0
e
q0
q1
0
q1
q1
1
q1
q1
a
q2
q1
b
q3
q1
c
q4
q1
d
q5
q1
e
q6
q2
0
q2
q2
1
q2
q2
a
q2
q2
b
q2
q2
c
q2
q2
d
q2
q2
e
q2
q3
0
q3
q3
1
q3
q3
a
q3
q3
b
q3
q3
c
q3
q3
d
q3
q3
e
q3
q4
0
q3
q4
1
q4
q4
a
q4
q4
b
q4
q4
c
q4
q4
d
q4
q4
e
q4
q5
0
q5
q5
1
q5
q5
a
q5
q5
b
q5
q5
c
q5
q5
d
q5
q5
e
q5
q6
0
q6
q6
1
q6
q6
a
q6
q6
b
q6
q6
c
q6
q6
d
q6
q6
e
q6
 
Fonte: Autoria própria.
O autômato funciona da seguinte maneira:
Quando o visitante chega porta de entrada e não possui nenhum dos objetos proibidos sua entrada é liberado, para isso o estado q0 precisa ler '1' para a maquina passar para o próximo estado.
Apos o visitante estar com seu cartão magnético ele vai dirigir-se para a porta correspondente a sessão de destino, cada sessão a maquina aceitara o código correspondente, sendo: 	a - sessão 1
				b - sessão 2
				c - sessão 3
				d - sessão 4
				e - sessão 5
				
3 CONCLUSÃO
Os autômatos servem para simular um problema que pode ser computado. Nele definimos os estados onde o problema a ser resolvido percorre de acordo com o dado apresentado. Os dados aceitos são definidos pelo alfabeto estipulado para formar a palavras ‘comando’ desejadas para se chegar ao estado final, dependendo da aplicação podemos ter mais de um estado final.
Durante a execução o programa baseia-se nas funções de transição definidas pelo programador do autômato para aceitar ou não a palavra de entrada, um autômato finito determinístico nunca pode falhar então todas as possibilidades de entrada aceitas devem funcionar e o mesmo com entradas não aceitas devem ser recusados.
REFERÊNCIAS
LEWIS, H. Elementos de Teoria da Computação. 2°. ed. Porto Alegre: Bookman, 2000. 344p.
Autômatos e Linguagens. Disponível em: <https://drive.google.com/a/asga.com.br/file/d/0Bwtkydm_xvOrQTNqN25SWmkzdms/edit> Acesso em: 1 out. 2015
e-Book: Linguagens Formais & Autômatos. Disponível em: <https://drive.google.com/a/asga.com.br/file/d/0Bwtkydm_xvOrZEJ3T3dkaEJ2WmM/edit> Acesso em: 1 out. 2015