[프로그래밍언어개론] Finate Automata의 수학적 정의와 연습

서론

Finate automata를 정의하는 방법과 이를 이용해 아호-코라식을 정의해봅시다.

유한 오토마타

유한 오토마타는 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$로 정의됩니다.

기호	의미
$Q$	상태(state)의 유한 집합
$\Sigma$	입력 알파벳(terminal symbol)의 유한 집합
$\delta: Q \times \Sigma \to Q$	전이 함수(transition function)
$q_0$	시작 상태(start state), $q_0 \in Q$
$F \subseteq Q$	종료(accepting) 상태들의 부분집합

이를 이용해 아호-코라식을 정의해봅시다.

아호-코라식

아호-코라식이 뭔데

어떤 문자열 $s$에서 원하는 문자열 패턴 $p$가 여러 개 주어지고 이 각각의 패턴이 몇 번 존재하는지 파악하고 싶다고 합시다.

brute-force 방식으로는 뭐 각 패턴에 대해, 문자열 각 부분을 매칭하는 것을 반복하면 되겠지만, 이는 매우 비효율적입니다.

왜냐면, 문자열 $s$를 한 글자 한 글자 읽을 때 지금까지 읽은 문자열에 대해 손해가 발생하기 때문입니다.

그렇다면 이 지금까지 읽은 문자열을 재활용할 수 있을까요?

따라서 이것을 재활용하기 위한 알고리즘이 바로 Aho-corasick입니다.

트라이

간략하게 설명하자면, 여러 문자열의 문자에 대해 노드라고 생각하면, 여러 문자열을 하나의 트리로 만들 수 있습니다. 이것을 트라이라고 합니다.

실패함수의 재귀적 특성

사실 이게 아호-코라식의 핵심인데, 인터넷에 좋은 양질의 자료가 있으니 설명을 대체합니다.

링크

수학적 정의

상태 집합 Q

PatternSet에서 임의의 어떤 패턴의 어떤 접두사에 해당하는, 쉽게 생각해서 트라이 구조의 모든 노드의 집합이 상태 집합이 될 수 있습니다.

$Q = {\, q \mid \exists\, p \in \text{PatternSet},\, v \in \Sigma^* \text{ such that } p = qv \,}$

입력 심볼 집합 Σ

영어 알파벳 26개만 사용가능하다고 해봅시다.

$\Sigma = { a, b, c, \ldots, z }$

전이 함수 δ

트라이에서 상태 q에서 문자 a로 자식이 있으면

\[\delta(q,a) = \begin{cases} \mathrm{goto}(q,a), & \text{if } a \text{가 } q \text{의 자식이면},\\[6pt] \delta\bigl(\mathrm{failure}(q),\,a\bigr), & \text{otherwise}. \end{cases}\]

실패 함수 failure()

\[\text{failure}(q) = \begin{cases} q_0, & \text{if } q = q_0,\\[6pt] \delta\bigl(\text{failure}(p),\,a\bigr), & \text{otherwise}. \end{cases}\]

여기서

• $p$는 상태, $q$의 부모 상태
• $a$는 $p \xrightarrow{a} q$인 엣지의 라벨
  로 정의할 수 있습니다.

초기 상태 $q_0$

빈 문자열을 나타내는 상태입니다. (루트)

$q_0 = \epsilon$

종료(출력) 상태 집합 F

$F = {\, q \in Q \mid \exists\, p \in \text{PatternSet} \text{ such that } p = q \,}$

정리

이로써 유한 오토마타를 이용해 아호-코라식을 정의해봤습니다!