決定性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を使う方法しか思いつかなかった。