CS 워크숍 002 제한된 오토매틱

프로그래밍 언어에서 사용하는 정규 표현식은 자동 이론에서 파생된 것이지만 자동 이론에서 말하는 정규 표현식과 프로그래밍 언어의 정규 표현식의 의미는 다르다.이 세미나에서 먼저 자동 이론에서의 정규적 표현을 소개한 다음에 프로그래밍 언어의 정규적 표현을 설명한다.
자동 이론 중의 정규 언어(regulanguage)는 유한 자동어나 유한 상태기(finite state machine)가 식별하는 언어이다.언어는 문자열을 식별하는 집합을 가리킨다.
예를 들면, "나는 사람이다."일본어지만 "주름을 억제할 수 있다."일본어 아니에요.따라서 이론적으로 일본어를 일본어로 해석할 수 있는 문자열 집합으로 정의한다.
정규 언어는 학문의 기초 중의 기초이기 때문에 그렇게 할 수 없다.그래, 긴장을 풀자.
유한 자동 수정 정의
제한된 자동 그림을 다음 다섯 그룹으로 정의합니다:.
1. 상태의 유한 집합이라고 불린다
2. 자모의 유한한 집합이라고 불린다
3. 상태와 알파벳을 매개 변수로 하고 상태를 반환값의 변환 함수로 한다
4. 시작 상태
5. 접수 상태의 집합 (set of acceptstates)
지장
다음 그림에서'지짱'이라는 글자만 자동으로 표시한다fsm1.

상태는 q1에서 q8까지의 8가지 상태입니다.문자는 Kuin이 처리하는 모든 문자입니다.시작 상태는 q1입니다.접수 상태는 q7입니다.그럼 이 자동 기어 프로그램을 써볼게요.
automaton1.kn

enum State
    q1
    q2
    q3
    q4
    q5
    q6
    q7
    q8
end enum

func transitionFunction(state: @State, alphabet: char): @State
    if(state = %q1)
        if(alphabet = 'く')
            ret %q2
        else
            ret %q8
        end if
    elif(state = %q2)
        if(alphabet = 'い')
            ret %q3
        else
            ret %q8
        end if
    elif(state = %q3)
        if(alphabet = 'な')
            ret %q4
        else
            ret %q8
        end if
    elif(state = %q4)
        if(alphabet = 'ち')
            ret %q5
        else
            ret %q8
        end if
    elif(state = %q5)
        if(alphabet = 'ゃ')
            ret %q6
        else
            ret %q8
        end if
    elif(state = %q6)
        if(alphabet = 'ん')
            ret %q7
        else
            ret %q8
        end if
    else {stateがq7かq8のとき}
        ret %q8
    end if
end func

; この関数はオートマトンを動作させて、
; 入力の文字列を受理すればtrue, 拒否すればfalseを返します。
func runAutomaton(str: []char): bool
    var state: @State :: %q1
    for i(0, ^str - 1)
        do state :: @transitionFunction(state, str[i])
    end for
    if(state = %q7)
        ret true
    else
        ret false
    end if
end func

; この関数はオートマトンに文字列を入力し、
; 入力と結果を印字します。
func check(str: []char)
    do cui@print("入力=\"" ~ str ~ "\", 結果=")
    if(@runAutomaton(str))
        do cui@print("受理\n")
    else
        do cui@print("拒否\n")
    end if
end func

func main()
    do @check("くいなちゃん")
    do @check("くいな")
    do @check("くいなちゃんくいなちゃん")
    do @check("kuin")
end func

프로그램은 실행 환경에서 CUI를 설정한 후 실행됩니다.실행 결과는 다음과 같습니다.

자동 쿠마의 입력에 "짱"이라는 문자열을 입력했을 때만 수리할 수 있습니다.자동으로 식별되는 언어를 수학적으로 쓰면A = {"くいなちゃん"}이다.
참고로 문자열\"에 대한 설명은 도피 서열 중의 하나로 "를 나타낸다.
연습 1 Kuin에는 조건 연산자라는 연산자가 있습니다.이 연산자를 사용하여 [automatoon1.kn]을 단축하십시오.(힌트: 쿠인%q1 등 모르는 경우@State형일 경우 출연)
연습 2 [automatoon1.kn]를 조건 연산자가 아닌 논리적 적 연산자로 줄여 보십시오.
연습 3 [automatoon1.kn]의 check 함수 내의 do cui@print("入力=\"" ~ str ~ "\", 結果=")에 대한 기술은 도피 서열로 ~(수조 연결 산자)를 대체하여 다시 쓰십시오.
**
수고하셨습니다.
나는 이번 수준이 지난번보다 좀 높아졌다고 생각한다.쿠인의 기본 구조에 익숙하지 않은 사람은 쿠인 튜토리얼을 만들어 볼 수 있다.매우 즐거운 훈련.
연습의 답안
연습1
automaton2.kn (발췌)

func transitionFunction(state: @State, alphabet: char): @State
    if(state = %q1)
        ret alphabet = 'く' ?(%q2 $ @State, %q8 $ @State)
    elif(state = %q2)
        ret alphabet = 'い' ?(%q3 $ @State, %q8 $ @State)
    elif(state = %q3)
        ret alphabet = 'な' ?(%q4 $ @State, %q8 $ @State)
    elif(state = %q4)
        ret alphabet = 'ち' ?(%q5 $ @State, %q8 $ @State)
    elif(state = %q5)
        ret alphabet = 'ゃ' ?(%q6 $ @State, %q8 $ @State)
    elif(state = %q6)
        ret alphabet = 'ん' ?(%q7 $ @State, %q8 $ @State)
    else {stateがq7かq8のとき}
        ret %q8
    end if
end func

연습2
automaton3.kn (발췌)

func transitionFunction(state: @State, alphabet: char): @State
    if(state = %q1 & alphabet = 'く')
        ret %q2
    elif(state = %q2 & alphabet = 'い')
        ret %q3
    elif(state = %q3 & alphabet = 'な')
        ret %q4
    elif(state = %q4 & alphabet = 'ち')
        ret %q5
    elif(state = %q5 & alphabet = 'ゃ')
        ret %q6
    elif(state = %q6 & alphabet = 'ん')
        ret %q7
    else
        ret %q8
    end if
end func

연습do cui@print("入力=\"\{str}\", 結果=")