[오토마타] context free grammar - 문맥 자유 문법(CFG)

 

정규 언어보다 한 단계 높은 계층, 문맥 자유 언어

 

 

 

 

"문맥 자유 언어"(context-free language, CFL)는 컴퓨터 과학과 형식 언어 이론에서 주로 사용되는 용어이다. 문맥 자유 언어는 특정한 규칙 집합에 의해 생성될 수 있는 문자열의 집합을 나타내며, 이러한 규칙 집합은 보통 "문맥 자유 문법"(context-free grammar, CFG)이라고 한다.

---

문맥 자유 문법 (Context Free Grammars)

 

문맥 자유 문법 정의:

 

문맥 자유 문법은 4가지의 요소가 있다. G = ( V, Σ, R, S)

 

V: 변수(Variables) 혹은 비단말(Non-terminal)이라고 한다.

Σ: 단말(terminal == 알파벳)의 집합이며, 앱실론 ε 을 포함

R: 생성(productions) 규칙의 집합

S: 시작 변수(start variable)

 

GPT 답변

문맥 자유 문법은 다음과 같은 구성 요소로 이루어져 있습니다:

1. 비터미널 심볼(Non-terminal symbols): 다른 심볼로 대체될 수 있는 심볼입니다.
2. 터미널 심볼(Terminal symbols): 더 이상 대체되지 않고 언어의 문자열을 구성하는 기본 심볼입니다.
3. 생성 규칙(Production rules): 비터미널 심볼을 터미널 심볼 또는 다른 비터미널 심볼의 시퀀스로 대체하는 규칙입니다.
4. 시작 심볼(Start symbol): 언어를 생성하기 시작하는 데 사용되는 특별한 비터미널 심볼입니다.

문맥 자유 언어의 주요 특징은 각 생성 규칙이 "단일 비터미널 심볼이 다른 심볼 시퀀스로 대체되는" 형태를 가진다는 것입니다.

 

예를 들어, 다음은 간단한 문맥 자유 문법의 예입니다.

1. S→aSb
2. S→ϵ

위의 문법은 문자 'a'와 'b'로 구성된 균형 잡힌 괄호 문자열을 생성할 수 있습니다: "", "ab", "aabb", "aaabbb", ...

 

문맥 자유 문법은 G는 모든 생성 규칙이 다음과 같은 형식 문법을 말합니다.

 

A -> a

 

A는 V의 원소이고, a는 V 혹은 Σ의 원소이다.

 

※ 모든 Regular Grammar는 항상 CFG이다.
- 단, 역은 성립하지 않는다.

※ 모든 Linear Grammar는 항상 CFG이다.
- 단, 역은 성립하지 않는다.

---

parsing(파싱)

- 문장을 문법적 유도를 통하여 설명하는 과정

- 문장의 구조를 표현하는 방법 중 하나

- L(G)에 속하는 (w)가 유도되는데 사용된 일련의 생성규칙들을 찾는 과정

 

examples of context-free grammars

example1)

{a^ib^j | i > j >=0 }

start : S, terminal = a, b , variable = S

S -> aS | aSb | a

 

example2)

{a^ib^jc^k | i = j+k, i, j, k>=0}

start = S1, terminal = a, b, c , variable = S1, S2

S -> aSc | S2

S2 -> aS2b | ε