[계산이론](13)[CFG 디자인]

 

R.L -> CFL

context free language가 regular language보다 더 넓은 범위라 했는데 그럼 regular language를 context free grammer로 표현할 수 있지 않을까?

 

CFG 디자인 팁

어떤 language를 CFG로 표현는 정형화된 방법은 딱히 없다...
그러나 좀 더 쉽게 바꾸는 팁은 있다!

1. 대부분의 CFL은 간단한 CFL의 모음이다

각각의 CFG을 만들고
    S1 -> ...
    S2 -> ...
 S -> S1 | S2 | ... 이렇게 합쳐버리기

 

예) ${0^n1^n \ | \ n \ge0} \cup {1^n0^n\ \ | \ n \ge 0}$을 CFG로 바꾸셈
    일단 각각을 만들고 그 다음 합치자!
    - ${0^n1^n \ | \ n \ge0}$의 CFG를 만들면
        A -> 0A1
        A -> ε
    - ${1^n0^n\ \ | \ n \ge 0}$의 CFG를 만들면
        B -> 1B0
        B -> ε
    이제 다음과 같은 rule을 추가하면 union이 된다
        S -> A | B

 

2. DFA로 만들고 하면 더 쉽다

만약 디자인하려는 language가 regular라면

1. DFA로 변환하고
2. DFA의 state, transition을 이용해 $(V, \sum, R, S)$ 를 정하면
   V = state
   $\sum$ = alphabet + ε
   R = (all transition) + (accept -> ε)
       이떄 transition var 앞에 input string을 써준다
   S = start state
   더 쉽게 알 수 있다.

예) 0이 홀수개인 language의 CFG?
    1. DFA는 간단히 그릴 수 있다

    2. $(V, \sum, R, S)$ 를 정하면
        - V = {$Q_1$, $Q_2$}
        - $\sum$ = {0, 1, ε}
        - S = {Q1}
        - R
            $Q_1$ -> 0$Q_2$
            $Q_1$ -> 1$Q_1$
            $Q_2$- > 0$Q_1$
            $Q_2$ -> 1$Q_2$
            $Q_2$ -> ε

 

3. 2개의 string이 있을 떄 2개가 뭔 관계가 있다면 변수 양쪽에 넣는걸로 나타낼 수 있다

예를 들어, 0이 1번 늘어날 때 1이 2번 늘어난다면 뭔가 0과 1 사이에 관계가 있다.
이 관계를 S -> 0S11 이런 식으로 표현한다.

 

4. 재귀는 자기 자신을 넣으면 된다

S -> 0S1마냥 자기 자신을 다시 넣으면
S => 0S1 => 00S11 => 000S111 => ....
이렇게 재귀를 구현할 수 있다.

 

Ambiguity (모호성)

같은 string이 2개 이상의 다른 parse tree로 나타날 때
그 string은 ambiguously하게 변환되었다고 하고,
그 grammer를 ambiguous하다 한다.

(몇몇 language는 ambiguous한 grammer로만 표현된다...)

 

주의) parse tree가 다르다는게 단순히 순서가 다른게 아니라 구조가 다르다는 것이다.
따라서 순서를 상관하지 않기 위하 parse tree를 그릴 때
leftmost derivation(왼쪽 먼저 연산)을 수행한다.