CSセミナー005 正規言語の和集合演算・スター演算

今回は、正規言語の演算のうち、和集合演算とスター演算について説明します。

今回のソースコード

和集合演算

正規言語の和集合演算を数式で記述すると次のようになります。
A ∪ B = { x | x ∈ A または x ∈ B }
例えば、「みかん」という文字列を認識する言語と「りんご」という文字列を認識する言語を和集合演算すると、「みかん」と「りんご」の両方を認識する言語になります。

ソースコードを次に示します。

automaton.kn(抜粋)

; ２つのオートマトンの和集合演算を行うクラス
class Union(@Automaton)
    +var automatonA: @Automaton
    +var automatonB: @Automaton

    +*func isAccepted(): bool
        ret me.automatonA.isAccepted() | me.automatonB.isAccepted()
    end func

    +*func put(c: char)
        do me.automatonA.put(c)
        do me.automatonB.put(c)
    end func

    +*func clone(): @Automaton
        var res: @Union :: #@Union
        do res.automatonA :: me.automatonA.clone()
        do res.automatonB :: me.automatonB.clone()
        ret res
    end func
end class

+func makeUnion(a: @Automaton, b: @Automaton): @Automaton
    var res: @Union :: #@Union
    do res.automatonA :: a.clone()
    do res.automatonB :: b.clone()
    ret res
end func

テストコードを次に示します。

test_union1.kn

; test_union1.kn

func runAutomaton(automaton: \automaton@Automaton, str: []char): bool
    var a: \automaton@Automaton :: automaton.clone()
    for i(0, ^str - 1)
        do a.put(str[i])
    end for
    ret a.isAccepted()
end func

var automaton: \automaton@Automaton

func check(str: []char)
    var res: []char ::
    |@runAutomaton(@automaton, str) ?("受理", "拒否")
    do cui@print("入力=\"\{str}\", 結果=\{res}\n")
end func

; 文字列をオートマトンに変換する関数
func toAutomaton(str: []char): \automaton@Automaton
    var res: \automaton@Automaton
    do res :: \automaton@makeOneChar(str[0])
    for i(1, ^str - 1)
        do res :: \automaton@makeConcatenation(
        |res, \automaton@makeOneChar(str[i]))
    end for
    ret res
end func

func main()
    alias a: \automaton@Automaton
    do cui@print("test kuina or chan\n")
    do @automaton :: \automaton@makeUnion(
    |@toAutomaton("くいな"), @toAutomaton("ちゃん"))
    do @check("")
    do @check("くいな")
    do @check("ちゃん")
    do @check("くいなちゃん")
    do @check("く")
    do @check("ち")
    do cui@print("test kuinachan or rokusai\n")
    do @automaton :: \automaton@makeUnion(
    |@toAutomaton("くいなちゃん"), @toAutomaton("６さい"))
    do @check("")
    do @check("くいな")
    do @check("ちゃん")
    do @check("くいなちゃん")
    do @check("６さい")
    do @check("くいなちゃん６さい")
end func

実行結果を次に示します。

スター演算

スター演算はある言語の繰り返しを認識する言語を生成する演算です。数式で示すと以下のようになります。
A* = { x1 x2 ... xk | k ≥ 0 で、各々の xi について xi ∈ A }
例えば、「くいなちゃん」という文字列を認識する言語にスター演算を適用すると、空文字列「」、「くいなちゃん」、「くいなちゃんくいなちゃん」などを認識する言語が生成されます。

次にソースコードを示します。

automaton.kn(抜粋)

; オートマトンのスター演算を行うクラス
class Star(@Automaton)
    +var automaton: @Automaton {テンプレート}
    +var listA: list<@Automaton> {実働}

    *func ctor()
        do me.listA :: #list<@Automaton>
    end func

    +*func isAccepted(): bool
        if(^me.listA = 0)
            ret true
        end if
        do me.listA.head()
        while(!me.listA.term())
            if(me.listA.get().isAccepted())
                ret true
            end if
            do me.listA.next()
        end while
        ret false
    end func

    +*func put(c: char)
        if(^me.listA = 0)
            do me.listA.add(me.automaton.clone())
        else
            do me.listA.head()
            while loop(!me.listA.term())
                if(me.listA.get().isAccepted())
                    do me.listA.add(me.automaton.clone())
                    break loop
                end if
                do me.listA.next()
            end while
        end if
        do me.listA.head()
        while(!me.listA.term())
            do me.listA.get().put(c)
            do me.listA.next()
        end while
    end func

    +*func clone(): @Automaton
        var res: @Star :: #@Star
        do res.automaton :: me.automaton
        ret res
    end func
end class

+func makeStar(a: @Automaton): @Automaton
    var res: @Star :: #@Star
    do res.automaton :: a
    ret res
end func

スター演算の実装の仕方は連結演算のそれに似ています。空文字列の扱いは少しトリッキーになっています。

次にテストコードを示します。

test_star1.kn

; test_star1.kn

func runAutomaton(automaton: \automaton@Automaton, str: []char): bool
    var a: \automaton@Automaton :: automaton.clone()
    for i(0, ^str - 1)
        do a.put(str[i])
    end for
    ret a.isAccepted()
end func

var automaton: \automaton@Automaton

func check(str: []char)
    var res: []char ::
    |@runAutomaton(@automaton, str) ?("受理", "拒否")
    do cui@print("入力=\"\{str}\", 結果=\{res}\n")
end func

; 文字列をオートマトンに変換する関数
func toAutomaton(str: []char): \automaton@Automaton
    var res: \automaton@Automaton
    do res :: \automaton@makeOneChar(str[0])
    for i(1, ^str - 1)
        do res :: \automaton@makeConcatenation(
        |res, \automaton@makeOneChar(str[i]))
    end for
    ret res
end func

func main()
    alias a: \automaton@Automaton
    do cui@print("test kuina*\n")
    do @automaton :: \automaton@makeStar(@toAutomaton("くいな"))
    do @check("")
    do @check("くいな")
    do @check("くいなくいな")
    do @check("くいなくいなくいな")
    do @check("くいなくいなくいなちゃん")
    do cui@print("test (kuina or rokusai)*\n")
    do @automaton :: \automaton@makeStar(
    |\automaton@makeUnion(@toAutomaton("くいな"), @toAutomaton("６さい")))
    do @check("")
    do @check("くいな")
    do @check("ちゃん")
    do @check("６さい")
    do @check("くいなちゃん６さい")
    do @check("くいな６さい")
    do @check("くいな６さい６さいくいな")
end func

次に実行結果を示します。

まとめ

有限オートマトンと、それに関する３つの演算（連結演算・和集合演算・スター演算）を示しました。有限オートマトンに対してこれらの演算を適用しても有限オートマトンが得られることが分かっています。示したソースコードでは定義を満たす最も簡潔な実装を行っているので実行効率は悪いものとなっています。

正規言語は有限オートマトンで認識可能な言語のことです。プログラミング言語で用いられている正規表現は正規言語のアイディアがもとになっていますが、より実用的なインターフェースが用意されており、アルゴリズムの工夫により高速に動作するようになっています。次回は、Kuinの正規表現ライブラリについて学んでみましょう。