ATPS LFA

7/31/2019 ATPS LFA

1/6

Cincia da Computao7 SrieLinguagens Formais e Autmatos

9

9

9

9

9

9

9

9

AUTORIA:

Diego Daniel DuarteFaculdade Anhanguera de Limeira

7/31/2019 ATPS LFA

2/6

Cincia da Computao - 7 Srie - Linguagens Formais e Autmatos

Diego Daniel Duarte

Pg. 2 de 6

COMPETNCIAS E HABILIDADES

Ao concluir as etapas propostas neste desafio, voc ter desenvolvido as competnciase habilidades descritas a seguir.

9Capacidade para desenvolvimento de pesquisa cientfica e tecnolgica.9 Profundo conhecimento dos aspectos tericos, cientficos e tecnolgicos relacionados computao.

9 Competncia para identificar, analisar, documentar e solucionar problemas enecessidades passveis de soluo via computao.

9 Saber conciliar teoria e prtica.

DESAFIO

O Xadrez um jogo estratgico de tabuleiro para dois jogadores. O jogo disputadoem um tabuleiro de 64 casas (8x8) alternadas entre claras e escuras. Cada jogador inicia apartida com 16 peas, sendo: 1 rei, 1 rainha, 2 bispos, 2cavalos, 2 torres e 8 pees. O objetivo da partida capturar orei inimigo. Para isso, um dos jogadores deve posicionar suaspeas no tabuleiro de forma que, na prxima jogada, eleconsiga mover uma das peas para a casa ocupada pelo reiinimigo, considerando o movimento particular de cada pea.

Alm do seu valor estratgico e ldico, o xadreztambm se mostra muito importante no ponto de vista

matemtico e computacional. Diversos problemas de naturezacombinatria e topolgica ligado ao xadrez so conhecidos,foram estudados nas ltimas centenas de anos e, maisrecentemente, suas solues foram aplicadas para resoluode vrios problemas computacionais. Esses problemas sochamados de composies.

Em uma composio o problema apresentado pormeio da definio de uma distribuio de peas no tabuleiro e a soluo consiste em realizaruma ao determinada. comum que a ao a ser realizada venha acompanhada de uma ou

mais restries.

Existem diversas composies clssicas no xadrez. Umadelas conhecida como o passeio do cavalo. Nessa composioo desafio fazer com que o cavalo passe por todas as casas dotabuleiro. Inicialmente o cavalo est em uma casa qualquer e eledeve ser movimentado obedecendo s regras de movimentaopara essa pea.

Este desafio consiste em elaborar uma soluocomputacional, utilizando os conceitos de Linguagens Formaise Autmatos, para verificar se uma sequncia demovimentaes uma soluo para a composio do passeio

do cavalo. Para tanto o aluno convidado a elaborar osformalismos geradores (expresses regulares e gramticas) ereconhecedores (mquinas de estados finitos) necessrios para verificar se a sequncia

7/31/2019 ATPS LFA

3/6


Diego Daniel Duarte

Pg. 3 de 6

corresponde a uma representao textual correta de movimentos da pea; se a sequncia demovimentos valida e, por fim, se todas as casas do tabuleiro foram visitadas.

Objetivo do desafio

Elaborar uma soluo computacional, utilizando os conceitos de Linguagens Formais eAutmatos, para verificar se uma sequncia de movimentaes uma soluo para acomposio do passeio do cavalo.

Produo Acadmica

x Relatrio contendo a apresentao e soluo para validao do problema doPasseio do Cavalo.

Participao

Para a elaborao desta atividade, os alunos devero previamente organizar-se emequipes de 3 a 4 participantes e entregar seus nomes, RAs e e-mails ao professor(a) dadisciplina. Essas equipes sero mantidas durante todas as etapas.

Padronizao

O material escrito solicitado nesta atividade deve ser produzido de acordo com asnormas da ABNT1, com o seguinte padro:

x em papel branco, formato A4;x com margens esquerda e superior de 3cm, direita e inferior de 2cm;x fonte Times New Roman tamanho 12, cor preta;x espaamento duplo entre linhas;x se houver citaes com mais de trs linhas, devem ser em fonte tamanho 10, com

um recuo de 4cm da margem esquerda e espaamento simples entre linhas;x com capa, contendo:

x nome de sua Unidade de Ensino, Curso e Disciplina;x nome e RA de cada participante;x ttulo da atividade;x nome do professor(a) da disciplina;x cidade e data da entrega, apresentao ou publicao.

ETAPA 1 (tempo para realizao: 5 horas)

9 Aula-tema: Introduo e Conceitos Bsicos. Expresses Regulares. GramticaRegular.

Esta atividade importante para que voc possa entender o processo de representaode problemas em uma forma que seja passvel de computao, utilizando os conceitos delinguagem e gramtica vistos nas primeiras aulas da disciplina.

7/31/2019 ATPS LFA

4/6


Diego Daniel Duarte

Pg. 4 de 6

Para realiz-la, importante seguir os passos descritos.

PASSOS

Passo 1 (Aluno)

Faa uma pesquisa para determinar as regras do xadrez referentes ao posicionamento, movimentao das peas e a Notao Algbrica utilizada para descrever essasmovimentaes. Utilize o documento contendo as regras do Xadrez disponibilizado em (Acesso em: 26 out. 2010) como base para a suapesquisa. Discuta os resultados da pesquisa com o grupo para garantir que todos tenham omesmo entendimento.

Passo 2 (Equipe)

Acessem (Acesso em: 26 out. 2010) e joguemuma partida de xadrez on-line com os membros do seu grupo para validar as regras eperceber a utilizao das Notaes Algbricas para descrio das jogadas.

Passo 3 (Equipe)

Elaborem, com base na pesquisa realizada, uma expresso regular e/ou uma gramticaregular capaz de representar uma sequncia de movimentos utilizando Notao Algbricapara a pea cavalo.

Passo 4 (Equipe)

Montem um relatrio denominado O Passeio do Cavalo, distribudo em dois captulos.Apresentem o problema no captulo 1, que dever ter o ttulo Descrio do Problema.Nomeiem o captulo 2 como Descrio Textual dos Movimentos do Xadrez e descrevamnele as especificaes e formalismos definidos nessa etapa. Acrescente a esse relatrio umacapa contendo a nome do relatrio e os nomes dos integrantes do grupo.


9 Aula-tema: Autmatos Finitos Determinsticos. Autmatos Finitos NoDeterminsticos.

Esta atividade importante para que voc aprimore o seu entendimento dos conceitosde autmatos, desenvolvendo a capacidade de aplic-los para resoluo de problemascomputacionais.

Para realiz-la, importante seguir os passos descritos.

7/31/2019 ATPS LFA

5/6


Diego Daniel Duarte

Pg. 5 de 6

PASSOS

Passo 1 (Equipe)

Utilizem os teoremas apresentado no livro-texto e/ou na bibliografia complementar dadisciplina para elaborar um Autmato Finito No Determinstico que reconhea as sentenasgeradas pela gramtica/expresso regular definida na Etapa 1.

Passo 2 (Equipe)

Definam um Autmato Finito Determinstico equivalente ao Autmato Finito NoDeterminstico especificado no Passo 1 desta etapa. Consulte o livro-texto para identificar oprocesso para construo de um Autmato Finito Determinstico equivalente a um AutmatoFinito No Determinstico.

Passo 3 (Equipe)

Estendam o relatrio O Passeio do Cavalo adicionando o captulo 3 denominadoReconhecimento da Entrada. Descreva nesse captulo os formalismos reconhecedoresdefinidos nesta etapa.


9 Aula-tema:Gramtica Livre de Contexto. Autmato com Pilha.

Esta atividade importante para que voc possa verificar se uma sequncia demovimentaes uma sequncia vlida para uma pea.Para realiz-la, importante seguir os passos descritos.

PASSOS

Passo 1 (Equipe)

Definam uma gramtica livre de contexto capaz de produzir sequncias de movimentosvalidos para a pea cavalo. Para tanto, considere cada casa como uma varivel que gera a

notao da pea quando posicionada nessa casa seguida das variveis representando aspossveis casas que a pea pode assumir atravs de uma movimentao vlida.

Passo 2 (Equipe)

Utilizem os teoremas apresentados no livro-texto e/ou bibliografia complementar dadisciplina para elaborar o autmato com pilha que reconhece as produes da gramticadefinida no Passo 2 dessa etapa.

Passo 3 (Equipe)

Adicionem ao relatrio O Passeio do Cavalo o captulo 4 com o ttulo Reconhecimentodos Movimentos do Cavalo, contendo a descrio dos formalismos geradores ereconhecedores definidos nessa etapa.

7/31/2019 ATPS LFA

6/6


Diego Daniel Duarte

Pg. 6 de 6


9 Aula-tema:Gramticas Sensveis ao Contexto. Mquina de Turing.

Esta atividade importante para que voc possa validar se a soluo apresentada

atende restrio de que todas as casas do tabuleiro sejam visitadas.Para realiz-la, importante seguir os passos descritos.

PASSOS

Passo 1 (Equipe)

Definam uma Mquina de Turing que receba como entrada uma sequncia demovimentaes e simule o AFD definido na Etapa 2 para validar se a sequncia valida.

Passo 2 (Equipe)Estendam essa mquina para que ela simule o Autmato com Pilha definido na Etapa 3 paravalidar se os movimentos so vlidos.

Passo 3 (Equipe)

Adicionem a essa mquina uma segunda fita. Gravem nessa fita as casas para a qual a pease movimenta se, e somente se, essa casa no constar na fita. Depois de validar a sequnciade movimentos, validem se todas as 64 casas do tabuleiro constam na segunda fita.

Passo 4 (Equipe)

Estendam o relatrio Passeio do Cavalo adicionando o captulo 5, com o ttulo Validaodo Problema. Descrevam nesse captulo a Mquina de Turing projetada nessa etapa.

Documents

ATPS LFA