Context-Free Language and Grammar

 

 

 

 

 

1. Context-Free Grammar

 

A context free grammar is a quadruple G=(V,T,S,P) where –V: a finite set variables (or non-terminals) –T: a finite set of terminals –S: the start symbol Î V –P: a finite set of productions V → (VUT)*

 

기본적으로 context-free grammar는 형식 자체는 Regular Grammar와 같지만, production rule에 해당하는 부분만 다릅니다.

다시 기억해보면, regular language는 right-linear language와 left-linear language만 취급합니다.

Context-Free grammar는 그것과는 다르게, 그냥 집합 V와 T의 합집합 안에만 있으면 됩니다.

 

이런 점에서 regular language보다는 훨씬 더 많은 language를 표현할 수 있게 되는데, 이 점을 context-free하다고 표현합니다.

 

 

 

2. 예시

 

1) palindrome

가장 대표적인 예시는 palindrome이 있습니다.

예를 들자면 토마토, eve, noon, refer 등이 있습니다.

 

구체적으로 표현하면 다음과 같습니다.

Palindromes over {a,b,c} –L={wxwR: wÎ{a,b,c}*, xÎ{a,b,c,l}} is context-free, but not regular. –Generated by ({S,T},{a,b,c},S,P) where P consists of eight rules:   S →  aTa | bTb | cTc | T   T →  S | a | b | c | l

 

 

3. CFL to CFG

예시를 통해 보도록 합시다.

 

1. Design a CFG that accepts L = { aⁿb^m : 0 <= n <=m <= 2n }

a) S →  aSb | aSbb | λ

 

2. Design  a CFG that accepts L = { ab : 0 <= n <=m <= 2n }

a) S → AB

A → aAb | λ

B → bBa | ba

 

이렇게 작성하면 된다는거!

문제풀때 체크할거는 따로 정리해서 올릴 생각입니다

 

4. 결론(CFL의 필요성)

 

CFL은 컴퓨터 언어에 있어서 전반적으로 중요한 의미를 가집니다.

'파싱'의 개념이 기본적으로 CFL에서 나왔기 때문입니다.

예시로 넣지는 않았지만, 괄호 작성 여부 체크하는 것도 CFL로 표현 가능합니다 (ex. 좌괄호'('를 10개 썼다면 우괄호')'를 10개 썼는가?)

그리고 당연히 복잡하겠지만, 기본적인 영어 문법도 CFL로 표현 가능합니다. 이건 좀 복잡해서 궁금하신 분들만 보시면 될 것 같네요.

 

Number of rules:  <SENTENCE> →  <NOUN-PHRASE><VERB-PHRASE>  <NOUN-PHRASE> → <CMPLX-NOUN> | <CMPLX-NOUN><PREP-PHRASE>  <VERB-PHRASE> → <CMPLX-VERB> | <CMPLX-VERB><PREP-PHRASE>  <CMPLX-NOUN> → <ARTICLE><NOUN>  <CMPLX-VERB> → <VERB> | <VERB><NOUN-PHRASE> …     <ARTICLE> → a | the  <NOUN>  → boy | girl | house  <VERB>  → sees | ignores Possible element:   a boy sees a girl   the girl ignores the boy

 

아무튼 다양한 것들을 표현할 수 있을 뿐더러, 이를 기반으로 작성되는 parsing tree의 경우 정말 많이 응용된다고 합니다.

암튼 중요하다는거~!

 

끝!