Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

AprendizZ

Outro exercicio com autómato finito.

Mensagens Recomendadas

AprendizZ

Boas,

Mais uma vez venho pedir ajuda, novamente com autómatos finitos.

Desta vez pretendo simplificar um autómato que já criei.

O exercício tem a ver com a criação de um AF que aceite cadeias de "palavras" que só aceitam {0,1,#}, segundo a seguinte regra w1#w2 (w1 e w2 = cadeias binárias). Estas cadeias binárias não podem começar por 0, excepto um único 0. Outra regra é que w1 tem de ter paridade igual a w2, ou seja se w1 termina em 0 (par) então w2 tb termina em 0, o mesmo para 1 (ímpar), w1 e w2 têm de terminar com 1.

Eis alguns exemplos de "palavras" aceites:

0#0
110#110
100#10
1110011100#0
1111000001#1111000001
1111000110#1111000110
1111001100#1111000110
100000100010#100000100010
0#100100010010
1111000001#1
1#1
11#11
101#1
0#1010

e exemplos de "palavras" não-aceites:

0
1
#
1010
0101
11#0
1100#0011
00#00
0#00
00#0
11#000
11100#00100
111001#0000
1111100100#11111001
1000000000#11111001
1111100100#00111001
100100010010#100100010011
1#100100010010
00000000#1
1#00000000
10#01
100100010010#100100010011
1#100100010010

Entretanto já fiz o seguinte AF:

P2a.png

A ajuda que preciso é para simplificar este autómato, pois acho que tem estados a mais e não estou a ver como reduzi-lo.

Obrigado.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Existem métodos para simplificação de autómatos finitos, talvez queiras seguir um deles.

Procura um pouco que de certeza que encontras, "deterministic finite automata minimization". Já passou algum tempo desde que dei isso na faculdade, a única coisa que tenho aqui a jeito é código para o fazer..

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Logo à partida, os teu estados Q2, Q7 e Q19 não fazem sentido. São estados não finais sem retorno para qualquer outro estado.

E acredito qua hajam outras situações similares, mas o teu Q5: # -> Q6 pode passar directamente para Q12, eliminando o Q6 e o Q8.

Mais um edit... Q1: # -> Q11, eliminando o Q3, Q4 e Q17.

Portanto, numa vista rápida consegui remover-te 8 estados desse autómato :)


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
AprendizZ

Obrigado pessoal, era mesmo isso que pretendia (estou a precisar de mais prática nisto).

O autómato ficou bastante mais reduzido: :P

P2b.png

Agora vou para a segunda fase do exercício, que sinceramente não sei como encaixa-lo no AF que já está feito.

Já agora para quem me puder ajudar na etapa seguinte, eis o enunciado do exercício todo.

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:

(i) 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),

(ii) 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 assim:
   Podemos facilmente definir a noção de prefixo para uma palavra y. A palavra x será um
   prefixo de y se existe uma palavra z tal que y = xz. Dizemos ainda que x é um prefixo
   próprio de y se x é prefixo de y e x diferente de y. Da mesma forma x é um sufixo de y se existe
   uma palavra z tal que y = zx. Mostre que se A é uma linguagem regular, também o será a
   linguagem:
   NOPREFIX(A) = {w pertence A | nenhum prefixo próprio de w pertence a A}:

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).

Uma ajudinha será sempre bem vinda. Obrigado. :thumbsup:

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Reparei que ainda consegues simplificar mais o autómato. O Q5 e o Q10 podem ser o mesmo estado, e o Q8 e o Q1 também.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
AprendizZ

Obrigado a todos os que me ajudaram... a ver a luz.  :thumbsup:

Afinal a solução ao problema é simples. Consegui passar de um autómato de 20 estados (no inicio) para um de 8.

Ora para quem ler o enunciado (que complica mais do que explica) precisa de um AF que aceite palavras w1#w2 sobre um alfabeto {0,1,#}, segundo as regras indicadas.

Nada como fazer no papel as combinações das palavras todas e eliminar as que não seriam aceites. Verificar-se-ia a existência de uma lógica de palavras tipo:

w1 - todas as cadeias binárias são admitidas;

w2 - 1 (para w1 terminadas em 1) - 0,10,110,1110, 11110, etc. (para w1 terminadas em 0).

E pronto, agora é só fazer o autómato.

Até breve.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.