Linguagens Formais e Autômatos

Faculdade Anhanguera                

[pic 1]

                             Rafael Macedo Bertanha – RA: 3730729220

Thiago Augusto Figueiredo – RA: 3724680518

linguagens formais e autômatos

                                                          LIMEIRA

2015

Sumário

Passeio do Cavalo        

1-        Descrição do problema        

2-        Descrição Textual do Movimentos de Xadrez        

3-        Reconhecimento da Entrada        

3.1 - Autômato Finito Determinístico        

3.2 - Autômato Finito Não - Determinístico        

4-        Reconhecimento dos Movimentos do Cavalo        

5-        Validação do Problema        

Bibliografia        

    Passeio do Cavalo

1. Descrição do problema

Cada adversário recebe suas peças, por regar quem recebe a branca tem é que começa o jogo. O objetivo do jogo e movimentar as peças de acordo com o seu movimento e eliminar as peças do adversário até chegar ao rei e bloquear seus movimentos (“cheque – mate”). O adversário pode desistir do jogo a qualquer momento tornado o xeque – mate não sendo o único jeito de ganhar o jogo.

O cavalo tem o seu movimento em “L”, ele anda duas casa e vira pra direita ou para esquerda, durante o jogo se uma peça estiver em seu caminho ele pode pula está peça para chegar à casa que deseja.

1. Descrição Textual do Movimentos de Xadrez

Rei – Seu movimento e para tordos os lados, mas uma casa por vez, não pula peça.

Rainha – Seu movimento é para todos os lados e quantas casa quiser, não pula peça.

Bispo – Seu movimento e só em diagonal, não pula peça.

Torre – Seu movimento horizontal e vertical, não pula peça.

Cavalo – Seu movimento é em L, pode pular peça

Peão – Só anda uma casa, havendo seu movimento de duas casa caso não tenha movido, não pula peça.

Utilizando a gramática regular chegamos a essas conclusões.

G= (C, l, k, S)

C = Cavalo

l = linha

K = Coluna

S= Posição Inicial

G= ({G, S}, {b2, a4, c4, d3, d1} S, R)

S->C

C->b2, C-> a4, C-> c4, C-> d3, C-> d1

Expressão regular

ER= (C *(l + k + k) *(l + l + k))

C->b2, C->a4

C->b2, C->c4

C->b2, C->d3

C->b2, C->d1

1. Reconhecimento da Entrada

                  3.1 - Autômato Finito Determinístico

[pic 2][pic 3][pic 4][pic 5][pic 6]

                    3.2 - Autômato Finito Não - Determinístico

[pic 7][pic 8]

[pic 9]

[pic 10][pic 11][pic 12]

[pic 13][pic 14][pic 15]

[pic 16][pic 17]

[pic 18]

[pic 19]

[pic 20]

1. Reconhecimento dos Movimentos do Cavalo

G=({G,S},{a,b2,a4,c4,d3,d1},P,C)

P={C -> SG|S}

     {S -> b2,a4,c4,d3,d1}

Derivação da Expressão:

G->GS->SSG->SSSG->SSSSG->SSSSS-> b2a4c4d3d1

...