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*={x1x2...xk|k≥0, 각xixixi왜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

다음은 실행 결과를 보여 줍니다.

총결산
유한 자동도와 관련된 3개의 연산 (합병 연산, 집합 연산, 성형 연산) 을 보여 줍니다.우리는 유한한 자동 기어에 이런 연산을 적용해도 유한한 자동 기어를 얻을 수 있다는 것을 안다.상기 원본 코드는 정의에 부합되는 가장 간단한 실현 방식이기 때문에 실행 효율이 매우 떨어진다.
정규 언어는 유한하고 자동적으로 식별되는 언어다.프로그래밍 언어에서 사용하는 정규 표현식은 정규 언어의 생각을 바탕으로 하지만 더욱 실용적인 인터페이스를 제공하여 알고리즘에 공을 들여 고속으로 운행할 수 있다.다음에 Kuin의 정규 표현식 라이브러리를 배워봅시다.