[Context-Free Grammers & Context-Free Language]
- 비유하자면, Context-Free Language는 Regular Language에 비유할 수 있다. CFG는 language를 묘사하는 방법...이고, DFA에 대응되는 것은 pushdown automata 인 것 같다.
- 중간 내용으로는, CFG가 재귀적 구조를 갖는다는 것, parser과 compilation에 CFG가 사용된다는 것, Parse Tree로 표현할 수 있다는 것이다.
- Context-Free Grammer로 만들어질 수 있는 모든 Language를 CFL라고 한다. (Language 개념에서 확장되어, Language를 만드는 것에 대한 개념이 생겼다고 이해했다.)
- CFG는 다음과 같은 정의를 갖는다.
G = ( V, 시그마, R, S)
V = variable의 유한 집합
시그마 = terminals의 유한 집합. *** V와 disjoint 해야함 !!! ***
R = rules의 유한 집합. rules는 variable 또는 a string of variables and terminals 가 되는 것을 말한다.
S = start Variable
여기서 variable과 terminals이 다르다는 것에 유의해야 한다.
variable은 symbol이고, terminals는 string을 구성하는 요소 중에 variable이 아닌 symbol! 쉽게 보면, 더이상 나누어 지지 않는 존재들이라고 이해할 수 있을 것 같다.
인상깊었던 것은 The language of the grammer. grammer에 대한 language 를 표현하는 방법이다.
- 집합기호를 잘 살펴보면, 시그마*로 이루어진 string w이고, S 가 rule의 *d에 의해 w를 생성하기만 하면 된다. 즉, 시그마는 terminals이니까!! [S가 rule의 스타에 의해 생성한 w가 터미널로만 이루어진 것]을 grammer의 language라고 한다.
그리고 앞으로는 Grammer을 formal한 정의로 보이지 않고, 간략하게 하나의 arrow 관계로 표현할 것이라고 한다.