ATPS Linguagens Formais E Autômatos
Casos: ATPS Linguagens Formais E Autômatos. Pesquise 861.000+ trabalhos acadêmicosPor: mitsanx • 10/6/2014 • 2.394 Palavras (10 Páginas) • 888 Visualizações
Sumário
O passeio do Cavalo ....................................................................................................................................... 3
ETAPA 1 ............................................................................................................................................................ 3
Capítulo 1 : Descrição do Problema ..................................................................................................... 3
Capítulo 2 : Descrição Textual dos Movimentos do Xadrez .............................................................. 4
ETAPA 2 ............................................................................................................................................................ 7
Capítulo 3 : Reconhecimento da entrada ............................................................................................ 7
Notação Algébrica ............................................................................................................................ 7
Alfabeto .............................................................................................................................................. 7
Linguagem ........................................................................................................................................ 7
Expressão Regular .......................................................................................................................... 8
Exemplos de alguns passeios possíveis: ..................................................................................... 8
Autômato não determinístico que representa uma sequência de movimentos ...................... 8
Autômato determinístico que representa uma sequência de movimentos ............................. 8
ETAPA 3 ............................................................................................................................................................ 9
Capítulo 4 : Reconhecimento dos Movimentos do Cavalo ............................................................... 9
Autômato com pilha ....................................................................................................................... 14
Referencia Bibliográfica: .............................................................................................................................. 16
ANEXO I – Partida de Xadrez ..................................................................................................................... 17
ANEXO II – Orientações da Primeira Entrega .......................................................................................... 21
ANEXO III – Orientações em PDF (2ª Entrega) ....................................................................................... 22
ANEXO IV – Contracapa comentada (1ª entrega) ................................................................................... 23
ANEXO V – referência ao AFD (contracapa comentada) ....................................................................... 24
3
O passeio do Cavalo
ETAPA 1
Capítulo 1 : Descrição do Problema
“O Xadrez é um jogo estratégico de tabuleiro para dois jogadores. O jogo é
disputado em um tabuleiro de 64 casas (8x8) alternadas entre claras e escuras. Cada
jogador inicia a partida com 16 peças, sendo: 1 rei, 1 rainha, 2 bispos, 2 cavalos, 2 torres e 8
peões. O objetivo da partida é capturar o rei inimigo. Para isso, um dos jogadores deve
posicionar suas peças no tabuleiro de forma que, na próxima jogada, ele consiga mover
uma das peças para a casa ocupada pelo rei inimigo, considerando o movimento particular
de cada peça.
Além do seu valor estratégico e lúdico, o xadrez também se mostra muito
importante no ponto de vista matemático e computacional. Diversos problemas de natureza
combinatória e topológica ligado ao xadrez são conhecidos, foram estudados nas últimas
centenas de anos e, mais recentemente, suas soluções foram aplicadas para resolução de
vários problemas computacionais. Esses problemas são chamados de composições.
Em uma composição o problema é apresentado por meio da definição de uma
distribuição de peças no tabuleiro e a solução consiste em realizar uma ação determinada. É
comum que a ação a ser realizada venha acompanhada de uma ou mais restrições.
Existem diversas composições clássicas no xadrez. Uma delas é conhecida como o
passeio do cavalo. Nessa composição o desafio é fazer com que o cavalo passe por todas
as casas do tabuleiro. Inicialmente o cavalo está em uma casa qualquer e ele deve ser
movimentado obedecendo às regras de movimentação para essa peça.
Este desafio consiste em elaborar uma solução computacional, utilizando os
conceitos de Linguagens Formais e Autômatos, para verificar se uma sequência de
movimentações é uma solução para a composição do passeio do cavalo. Para tanto o aluno
é convidado a elaborar os formalismos geradores (expressões regulares e gramáticas) e
reconhecedores (máquinas de estados finitos) necessários para verificar se a sequência
corresponde a uma representação textual correta de movimentos da peça; se a sequência
de
...