決定性TMをシミュレートするシェルスクリプト

この休日、シェルスクリプトの基本を勉強したので、その記録として、決定性TM $M=(Q,S,S,\delta,q_0,\_,F)$ をシミュレートするシェルスクリプトを作りました。

TM.sh

#!/bin/bash

# Settings
Q=(0 1 2)
S=('_' 'a' 'b')
q0=0; F=(2); L=-1; R=1;

# delta: Q×S → Q×S×{L,R}
d0_=end;        d0a=(1 'a' $R); d0b=(0 'b' $R);
d1_=(2 'a' $L); d1a=(1 'b' $R); d1b=(1 'a' $L);
d2_=end;        d2a=end;        d2b=end;

# Controller
q=$q0; w="$1"; cur=0

echo "$w: "
while
	if [ 0 -le $cur -a $cur -lt ${#w} ]; then
		c=${w:$cur:1}
	else
		c='_'
	fi
	to=($(eval echo \${d"$q$c"\[\@\]}))
	echo '(q,w,cur): '"($q,$w,$cur)"
	if [ $to = end ]; then
		break
	fi
	q=${to[0]}
	if [ 0 -le $cur -a $cur -lt ${#w} ]; then
		w=$(echo "$w" | sed -e "s/./${to[1]}/$((cur + 1))")
	elif [ $cur -lt 0 ]; then
		for ((i=0; i < -cur - 1; ++i)); do
			w='_'"$w"
		done
		w="${to[1]}$w"
		cur=0
	else
		for ((i=0; i < cur - ${#w}; ++i)); do
			w="$w"'_'
		done
		w="$w${to[1]}"
	fi
	((cur += ${to[2]}))
	:
do :; done

for qf in "${F[@]}"; do
	if [ $qf -eq $q ]; then
		echo 'Accepted'
		exit 0
	fi
done
echo 'Rejected'
exit 1

この設定では次のようなTMを表しています:

だから、例えば、

$ bash TM.sh ab
ab: 
(q,w,cur): (0,ab,0)
(q,w,cur): (1,ab,1)
(q,w,cur): (1,aa,0)
(q,w,cur): (1,ba,1)
(q,w,cur): (1,bb,2)
(q,w,cur): (2,bba,1)
Accepted

とか、

$ bash TM.sh ababa
ababa: 
(q,w,cur): (0,ababa,0)
(q,w,cur): (1,ababa,1)
(q,w,cur): (1,aaaba,0)
(q,w,cur): (1,baaba,1)
(q,w,cur): (1,bbaba,2)
(q,w,cur): (1,bbbba,3)
(q,w,cur): (1,bbbaa,2)
(q,w,cur): (1,bbaaa,1)
(q,w,cur): (1,baaaa,0)
(q,w,cur): (1,aaaaa,-1)
(q,w,cur): (2,aaaaaa,-1)
Accepted

とか、

$ bash TM.sh bb
bb: 
(q,w,cur): (0,bb,0)
(q,w,cur): (0,bb,1)
(q,w,cur): (0,bb,2)
Rejected

など。深夜テンションで作ったので、間違い等あるかもしれません。

学べたこと

• bashがとても書きやすいこと(算術式のfor文など)。
• 多次元配列のサポートがないこと。
• 外部コマンドを使うよりも組み込みのコマンドで構成したほうが随分と速いこと。特にループ中のインクリメント をexprで行うとたかだか100回のループでも体感できる程度の遅延があった。
• 文字列の $n$ 文字目だけを置換するのが案外難しいこと。sedを使う方法しか思いつかなかった。