チューリング・マシン

TuringMachine.rb

require 'test/unit'
# 要 
# $ gem install test-unit

require 'set'


LEFT  = 'L'
RIGHT = 'R'

BLANK = 'B'



# チューリング・マシン
# M = (Q, \Sigma, \Gamma, \delta, q_0, q_{acc}, q_{rej})
class TuringMachine 

	MAX_TAPE_LENGTH = 30

	def initialize q_set, sigma, gamma, delta, q_initial, q_accept, q_reject

		# テープを空白文字で埋める
		@tape = Array.new(MAX_TAPE_LENGTH)
		MAX_TAPE_LENGTH.times do |i|
			@tape[i] = BLANK
		end

		# ヘッド位置
		@head = 0

		@delta = delta

		@q_initial = q_initial
		@q_accept  = q_accept
		@q_reject  = q_reject

		@q_current = q_initial
		@q_set = q_set
		
	end


	# テープに入力文字列を読み込み，チューリング・マシンを初期化する
	def set input_string
		input = input_string

		input.length.times do |i|
			@tape[i] = input[i]
		end

		@q_current = @q_initial
		@head = 0

	end


	# チューリング・マシンを 1 ステップ進める
	def step
		cell = @tape[@head]

		result = @delta.call(@q_current, cell)

		# 内部状態を変化
		@q_current = result[0]

		# テープのセルを書き換え
		@tape[@head] = result[1]

		# 停止したら true をかえす
		if self.isHalted then
			return true

		else
			# ヘッドを移動
			if result[2] == LEFT then
				@head -= 1
			elsif result[2] == RIGHT then
				@head += 1
			end

			return false

		end

	end


	# 停止状態かどうか
	def isHalted 
		if @q_current == @q_accept || @q_current == @q_reject then
			return true
		else
			return false
		end

	end


	# 受理状態かどうか
	def isAccepted
		if @q_current == @q_accept then
			return true
		else
			return false
		end

	end


	# 現在のチューリング・マシンの状態を出力
	def dump
		@tape.each do |cell|
			if cell == BLANK
				print ' '
			else
				print cell
			end
		end

		puts ""

		@head.times do |index|
			print " "
		end

		puts "*"

		@head.times do |index|
			print " "
		end

		puts @q_current

		puts ""

	end

end


# 状態遷移機械
class State
	def initialize id, name
		@id   = id
		@name = name
	end

	def equal? other
		@id == other.id
	end

	def to_s
		"<#{@name}>"
	end

	attr_reader :id 

end




if __FILE__ == $0 then

	# テストコード
	class TC_TuringMachine < Test::Unit::TestCase


		def setup
			# 入力アルファベット
			sigma = Set.new ['0', '1']

			# テープアルファベット
			gamma = Set.new ['0', '1', '$', '#', 'B']


			# 内部状態の集合
			q_set     = Set.new
			id = 0

			q_accept  = State.new id, "q_acc"
			q_set.add q_accept
			id += 1

			q_reject  = State.new id, "q_rej"
			q_set.add q_reject
			id += 1

			q_0       = State.new id, "q_0"
			q_set.add q_0
			id += 1


			q_1       = State.new id, "q_1"
			q_set.add q_1
			id += 1

			q_2       = State.new id, "q_2"
			q_set.add q_2
			id += 1

			q_3       = State.new id, "q_3"
			q_set.add q_3
			id += 1


			# 入力した {0, 1} の文字列に対し，
			#   0と1 が一致したら accept，
			#   そうでなければ    reject 
			# を返すチューリング・マシン
			delta = Proc.new do |q_current, cell|
				# q_0 のとき
				if q_current == q_0 then
					if cell == '0' then
						[q_1, '$', RIGHT]
					elsif cell == '1' then
						[q_2, '$', RIGHT]
					elsif cell == '&' then
						[q_0, '&', RIGHT]
					elsif cell == BLANK then
						[q_accept, BLANK, RIGHT]
					else
						[q_reject, BLANK, RIGHT] #reject
					end

				# q_0 のとき
				elsif q_current == q_1 then
					if cell == '0' then
						[q_1, '0', RIGHT]
					elsif cell == '1' then
						[q_3, '&', LEFT]
					elsif cell == '&' then
						[q_1, '&', RIGHT]
					else
						[q_reject, BLANK, RIGHT] #reject
					end

				elsif q_current == q_2 then
					if cell == '0' then
						[q_3, '&', LEFT]
					elsif cell == '1' then
						[q_2, '1', RIGHT]
					elsif cell == '&' then
						[q_2, '&', RIGHT]
					else
						[q_reject, BLANK, RIGHT] #reject
					end

				elsif q_current == q_3 then
					if cell == '0' then
						[q_3, '0', LEFT]
					elsif cell == '1' then
						[q_3, '1', LEFT]
					elsif cell == '&' then
						[q_3, '&', LEFT]
					elsif cell == '$' then
						[q_0, '$', RIGHT]
					else
						[q_reject, BLANK, RIGHT] #reject
					end

				else
					[q_reject, BLANK, RIGHT] #reject

				end


			end


			# チューリング・マシンを定義
			@machine = TuringMachine.new q_set, sigma, gamma, delta, q_0, q_accept, q_reject

		end


		def test_case1
			# 入力文字列
			input = "00101111100001"

			@machine.set input
			#@machine.dump
			while [email protected] 
				#@machine.dump
			end
			#@machine.dump

			assert( @machine.isAccepted, "input: \"#{input}\" was expected to be accepted" )

		end


		def test_case2
			# 入力文字列
			input = "0010111111"

			@machine.set input
			#@machine.dump
			while [email protected] 
				#@machine.dump
			end
			#@machine.dump

			assert( [email protected], "input: \"#{input}\" was expected to be not accepted" )

		end


		def test_case3
			# 入力文字列
			input = "00101111110000000"

			@machine.set input
			#@machine.dump
			while [email protected] 
				#@machine.dump
			end
			#@machine.dump

			assert( [email protected], "input: \"#{input}\" was expected to be not accepted" )

		end


	end

end