CS 워크숍 004 정규 언어의 연결 연산

그러면 지난번에는 쿠인 언어로 특정 문자를 인식하는 자동어를 만들었다.이번에는 정규 언어의 연결 연산을 가져와 특정 문자열을 식별하는 자동 그림을 만듭니다.
이번 소스 코드
이번에 만든 자동 코드를 표시합니다.
automaton.kn (발췌)

; ２つのオートマトンの連結演算を行うクラス
class Concatenation(@Automaton)
    +var automatonA: @Automaton {テンプレートと実働を兼ねる}
    +var automatonB: @Automaton {テンプレートのみ}
    +var listB: list<@Automaton> {実働}

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

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

    +*func put(c: char)
        if(me.automatonA.isAccepted())
            do me.listB.add(me.automatonB.clone())
        end if
        do me.automatonA.put(c)
        do me.listB.head()
        while(!me.listB.term())
            do me.listB.get().put(c)
            do me.listB.next()
        end while
    end func

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

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

이번 코드에는 자동 조판 병행 실행 구조가 설치되어 있다.Concatenation 클래스 구성원 변수listB는 Kuin의list라는 데이터 구조를 사용하여 여러 개의 자동 수를 병행적으로 실행할 수 있습니다.Kuin의list에 대해 다음 문서가 비교적 상세합니다.
Kuin 인덱스 사전 3은 다양한 데이터 구조를 처리합니다.
합병 연산은 수학적으로 다음과 같다.
A ○ B={xy|x 왜 A 그리고 y 왜 B}
구체적으로 말하면'에서 내용'이라는 문자열을 식별하는 언어와'에서 내용'이라는 문자열을 식별하는 언어는 병합 연산에서'에서 내용'이라는 문자열을 식별하는 언어가 된다.
원본 코드에서'템플릿'과'실제 작업'이라는 두 단어가 등장했다.'템플릿'은 Automaton류가'언어'로 취급되는 것을 가리키고,'실제 작업'은 Automaton류가 유한한 자동 기어로 취급되는 것을 가리킨다.언어는 받아들인 문자열의 집합이기 때문에 상태가 없다.하지만 유한한 자동 기어는 상태가 있다.언어와 자동 정정의 단계를 분리할 수 있지만 복제 상태 이외의 구성원만 있으면 자동 정정을 복제할 수 있기 때문에 언어와 자동 정정은 같은 단계에서 처리된다.
이번에 제작된 연결 연산을 테스트하는 코드를 나타낸다.
test_concatenation1.kn

; test_concatenation1.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 main()
    alias a: \automaton@Automaton
    var ku: a :: \automaton@makeOneChar('く')
    var i: a :: \automaton@makeOneChar('い')
    var kui: a :: \automaton@makeConcatenation(ku, i)
    do @automaton :: kui
    do cui@print("check kui:\n")
    do @check("")
    do @check("く")
    do @check("い")
    do @check("くい")
    do @check("くいな")
    var kuinachan: a
    |::
    |\automaton@makeConcatenation(\automaton@makeOneChar('く'),
    |\automaton@makeConcatenation(\automaton@makeOneChar('い'),
    |\automaton@makeConcatenation(\automaton@makeOneChar('な'),
    |\automaton@makeConcatenation(\automaton@makeOneChar('ち'),
    |\automaton@makeConcatenation(\automaton@makeOneChar('ゃ'),
    |\automaton@makeOneChar('ん'))))))
    do @automaton :: kuinachan
    do cui@print("check kuinachan:\n")
    do @check("")
    do @check("く")
    do @check("くい")
    do @check("くいな")
    do @check("くいなち")
    do @check("くいなちゃ")
    do @check("くいなちゃん")
    do @check("くいなちゃんく")
    do @check("くいなちゃんくいなちゃん")
end func

결과는 다음과 같다.

먼저,'쿠'를 식별하는 자동 단어와'쿠'를 식별하는 자동 단어를 병합하여'쿠'라는 문자열을 식별하는 자동 단어를 생성한다.그 다음에 각각'쿠','지짱','지짱','지짱','지짱'을 식별하는 자동어를 병합 연산을 통해 결합시켜 지짱을 자동으로 식별하고 테스트한다.나는 네가 두 가지 상황에서 정확한 동작을 알게 될 것이라고 생각한다.
정규 언어의 연산은 합병 연산 외에 집합 연산과 성형 연산도 있다.이런 것들을 조합하면 유한한 자동도를 만들어 복잡한 패턴을 식별할 수 있다.
그럼에도 불구하고 이번 세미나에서 설명한 원본 코드는 유한자동도 이론에 대해 우직한 처리를 하기 때문에 일반적으로 사용하는 정규 표현 라이브러리보다 훨씬 느리다.그러나 정규 표현의 사상이 정규 언어와 큰 관계를 가진다는 것을 이해하기 위해 이번에는 그 이론에 대해 우직한 편찬을 할 것이다.