🚀 구 - 구조 문법 (Phrase-Structure Grammars)

• 문법 G는 다음과 같은 네 원소 쌍으로 정의 된다 .

G = (V,T,S,P)

V : 변수(variables)라 부르는 객체들의 유한 집합.

• 모든 기호 V = N(비단말 기호)∪T

T: 단말 심벌(terminal symbols)이라 불리는 객체들의 유한 집합.

*단말 기호는 더 이상 다른 것으로 치환될 수 없음.

S: 시작 변수(start variable). V의 원소인 특별한 시작을 나타내는 심벌이다. (비단말 기호)

P: 생성규칙들(productions)의 유한집합. (문법 구조)

🚀 생성 규칙 (Productions)

• 생성 규칙이 문법 G의 핵심이다.
  하나의 string을 다른 string으로 변환하는 방법을 규정.
  다음과 같은 형태를 갖는다.

x -> y

Case 1.

• string w가 XzY라고 가정하자.이 때 생성규칙 z -> k를 적용하여 XkY인 string z를 얻었다고 하면,
  - w ⇒ z 로 표현할 수 있다.

이에 대해서는 다음과 같이 설명한다.

w가 z를 유도한다 (x derives z)
z가 w로부터 유도된다.(z is derived from w)

• 생성 규칙을 임의로 적용하여 문자열을 만들 수 있다. 생성 규칙은 적용 가능하면 언제든지 사용할 수 있고 필요한만큼 사용할 수 있다.

Case 2.

만약 다음과 같이 유도할 수 있다면,

w1⇒w2⇒...⇒wn

w1이 wn을 유도한다 한다. (w1 derives wn)
또한 다음과 같이 표기 한다.

  ∗
W1⇒Wn

∗은 W1 에서 Wn을 유도하기까지 0 ~ n 단계를 거칠 수 있음을 의미한다.

🚀 언어 L(G)

문법 G = (V,T,S,P)으로 생성되는 언어 L(G)를 아래와 같이 정의 한다.

• w : string 문자열
• T* : S부터 시작 했고, 더 이상 치환 할 수 없는 단말 기호들의 모음.
• S : 시작 변수

*Ex)
G = (N, T, S, P)
N = {S, A}
T = {a, b}
P = {S->aA, S->b, A->aa}
L(G) = aaa,b

*Ex)
G = (N, T, S, P)
N = {S}
T = {0, 1}
P = {S-> 11S, S->0}
L(G) = 0,110,11110,1111110...

🚀 문법의 유형 (Types of Grammars)

- Type 0 : 무 제약 언어 / 문법의 생성 규칙이 존재 X

- Type 1 : 문맥 의존 언어

- Type 2 : 문맥 자유 언어

- Type 3 : 정규 언어

• 컴퓨터 처리가 가능한 경계선은 type 2이다. 문맥 자유 언어와 정규 언어에서는 잘 다뤄짐.

문법 분류:

*W1은 좌변을 의미한다.

• |w1|≥2 인 경우
  type 0일 경우, 왼쪽, 오른쪽 아무런 제약이 없다.
  type 1일 경우, xw1y -> xw2y 형식이다. //좌우에 x, y가 있을 때 치환된다.
  x, y가 공백 문자열일 수도 있다. but w는 λ(empty string)가 아니다.
  
• |w1|=1 인 경우
  type 2일 경우, 아무런 제약이 없다.
  type 3일 경우, 오른쪽에 제약이 존재한다. // 비 단말 기호가 나온다면 오른쪽 끝 또는 왼쪽 끝에 존재.

L = {(a^m)(b^n) | m, n≥0}을 생성하는 문법은?
N = {S}
T = {a, b}
S
P = {S->aS, S->Sb, S->λ}

생성 규칙에서 |w1|(좌변)=1이고 , 오른쪽이나 왼쪽 끝에 NonTerminal 기호가 있으므로 Type3 정규 언어이다.

L = {(a^n)(b^n) | n≥0}을 생성하는 문법은?
N = {S}
G = {a, b}
S
P = {S->aSb, S->λ}

생성 규칙에서 |w1|(좌변)=1이고 , 오른쪽이나 왼쪽 끝에 NonTerminal 기호가 없으므로 Type2 문맥 자유 언어이다.

L = {0ⁿ1ⁿ2ⁿ | n=0,1,2,3,... }
N = {S}
G = {0,1,2}
S
P = {S->0 S->AB, S->λ, BA->AB, 0A->01, 1A->11, 1B->12, 2B->22}

생성 규칙에서 |w1|(좌변) >= 2이고 ,제약이 없으므로 Type 0 무 제약 언어이다.

Ref :
https://johngrib.github.io/wiki/f-l-a-01-02/
https://jihyeong-ji99hy99.tistory.com/51