GNF는 Greibach Normal Form의 약자입니다. CFG(context free Grammar)는 모든 생산 규칙이 다음 조건 중 하나를 만족하는 경우 GNF(Greibach 정규 형식)입니다.

• ε을 생성하는 시작 기호입니다. 예를 들어 S → ε입니다.
• 터미널을 생성하는 비 터미널. 예를 들어 A → a입니다.
• 비터미널은 임의 개수의 비터미널이 뒤따르는 터미널을 생성합니다. 예를 들어 S → aASB입니다.

예를 들어:

 G1 = aB, A → aA G2 = S → aAB 

Grammar G1의 생성 규칙은 GNF에 지정된 규칙을 충족하므로 문법 G1은 GNF에 있습니다. 그러나 Grammar G2의 생성 규칙은 A → ε 및 B → ε에 ε이 포함되어 있으므로 GNF에 대해 지정된 규칙을 충족하지 않습니다(시작 기호만 ε을 생성할 수 있음). 따라서 문법 G2는 GNF에 없습니다.

CFG를 GNF로 변환하는 단계

1 단계: 문법을 CNF로 변환합니다.

주어진 문법이 CNF가 아닌 경우 CNF로 변환합니다. CFG를 CNF로 변환하려면 다음 항목을 참조할 수 있습니다. Chomsky 정규 형식

2 단계: 문법이 왼쪽 재귀에 존재하면 제거하십시오.

버블 정렬 자바

문맥 자유 문법에 왼쪽 재귀가 포함되어 있으면 이를 제거하세요. 왼쪽 재귀를 제거하려면 다음 항목을 참조할 수 있습니다. 왼쪽 재귀

3단계: 문법에서 주어진 생산 규칙을 ​​GNF 형식으로 변환합니다.

문법의 생성 규칙이 GNF 형식이 아닌 경우 이를 변환합니다.

자바에서 난수를 생성하는 방법

예:

 S → XB | AA A → a | SA B → b X → a 

해결책:

주어진 문법 G는 이미 CNF에 있고 왼쪽 재귀가 없으므로 1단계와 2단계를 건너뛰고 바로 3단계로 이동할 수 있습니다.

생산 규칙 A → SA는 GNF에 없으므로 S → XB | 생산 규칙 A → SA의 AA는 다음과 같습니다.

 S → XB | AA A → a | XBA | AAA B → b X → a 

생성 규칙 S → XB 및 B → XBA는 GNF에 없으므로 생성 규칙 S → XB 및 B → XBA에서 X → a를 다음과 같이 대체합니다.

 S → aB | AA A → a | aBA | AAA B → b X → a 

이제 왼쪽 재귀(A → AAA)를 제거하면 다음과 같은 결과를 얻습니다.

 S → aB | AA A → aC | aBAC C → AAC | ε B → b X → a 

이제 null 생산 C → ε을 제거하면 다음과 같은 결과를 얻습니다.

 S → aB | AA A → aC | aBAC | a | aBA C → AAC | AA B → b X → a 

생산 규칙 S → AA는 GNF에 없으므로 A → aC | 에이백 | | 생산 규칙 S → AA의 aBA:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → AAC C → aCA | aBACA | aA | aBAA B → b X → a 

생산 규칙 C → AAC는 GNF에 없으므로 A → aC | 에이백 | | 생산 규칙 C의 aBA → AAC:

 S → aB | aCA | aBACA | aA | aBAA A → aC | aBAC | a | aBA C → aCAC | aBACAC | aAC | aBAAC C → aCA | aBACA | aA | aBAA B → b X → a 

따라서 이것은 문법 G에 대한 GNF 형식입니다.

자바에서 배열을 정렬하는 방법