Automato

[Pattyrds 0]

Olá galera!

 

Preciso trandormar um AFN com transiçoes vazias em um AFN sem transiçoes vazia, não tô conseguindo implementar. Se alguem puder me ajudar eu agradeço e muito.

[quitZAUMMM 18]

oq seria um AFN?

e outra oq jah rabisco?

[Pattyrds 0]

AFN significa automato finito não deterministico

[Kandrade 7]

Para implementar temos que saber como isso será feito.

Voce tem algum material que fala o que fazer nesse caso?

[Pattyrds 0]

tenho sim, tenho um exemplo de como é que faz.

[Kandrade 7]

Então poste o exemplo.

[Pattyrds 0]

Poss te passar por e-mail, pois o arquivo possui graficos e é um pouco grande.

[Kandrade 7]

Ok, passe para slack.kleber@gmail.com

[Pattyrds 0]

Já enviei. :D

[Kandrade 7]

Tenho uma idéia de como implementar, mas não será tão fácil.

Voce desenvolveu alguma coisa? Está usando uma linguagem de programação específica?

[Pattyrds 0]

Já implementei sim. Tô fazendo em c. Não se foi a melhor solução mais implementei com lista encadeada, agora só tá faltando o calculo das transições vazias.

Criei uma lista que recebe os estados, outra onde eu add o alfabeto e outro com o e-closure de cada estado.

[Kandrade 7]

Vamos tentar fazer com calma.

Agora voce precisa fazer o seguinte:

 

Cada estado precisa de uma lista e-CLOSURE(qx).

Essa lista será preenchida com estados que tenham caminho rotulado com vazio.

Veja naquele material que voce me passou que q0 tem caminho rotulado com vazio para os outros estados e q1 só tem com q2.

 

Acho que uma função cairia bem nesse caso.

Talvez uma função que verifique se há um caminho entre dois estados rotulado com vazio.

A função recebe um estado origem e outro destino e verifica se há o caminho retornando um boolean por exemplo.

 

Veja se consegue implementar.

[Pattyrds 0]

Eu fiz assim:

 

Uma lista encadeada para add os estados

Uma lista encadeada para add o alfabeto

e outra para add o e-closure, nesta lista possui o id(estado), a informação(e-closure) e o alfabeto.

ex:

typedef struct eclosure

{

char id[20];

char info[20];

char alfa[20];

struct eclosure *prox;

}Eclosure;

 

o que tá dando errado agora é o calculo,pois tenho q pegar o e-closure de cada estado e comparar com cada letra do alfabeto digitado.

ex:

estado(q0) possui o e-closure {q0,q1,q2}

aí tô tentando pagar dessa lista de eclosure pra fazer a comparação(q0,0)(q0,1).....

[Kandrade 7]

Bom, eu não entendi direito a estrutura que voce criou, mesmo assim vamos ver se voce consegue aplicar isso a seu código.

O que precisa fazer é isso:

 

- Cada estado será comparado com todas as entradas.

- A cada resultado voce armazenará a nova regra de transição.

 

vamos supor que eu tenha a seguinte entrada: 0 e 1. Além dos seguintes estados: q0,q1,q2.

 

Temos duas entradas para serem analisadas para cada estado.

Dentro de dois loop aninhados é possível fazer isso.

 

Na primeira iteração voce tem o estado q0 e a entrada 0.

Busque o eclosure do estado q0 que no seu exemplo será q0,q1,q2.

Agora para montar a nova regra voce precisa consultar a antiga.

 

q0 lê 0 vai pra onde? R: q0.

q1 lê 0 vai pra onde? R: vazio.

q2 lê 0 vai pra onde? R: vazio.

 

E por último voce precisa achar o eclosure da união dessas respostas.

Nesse caso seria o eclosure de q0 que é {q0,q1,q2}.

 

Portanto a nova regra será:

partindo de q0 lê 0 vai para {q0,q1,q2}.

 

Até completar seu AFN sem transições vazias.

[Pattyrds 0]

Mandei um trab pra seu e-mail de uma colega pra você dá uma olhada, tem um erro que n consegui identificar.

[Pattyrds 0]

galera ainda preciso de ajuda. quem puder ajudar eu agradeço.