📘

バイナリ文字列に1が偶数個含むことを受理するオートマトンの実装

2023/05/16に公開

バイナリ文字列に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