Voltar à homepage de Daniel Graça

No ano letivo de 2011/12, os alunos deverão resolver 2 problemas na disciplina de LFA, cada um dos quais contribuindo 0,75 valores para a nota final. Os problemas devem ser resolvidos utilizando o software JFLAP.

Pequeno tutorial para o JFLAP

O JFLAP é um software que permite simular diversos modelos computacionais apresentados na cadeira de LFA. Para o seu funcionamento é necessário o ficheiro JFLAP.jar e a presença de Java. Nos problemas apenas serão utilizadas as funcionalidades do JFLAP para autómatos finitos, embora se recomende o uso deste software para experimentação com outros tópicos dados ao longo da cadeira (autómatos de pilha, máquinas de Turing, etc.).

A utilização deste software é intuitiva, estando disponível online um tutorial para a construção de autómatos finitos.

Depois de construir o autómato finito para cada um dos problemas, deve guarda-lo num ficheiro de extensão .jff e submete-lo ao Mooshak para validação.

Submissão de exercícios utilizando o Mooshak

Depois de obter o ficheiro .jff descrevendo o autómato que resolve um dos problemas, dirija-se ao site http://mooshak.deei.fct.ualg.pt/~mooshak/. Aí clique no botão "Login" e clique em "Register". Selecione o concurso "LFA1112_PX", onde X é o número do problema para o qual pretende submeter a sua solução. Por exemplo, se pretende submeter a sua solução para o problema 1, selecione o concurso "LFA1112_P1". Seguidamente crie um username com o seguinte formato: <nº aluno>_<primeiro nome>_<apelido>. Por exemplo, o nome poderia ser "27542_João_Sousa". Indique um email válido onde receberá a password que lhe permite aceder ao concurso, selecionando o grupo "Students".

Faça novamente login no site indicado acima, e aceda ao concurso pretendido. Clique no botão "Procurar" para selecionar o ficheiro que pretende submeter, carregando de seguida em "Submeter" para efetuar a submissão. Neste momento o sistema processará o ficheiro e verificará se a solução fornecida é correta ou não. Apenas as submissões cujo resultado seja "Accepted" são consideradas corretas. Todas as outras ("Wrong answer", "Runtime Error", etc.) são consideradas incorretas. Pode fazer tantas submissões quantas entender, sem penalização, desde que obtenha nalguma dessas submissões o resultado "Accepted".

Nota: O "Runtime Error" acontece quando não se utiliza o alfabeto pedido. Em particular se quiser fazer a mesma transição com o símbolo 0 e 1, não deve escrever "0,1" (senão o autómato só fará a transição no JFLAP se aparecer a palavra "0,1"), mas sim introduzir "0", carregar Enter, e introduzir "1". O "0" e o "1" aparecem um em cima do outro e não separados por uma vírgula.

Só serão consideradas soluções submetidas até às 24h do dia em que tiver lugar o exame de época normal de LFA.

Enunciado dos problemas

Seguidamente é apresentado o enunciado dos 2 problemas a resolver, que também pode encontrar no site do respetivo concurso no Mooshak.

Problema 1: Utilizando o programa JFLAP, construa um autómato finito que reconheça a linguagem A formada por todas as palavras w de {0,1}* que satisfazem simultaneamente as seguintes 3 condições:

  1. w representa um número binário (por exemplo 0, 1,110 representam números binários, o que não é o caso para as palavras 00 ou 0101),
  2. w, enquanto número binário, é divisível por 6 (por exemplo 110 [= 6], ou 10010 [= 18] são divisíveis por 6, mas 111 [= 7] já não o é. Consideramos que 0 é divisível por 6),
  3. w não contém a subpalavra 101.

Por exemplo 110110 [= 54] não pertence à linguagem A (embora o número seja divisível por 6, a palavra 110110 contém a subpalavra 101), enquanto 10010 [= 18] já pertence.

Problema 2: Considere a linguagem B formada por todas as palavras w de {0,1,#}* tais que w tem o formato w=w1#w2, onde w1 e w2 são palavras de {0,1}* que satisfazem simultaneamente as seguintes 2 condições:

  1. w1 e w2 representam números binários (por exemplo 0, 1,110 representam números binários, o que não é o caso para as palavras 00 ou 0101),
  2. Se considerarmos w1 e w2 como números binários, então w1 e w2 têm a mesma paridade (se um número é 0, consideramos que tem paridade par).

Por exemplo, 101#1 e 0#1010 são palavras de B, enquanto 11#0 e 0 já não o são.

Utilizando o programa JFLAP, construa um autómato finito que reconheça a linguagem C = NOPREFIX(B), onde NOPREFIX() está definido no exercício 31-a) das folhas de exercícios teórico-práticos disponível em http://w3.ualg.pt/~dgraca/Files/LFA/Exercicios_LFA.pdf.

Por exemplo, 101#01 não pertence a C (a palavra à direita do # não é um número binário), 10#100 não pertence a C (o seu prefixo próprio 10#10 pertence à linguagem B) assim como 10#1 (os elementos de NOPREFIX(B) pertencem a B, e como 10#1 não pertence a B, não pode pertencer a C). Por outro lado 10#0 ou 10#110 já pertencem a C (ambas as palavras pertencem a B e não admitem prefixos próprios que pertençam a B).