[계산이론](1)[오토마타와 언어]

기본 정리

기본 구조는 집합론, 자료구조를 참고
set VS sequence

• set: 중복없고 순서없는 원소의 모음
• sequence: 중복허용, 순서존재하는 원소의 모음

alphabet: 문자의 set = symbols
    예) $\sum_1 = {a, n, s, y}$
string: alphabet으로 이루어진 sequence
    특히 빈 string을 $\epsilon$ 이라고 한다.
    예) $\sum_1$의 string의 예시 = ansy, as, yana
language: string의 집합
    예) language of $\sum_1$ = {ansy, as}, {$\epsilon$, ya}

 

유한 오토마타 (finit automata)

유한 오토마타: 상태(Q)가 유한집합인 오토마타
    state 외의 저장 공간이 없으므로 마르코프 체인마냥 동작한다.

 

상태 다이어그램 (state diagram)

오토마타의 연산 과정을 나타낸 다이어그램
각 원은 state를 나타낸다
각각 -> 는 transion을 나타낸다
    특히 시작 state가 없는 -> 가 가리키는 state는 시작 상태를 나타낸다.
◎는 accept 상태를 나타낸다

 

정의 ($Q$, $\sum$, $\delta$, $q_0$, $F$)

• states ($Q$)
  상태의 유한 집합
• alphabet ($\sum$)
  행동에 쓰이는 문자의 유한 집합
• transition funtion ($\delta : Q \times \sum -> Q$)
  행동 함수
  직접 순서쌍으로 표현하거나 표로 표현
• start state ($q_0 \in Q$)
  상태 중 1개
• accept state ($F ⊆ Q$)
  목표, 상태의 부분집합
      여러개 가능
      없어도 됨

형식(syntax): 오토마타가 받아들이는 형식인가?
의미(semantics): 오토마타가 무슨 기능을 하는가?

 

language of Machine: M이 accept하는 모든 string의 집합
     오토마타M이 어떤 string을 넣었을 때 결과적으로 accept한다면

     그 string은 M의 language에 포함된다고 말한다.
     이런 string을 전부 모은 집합을 A라고 할 때,
          L(M) = A 라고 적고
          M recognize A 또는 M accepts A라고 한다.

 

예) 다음 오토마타의 M의 state diagram을 보고 알아보자

M = ($Q$, $\sum$, $\delta$, $q_0$, $F$)으로 정의할 수 있다.

• $Q$ = {$q_1, q_2$}
• $\sum = {0, 1}$
• $\delta = {((q_1, 0), q_1), ((q_1, 1), q_2), ((q_2, 0), q_2), ((q_2, 1), q_1)}$
• $q_0 = q_1$
• $F = {q_2}$

이 오토마타의 syntax에 따라 L(M)에 포함되는 string을 찾아보면,
01, 000011, 0101 ....
즉, L(M) = { 1로 끝나는 string }
따라서 이 오토마타의 sementics는 1로 끝나는 string을 찾는 것이다.