Fall 98, CSE 468: Solution of Assignment 2
The automaton
One possible automaton for L is M = (Q,Sigma,q0,A,delta),
where: Q = {0,1,2,3,4} (set of states), Sigma = {a,b,c} (alphabet), A = {0,3}
(acceptance states), q0 = 0 (initial state), and delta defined
as follows:
- delta(0,a) = 1, delta(0,b) = 0, delta(0,c) = 2
- delta(1,a) = 0, delta(1,b) = 4, delta(1,c) = 4
- delta(2,a) = 4, delta(2,b) = 4, delta(2,c) = 3
- delta(3,a) = 4, delta(3,b) = 3, delta(3,c) = 2
- delta(4,a) = 4, delta(4,b) = 4, delta(4,c) = 4
It is possible to show that this is actually
the minimum-state automaton recognizing L.
The program
We give the program in ML. The input string is codified
as a list of characters (this allows us to use pattern matching).
datatype alphabet = a | b | c;
fun delta(0,a) = 1 | delta(0,b) = 0 | delta(0,c) = 2
| delta(1,a) = 0 | delta(1,b) = 4 | delta(1,c) = 4
| delta(2,a) = 4 | delta(2,b) = 4 | delta(2,c) = 3
| delta(3,a) = 4 | delta(3,b) = 3 | delta(3,c) = 2
| delta(4,a) = 4 | delta(4,b) = 4 | delta(4,c) = 4;
fun delta_star(q,[]) = q
| delta_star(q,x::s) = delta_star(delta(q,x),s);
val initial_state = 0;
fun accept_or_reject q = if q = 0 orelse q = 3
then "accept"
else "reject";
fun check s = accept_or_reject(delta_star(initial_state,s));
Tests
- check [];
val it = "accept" : string
- check [a,a,b];
val it = "accept" : string
- check [a,a,b,c];
val it = "reject" : string
- check [a,a,b,a,a,c];
val it = "reject" : string
- check [a,a,c,c,a,a];
val it = "reject" : string