Exercícios Hopcroft

Questão 2.2.4.a:

2.2.4.a

Questão 2.2.4.b:

questão 2.2.4.b

Questão 2.2.5.c:

questão 2.2.4.c

Questão 2.2.5.a, representação gráfica do autômato que modela o jogo:

Questão 2.2.1a

O estado EEE simboliza esquerda, esquerda, esquerda. O estado DDE simboliza direita, direita, esquerda e assim por diante. O estado EEE’ simboliza o estado EEE final. Todos que tem um ‘ são finais. Um esboço para a função delta:

2.2.5

3.1.3.b – O conjunto de todos os strings com um número igual de 0’s e 1’s, tais que nenhum prefico tenha dois 0’s a mais que o 1’s, nem dois 1’s a mais que os 0’s.

Não entendi bem esta. 0011 tem nos dois primeiros digitos dois zeros a mais que uns, que são nenhum. Da mesma maneira nos dois últimos dígitos. Um palpite seria (10)*+(01)* 😛

3.1.3.c – A expressão regular O conjunto de strings de 0’s e 1’s cujo número de 0’s é divisível por 5 e cujo número de 1’s é par.

Usando algo como força bruta para resolver o problema.

Para formar o 5 zeros eu posso fazer assim:

5=5 ou 5=4+1 ou5=3+1. Ou seja, com 5 zeros, com 4 zeros mais 1 zero ou com 3 zeros e com 1 um. Respectivamente, com 5 zeros, com 4 zeros e 1 um ou com 1 zero e 4 uns ou com 3 zeros e 2 uns e com 2 zeros e 3 uns.

Para se fazer 5 zeros é assim: (00000)*. Para se fazer 4 zeros e 1 um assim (00001+00010+…)*. Para se fazer 1 zero e 4 uns assim (11110+11101+…)*. Para se fazer 3 zeros e 2 uns assim (11100+11010+…)*. Para se fazer 2 zeros e 3 uns (00011+00101+…)*. Então para resolver o problema usa-se uma dessas formas, assim:

( (00000)* + (00001+00010+…)* + (11110+11101+…)* + (11100+11010+…)* + (00011+00101+…)* )*

Expandindo os … para as expressões restantes, temos a expressão completa, assim:

((00000)*+(00001 + 00010 + 00100 + 01000 + 10000)* +(11110 + 11101 + 11011 + 10111 + 01111)* +(11100 + 11010 + 10110 + 01110 + 11001 + 10101 + 01101 + 10011 + 01011 + 00111)*+(00011 + 00101 + 01001 + 10001 + 00110 + 01010 + 10010 + 01100 + 10100 + 11000)*)*

3 Comentários »

RSS feed for comments on this post. TrackBack URI

  1. […] Exercícios Hopcroft […]

  2. As fotos estão bem ruins. 😦
    Mas é mais para mim usar quando eu precisar.

  3. A 3.1.3 estava errada. 😦


Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Crie um website ou blog gratuito no WordPress.com.
Entries e comentários feeds.

%d blogueiros gostam disto: