Linguagens formais e automatos - passeio do cavalo

FACULDADE ANHANGUERA DE CAMPINAS
UNIDADE II

Marcos A. Stecca RA:926435313
Robson J. Silva RA:901382362
Thiago Henrique da Silva RA:991002855

ATIVIDADES PRÁTICAS SUPERVISIONADAS LINGUAGENS FORMAIS E AUTÔMATOS: O passeio do cavalo.
Professor André Luís Bordignon

Campinas
11/04/2012

Capítulo 1 – Descrição do Problema.
O problema do cavalo, ou passeio do cavalo, é um problema matemático envolvendo o movimento da peça do cavalo no tabuleiro de xadrez. O cavalo é colocado no tabuleiro vazio e, seguindo as regras do jogo, precisa passar por todas as casas exatamente uma vez, ou seja, movimentar o cavalo em “L” para que ele passe por todas as 64 casas do tabuleiro sem repetir nenhuma.
Capítulo 2 – Descrição Textual dos Movimentos do Xadrez
Abaixo gramática regular que exemplifica uma sequência de movimento do cavalo em um tabuleiro 8x8.
G=({S, C}, {a1,b1,c1,d1,e1,f1,g1,h1, a2,b2,c2,d2,e2,f2,g2,h2, a3,b3,c3,d3,e3,f3,g3,h3, a4,b4,c4,d4,e4,f4,g4,h4, a5,b5,c5,d5,e5,f5,g5,h5, a6,b6,c6,d6,e6,f6,g6,h6, a7,b7,c7,d7,e7,f7,g7,h7, a8,b8,c8,d8,e8,f8,g8,h8}, R, S) onde R:
S→C
C→e4; C→c3; C→g3; C→d2; C→f2; C→c5; C→g5, C→d6; C→f6
Figura 1- Tabuleiro de Xadrez

Figura 2 - Tabuleiro de xadrez após aplicação da gramática regular descrita acima

Abaixo gramática regular que exemplifica uma sequência de movimento do cavalo completando o desafio “passeio do cavalo” em um tabuleiro 8x8.
G=({S, C}, {a1,b1,c1,d1,e1,f1,g1,h1, a2,b2,c2,d2,e2,f2,g2,h2, a3,b3,c3,d3,e3,f3,g3,h3, a4,b4,c4,d4,e4,f4,g4,h4, a5,b5,c5,d5,e5,f5,g5,h5, a6,b6,c6,d6,e6,f6,g6,h6, a7,b7,c7,d7,e7,f7,g7,h7, a8,b8,c8,d8,e8,f8,g8,h8}, R, S) onde R:
S→C
C→a8, C→b6, C→d7, C→c5, C→a4, C→b2, C→d1, C→c3, C→e4, C→f2, C→h1, C→g3, C→h5, C→g7, C→e6, C→f8, C→g6, C→h8, C→f7, C→e5, C→g4, C→h2, C→f1, C→e3, C→c4, C→d2, C→b1, C→a3, C→b5, C→a7, C→c8, C→d6, C→e8, C→f6, C→h7, C→g5, C→h3, C→g1, C→e2, C→f4, C→d3, C→c1, C→a2, C→b4, C→d5, C→c7, C→a6, C→b8, C→c6, C→d8, C→b7, C→a5, C→b3, C→a1, C→c2, C→d4, C→f3, C→e1, C→g2,