#!/bin/sh

# This script minimises a Deterministic Finite Automaton (DFA)

# usual dd/sh intro

PATH=''
rm=/bin/rm
dd=/bin/dd
tmp=/tmp/nfa2dfa.$$
trap "$rm -f $tmp.?" 0 1 2 3

# the input file consists of three sections, separated by one single
# blank line

# the first section lists the input alphabet, one symbol per line

# the second section lists the internal states, one per line,
# in the format "F state" for final states and "N state" for
# nonfinal states

# the third section lists the transitions, in the format
# "state symbol new-state". The symbol "*" is allowed as an
# abbreviation, and it means "one transition per each input symbol"

true () { return 0 }
false () { return 1 }

# read the input alphabet. Since the output alphabet is the same, write
# it out at the same time

go=true
intsymbol='is_symbol () {
    case "$1" in'
symbols=''

while $go && read symbol
do
    case "$symbol" in
	*\ *) echo "Symbol cannot contain spaces" >&2
	    exit 1
	    ;;
    	'*') echo "Invalid symbol '*'" >&2
	    exit 1
	    ;;
    	?*) intsymbol="$intsymbol
	$symbol) return 0 ;;" ; symbols="$symbols $symbol" ; echo "$symbol" ;;
	*) go=false ;;
    esac
done
echo ''

intsymbol="$intsymbol
    	*) return 1 ;;
    esac
}"

eval "$intsymbol"

# now read the state table

go=true
out=''
finstate='is_final () {
    case "$1" in'
nonfinstate='is_state () {
    case "$1" in'
states=''

# if you understand the code please don't comment it. It spoils the fun.

while $go && read fin state
do
    case "$fin" in
    	f*|F*) finstate="$finstate
	$state) return 0 ;;" ; nonfinstate="$nonfinstate
	$state) return 0 ;;" ; states="$states $state"
		out="0$out" ;;
    	n*|N*) nonfinstate="$nonfinstate
	$state) return 0 ;;" ; states="$states $state"
		out="0$out" ;;
	?*) ;;
	*) go=false ;;
    esac
done

finstate="$finstate
    	*) return 1 ;;
    esac
}"

nonfinstate="$nonfinstate
    	*) return 1 ;;
    esac
}"

eval "$finstate"
eval "$nonfinstate"

# read transition table

is_trans='is_trans () {
    case "$1 $2 $3" in
'

while read state symbol next
do
    if is_state "$state" && is_state "$next"
    then
    	:
    else
    	echo "Invalid state name in transition '$state $symbol $next'" >&2
	exit 1
    fi
    case "$symbol" in
        '*') for symbol in $symbols
	    do
		is_trans="$is_trans	$state\ $symbol\ $next) return 0 ;;
"
	    done
	    ;;
	*) if is_symbol "$symbol"
	    then
		is_trans="$is_trans	$state\ $symbol\ $next) return 0 ;;
"
	    else
	    	echo "Invalid symbol in transition '$state $symbol $next'" >&2
		exit 1
	    fi
	    ;;
    esac
done

is_trans="$is_trans    esac
    return 1
}
"

eval "$is_trans"

# minimise the automaton

remove_state () {
    s="$1"
    _states="$states"
    states=''
    for state in $_states
    do
        case $state in
	    $s) ;;
	    *) states="$states $state" ;;
	esac
    done
}

go=true
while $go
do
    go=false
    states2="$states"
    for state1 in $states
    do
	set $states2
	shift
	states2="$*"
    	for state2 in $states2
	do
	    case $state1 in
	    	$state2) ;;
		*)  same=true
		    if is_final $state1
		    then
		    	if is_final $state2
			then
			    :
			else
			    same=false
			fi
		    elif is_final $state2
		    then
		    	same=false
		    fi
		    if $same
		    then
			for symbol in $symbols
			do
			    for state3 in $states
			    do
				if is_trans $state1 $symbol $state3
				then
				    if is_trans $state2 $symbol $state2
				    then
				    	:
				    else
				    	same=false
				    fi
				elif is_trans $state2 $symbol $state3
				then
				    same=false
				fi
			    done
			done
		    fi
		    if $same
		    then
		    	# states are equivalent - remove one of them
			remove_state $state2
			go=true
		    fi
		    ;;
	    esac
	done
    done
done

# output the state table

for state in $states
do
    if is_final $state
    then
    	echo "F $state"
    else
    	echo "N $state"
    fi
done
echo

# output the transition table

for state1 in $states
do
    for symbol in $symbols
    do
    	for state2 in $states
	do
	    if is_trans $state1 $symbol $state2
	    then
	    	echo "$state1 $symbol $state2"
	    fi
	done
    done
done