construction FSA dans prolog

Question

On me demande de représenter un FSA dans prolog.

• Une fsa est une liste d'états.
• Un état est une structure avec l'état de foncteur et 3 arguments: un nom, une liste de transitions , et oui ou non pour indiquer si l'état est en cours d'acceptation ou pas.
• Une transition est une structure avec la transition de foncteur et 2 arguments: de, un caractère et un nom d'état.

Nos FSA n'ont pas de mouvements epsilon.

nondfsa(FSA) est vrai si FSA est non déterministe. Terminer nondfsa. Conseil: utilisez un prédicat auxiliaire , nondstate(State), ce qui est vrai si State a des transitions non déterministes . Vous pouvez ajouter des clauses pour la predicates.`

Je me donne la réponse comme suit:

nondfsa([Hstate | _ ]) 
    :- nondstate(Hstate). 
nondfsa([ _ | Tailstates]) :- 
    nondfsa(Tailstates). 

nondstate(state(_ , Transitions, _)):- 
    member(transition(Char, To1), Transitions), 
    member(transition(Char, To2), Transitions), 
    not(To1 = To2). 

quelqu'un peut-il expliquer à moi ce que chaque prédicat est en train de faire? Je suis très confus sur ce que ces lignes traduisent exactement. Je comprends Une fsa sans mouvements epsilon est non-déterministe si au moins un état a plus d'une transition avec le même caractère. Je ne comprends tout simplement pas ce qui se passe dans ce code.

Answer 1

Le code présenté est très simple et il serait bon d'apprendre à "lire" un prédicat Prolog.

nondfsa([Hstate | _ ]) :- 
    nondstate(Hstate). 
nondfsa([ _ | Tailstates]) :- 
    nondfsa(Tailstates). 

Ceci est un modèle Prolog très courant qui vérifie récursivement chaque élément d'une liste pour quelque chose. nondfsa/1 vérifie chaque élément de la liste. Si d'entre eux est un état non-déterministe (selon nondstate/1), alors nondfsa/1 réussit, ce qui signifie que le FSA est non-déterministe. Si nondstate/1 ne réussit pas pour un élément dans la liste donnée, alors nondfsa/1 échouera. La première clause vérifie la tête de la liste. La deuxième clause saute la tête et vérifie le reste de la liste. Dans l'appel récursif, Prolog recommence à la première clause, donc il vérifie simplement l'élément suivant via nondstate/1.

nondstate(state(_ , Transitions, _)):- 
    member(transition(Char, To1), Transitions), 
    member(transition(Char, To2), Transitions), 
    not(To1 = To2). 

nondstate/1 réussit si la donnée state/3 se trouve être non déterministe par une définition qui ne dépend que des transitions de cet état. Si vous lisez votre prédicat nondstate/1, vous pouvez voir ce que c'est.Le prédicat réussit si:

1. Je peux obtenir un membre de la liste des transitions
2. Je peux obtenir un autre membre de la liste des transitions en utilisant le même caractère (ce sera toujours réussir au moins une fois, en utilisant le même membre que dans l'# 1)
3. l'état de destination pour chacun des deux éléments sont différentes

en d'autres termes, un état est si non-déterministe, il y a un personnage qui a passage à au moins deux différents stat es.