| Lex Spoon 2004-03-27, 12:10 am |
| Christian Heinze <171179@web.de> writes:
> This concrete example accepts the language (ab)*. However, this
> interpreter, simple as it is, accepts any non-deterministic
> automaton. I am allowed to specify several delta/3-rules, where on the
> receipt of a symbol X in state Q it is not determined with state would
> come next, e.g.:
>
> delta(q0,a,q2).
> delta(q0,a,q3).
>
> I'd like to limit the interpreter to the acceptance of deterministic
> state machines only.
I like your code, myself, and would simply write the delta's in order
so that you can visually scan and see if there are non-determinisms.
But something like this would seem to work:
nondeterministic :- delta(Q1, A, Q2),
delta(Q1, A, Q3),
Q2 /= Q3 .
deterministic :- not nondeterministic .
I don't know whether Prolog allows you to write "not
nondeterministic", but even if i doesn't you can use
"nondeterministic" and mentally reverse the result.
-Lex
|