📘
バイナリ文字列に1が偶数個含むことを受理するオートマトンの実装
バイナリ文字列に1が偶数個含むことを受理するオートマトンを実装します。
オートマトンの作成
初期状態はA、受理状態はAとなります。例えば、0、011、0101は受理されます。一方、1、01、010は受理されません。
以下は、画像生成の元データとなります。
a: {shape: circle}
b: {shape: circle}
a -> a :0
a -> b :1
b -> b :0
b -> a :1
オートマトンの実装
module Match
using Test
function match(input)
state = 'A'
for e in input
if state == 'A' && e == '1'
state = 'B'
elseif state == 'B' && e == '1'
state = 'A'
end
end
state == 'A'
end
function main()
@testset "受理する場合" begin
@test match('0') == true
@test match("011") == true
@test match("0101") == true
end
@testset "受理しない場合" begin
@test match('1') == false
@test match("01") == false
@test match("010") == false
end
end
end
if abspath(PROGRAM_FILE) == @__FILE__
using .Match
Match.main()
end
Discussion