Context Free Grammar, CYK(CKY) 알고리즘

다루는 내용

문맥 자유 언어
문맥 자유 문법
촘스키 정규형
CYK 알고리즘

---

문맥 자유 언어(Context-Free Language, CFL)

문맥 자유 언어(Context-free language, CFL)는 문맥 자유 문법이 생성하는 형식 언어이다. (같은 문법이 다른 언어를 생성할 수도 있다.)

---

문맥 자유 문법(Context-Free Grammar)

문법 \( G=(N, \Sigma, R, S) \) 에서 모든 생성 규칙이
$$ A\,\to\, w $$
의 형태이면 \(G\)를 문맥 자유 문법(Context-free grammer, CFG) 라고 한다. 이때 \( A \in N \) 이고, \( w \in (N\cup \Sigma)^{*} \) 이다.

여기서 \(N\)은 a finite set of non-terminal symbols, 즉 비말단 기호의 유한집합이고,

\(\Sigma\)는 a finite set of terminal symbols, 즉 말단 기호의 유한집합이고,

\(R\)은 a finite set of rules, 즉 문법 규칙의 유한집합이고,

\(S\in N\)은 distinguished start symbol, 즉 시작 기호이다.

---

??? : 뭔 소리야

Nonterminals(비말단 기호)는 이런 거다. \( N\)={S, NP, VP, PP, Noun, Verb, ...}

Terminals(말단 기호)는 이런 거다. \(\Sigma\)={I, am, he, go, school, literally...}

말단 기호는 이름 그대로, 문법 규칙에서 화살표 왼쪽에 올 수 없다. (V→eat 로 변환되는 건 가능하지만 그 반대는 안 된다는 뜻이다!)

A set of rules \(R\subseteq\){\(A\to\beta\) with \(A\in N\) and \(\beta\in (N\cup\Sigma)^{*}\)}

그러니까 문법 규칙 R이란, A가 \(\beta\)로 바뀌는 건데 이때 A는 nonterminal이고, \(\beta\)는 nonterminal과 terminal이 섞일 수 있는 문자열이라는 뜻이다. (애스터리스크는 클레이니 스타로, 1편에서 다루었다.)

문법 규칙의 예시로는,

DT → {the, a} N → {school, eraser, teacher} P → {in, at, with} NP → DT N NP → NP PP PP → P NP

이런 것들이 문법 규칙이다. (DT는 Determiner로 한정사라고 1장에서 언급했다!)

마찬가지로 Start symbol \(S\)는 nonterminal 집합의 원소라는 것이다.

---

Chomsky Normal Form(촘스키 정규형)

일반 CFG에서는 화살표 오른쪽에 여러 개의 비단말 기호와 단말 기호들이 들어갈 수 있다. 예를 들어

VP → NP have ADV PP

이런 문법이 있을 수 있다는 것이다. 하지만 Chomsky normal form은 오직 두 가지 유형의 문법 규칙만 갖는다.

화살표 오른쪽에 오직 두 개의 nonterminals. 예를 들어 VP → ADV VP 화살표 오른쪽에 오직 하나의 terminal. 예를 들어 VP → have

기호로 표현하면,

Rules are all either A→BC or A→a (with A, B, C is nonterminals and a is terminal)

그리고, 임의의 2형 언어(문맥 자유 언어)는 이 두 가지 종류만 가지고도 전부 표현 가능하다는게 촘스키 정규형 정리이다.

 

---

CYK 알고리즘

• Cocke-Younger-Kasami 알고리즘
• CKY 알고리즘이라고도 많이 불림
• 현재 모든 문맥 자유 문법을 파싱할 수 있는 가장 효율적인 알고리즘
• 문자열의 길이가 \(n\)일 때 \(O(n^3)\)의 시간복잡도를 가짐
• dynamic programming 사용
• 촘스키 정규형식으로 표현된 문법 사용(위에서 언급했듯이, 모든 2형 언어에 대해 사용 가능)
• 상향식 파싱 구조
• membership 문제(얘가 이 언어의 문자열이니?) 해결 가능

CYK 알고리즘보다 더 효율적인 알고리즘이 있지만 그것들은 특정한 문법 상황에서만 사용 가능하다.

말로 설명

 

---

그럼 여러 분석된 결과 트리들 중에 맞는 게 뭔지 어떻게 알까?

2편에서 다루었던 통계 기반 분석법을 활용한다. 이걸 Proablisitic Context-Free Grammars(PCFGs) 라고 한다.