<< Prev | - Up - |
Implement your own Map
function by using a for
loop with a collect
feature.
Write a function Add1ToInts
adds 1
to all numbers in a list of numbers. The challange is to write your function such that it never blocks even if some of the numbers in the list are still unknown (i.e. a free logic variable). For instance:
{Inspect {Add1ToInts [1 _ 3 _ 4]}}
should return [2 _ 4 _ 5]
in the inspector.
(Extrapunkt) Reduce an until
loop to a for
loop.
Write a function that tests whether a record contains a node which is labeled with the atom got_it
. Use an exception to quit the recursion once successful.
The following functor automaton.oz
exports a function Reach
that should compute the set of states that can be reached by a given finite automaton when reading a given word. But there is a bug in the functors definition. Find the bug and correct it.
Install the packages Abstract.ozf
,
safe the functor automaton.oz
in a file of the same name and write an Oz-Makefile to compile it with the debugger option -g
,
debug the test program for automaton.oz
for the functor below, and correct the bug once you found it.
Here comes the functor automaton.oz
.
functor
import
Abstract at 'x-ozlib://oz-kurs/Abstract.ozf'
export
Reach
define
%% ReachByLetter computes the set of states that the
%% Automaton can reach from States via a single Letter
fun{ReachByLetter Automaton States Letter}
Reached = {Abstract.newBag}
for State in States do
for NextState in Automaton.trans.State.Letter do
{Reached.put NextState}
end
end
States = {Reached.toList}
in
States
end
%% ReachByWord computes the set of states that the
%% Automaton can reach from States via a given Word
fun{ReachByWord Automaton States Word}
case Word
of nil then States
[] Letter|RestWord then
NextStates = {ReachByLetter Automaton States Letter}
in
{ReachByWord Automaton NextStates RestWord}
end
end
%% Reach computes the set of states that the
%% Automaton can reach via a given Word
fun{Reach Automaton Word}
{ReachByWord Automaton Automaton.init Word}
end
end
You can use the following program to test the above functor from the OPI (from where it is easy to run the debugger).
declare [Auto] = {Module.link ['automaton.ozf']}
declare Automaton = unit(trans:unit(p:unit(1:[q] 2:nil)
q:unit(1:[p] 2:[q r])
r:unit(1:nil 2:nil))
init:[p]
fin:[q])
{Browse {Auto.reach Automaton [1 1 1 2 1]}}
A transducer is a finite automaton where transitions additionally produce output. For the purpose of this exercise, we suppose that each transition from state S
to state S'
has 1 input symbol I
and 1 output symbol O
:
I
S -----------> S'
O
You must first extend the representation of an automaton to allow the specification of an output symbol for each transition.
With a transducer, we don't simply reach a state: we reach it together with an output produced sofar. For this reason, a word is not simply accepted or rejected: when it is accepted, it is accepted with a corresponding output. We call the pair of a state that is reached together with the output produced sofar a token. You must modify the code for Reach
provided in the previous execise to collect tokens.
Then you must abstract over what gets collected so that your code can serve either to collect the reachable states or the reachable tokens.
You should then package your Reach
function into a library and use it to instantiate a function that collects reachable states and one that collects reachable tokens.
<< Prev | - Up - |