#!/bin/sh

# This script transforms a Nondeterministic Finite Automaton (NFA)
# into a Deterministic one (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.

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"

# now output the state table

increment () {
    o=''
    while true
    do
        case "$out" in
	    0*) out=${o}1`echo $out | $dd bs=1 skip=1 2>/dev/null`
	    	return ;;
	    1?*) o=${o}0
		out=`echo $out | $dd bs=1 skip=1 2>/dev/null`
		;;
	    *)  go=false
	    	return ;;
	esac
    done
}

make_slist () {
    slist=''
    n="$1"
    shift
    while true
    do
    	case "$n" in
	    0*) shift
		n=`echo "$n" | $dd bs=1 skip=1 2>/dev/null`
	    	;;
	    1*) slist="$slist $1"
	    	shift
		n=`echo "$n" | $dd bs=1 skip=1 2>/dev/null`
	    	;;
	    *)  slist=`echo "$slist" | $dd bs=1 skip=1 2>/dev/null`
	    	return ;;
	esac
    done
}

new_state='new_state () {
    case "$1" in
'

new_final='new_final () {
    case "$1" in
'

base="$out"

case "$out" in
    ?*) go=true
	while $go
	do
	    make_slist "$out" $states
	    fin=N
	    for st in $slist
	    do
	    	if is_final $st
		then
		    fin=F
		fi
	    done
	    echo "$fin $out"
	    new_state="$new_state	$out) st='$slist' ;;
"
	    case "$fin" in
		F) new_final="$new_final	$out) return 0 ;;
" ;;
	    esac
	    increment
	done
	;;
esac

new_state="$new_state    esac
}
"
new_final="$new_final    esac
    return 1
}
"

eval "$new_state"
eval "$new_final"

echo

# 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"

# output the transition table

add_bits () {
    neu=$new
    bit=$1
    new=''
    ggo=true
    while $ggo
    do
    	case "$bit" in
	    1*) new=${new}1
	    	bit=`echo $bit | $dd bs=1 skip=1 2>/dev/null`
	    	neu=`echo $neu | $dd bs=1 skip=1 2>/dev/null`
		;;
	    0*) case "$neu" in
		    1*) new=${new}1 ;;
		    0*) new=${new}0 ;;
	    	esac
	    	bit=`echo $bit | $dd bs=1 skip=1 2>/dev/null`
	    	neu=`echo $neu | $dd bs=1 skip=1 2>/dev/null`
		;;
	    *)  ggo=false
	    	;;
	esac
    done
}

case "$base" in
    ?*) go=true
	o="$base"
	out=""
	while $go
	do
	    case "$o" in
		?)  out=1$out
		    go=false
		    ;;
	    	?*) out=0$out
		    o=`echo "$o" | $dd bs=1 skip=1 2>/dev/null`
		    ;;
		*)  go=false ;;
	    esac
	done
	go=true
	pow=$out
	ifs="$IFS"
	IFS='+'
	set `echo $pow | $dd of=/dev/null bs=1 skip=2 2>&1`
	IFS="$ifs"
	len="$1"
	set $states
	make_bits='make_bits () {
    case "$1" in
'
	while $go
	do
	    case $# in
	    	0)  go=false ;;
		*)  make_bits="$make_bits	$1) bits=$pow ;;
"
		    shift
		    pow=0`echo $pow | $dd bs=1 count=$len 2>/dev/null`
	    esac
	done
	make_bits="$make_bits    esac
}
"
	eval "$make_bits"
	go=true
	while $go
	do
	    for symbol in $symbols
	    do
		new=$base
		new_state "$out"
		for nst in $st
		do
		    for dst in $states
		    do
		    	if is_trans $nst $symbol $dst
			then
			    make_bits $dst
			    add_bits $bits
			fi
		    done
		done
	    	echo "$out $symbol $new"
	    done
	    increment
	done
	;;
esac