[계산이론](12)[Context Free Language]

이전에는 R.L에 대해 다뤘고, 이번에는 그보다 더 넓은 범위인 Context-Free-Language를 다루고자 한다.

 

Context Free Grammer

교체규칙의 모음 (꽤 재귀적임)
    예) A -> 00B (A를 00B라는 걸로 교체하시오)
    이떄, 같은 variable이라면 이렇게 연결해서 쓸 수 있다
        A->B, A->C를 A->B|C 이렇게

• variable(A, B...): 실제 다른 것으로 교체되는 부분
  start variable: 시작하는 변수 (명시되있지 않으면 맨 첫줄의 왼쪽 변수)
• terminal($\sum$): 변수가 아닌 alphabet
  이떄, context free grammer로 생성될 수 있는 모든 문자열의 집합을 context free grammer라고 한다.

규칙

1. start variable을 찾아 그 규칙부터 시작
2. 변환 후 들어있는 변수를 왼쪽으로 두는 규칙을 아무거나 적용
3. 어떤 변수도 남아있지 않을 때까지 반복

• 예) 규칙이 다음과 같을 때 해당 grammer로아무거나 만들어보셈
  S -> 0S1T ...(1)
  T -> SS ...(2)
  S -> @ ...(3)
  일단 시작인 S에서 시작해
  S => 0S1T (1 적용)
  => 0S1SS (2 적용)
  => 0@1SS (3 적용)
  => 0@1@S (3 적용)
  => 0@1@@ (3 적용)
  변수가 남지 않았으므로, 해당 문법으로 0@1@@을 만들 수 있다.

 

parse tree

grammer에서 derivation을 통해 만든 string을 보여주는 그림
terminal은 아래에, 변수는 위쪽에...
아까 예시를 parse tree로 만들면 다음과 같다.

 

수학적 정의

정의 $(V, \sum, R, S)$

• V: variable의 유한집합
• $\sum$: 변수가 아닌 문자의 유한집합
  $V\cap \sum = \emptyset$
• R: rule의 집합
  R: $V \rightarrow V\cup \sum$
• S: start variable
  $S \in V$
  근데 단순히 rule만 늘어놓아도 V, $\sum$, S는 확정할 수도 있다.