CNF는 Chomsky Normal Form의 약자입니다. CFG(context free Grammar)는 모든 생산 규칙이 다음 조건 중 하나를 만족하는 경우 CNF(Chomsky 정규 형식)입니다.
- ε 생성을 시작합니다. 예를 들어 A → ε입니다.
- 비터미널은 두 개의 비터미널을 생성합니다. 예를 들어 S → AB입니다.
- 터미널을 생성하는 비 터미널. 예를 들어 S → a.
예를 들어:
G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} Grammar G1의 생성 규칙은 CNF에 지정된 규칙을 충족하므로 문법 G1은 CNF에 있습니다. 그러나 Grammar G2의 생성 규칙은 S → aZ가 터미널과 비터미널을 포함하므로 CNF에 대해 지정된 규칙을 충족하지 않습니다. 따라서 문법 G2는 CNF에 없습니다.
자바에서 배열을 만드는 방법
CFG를 CNF로 변환하는 단계
1 단계: RHS에서 시작 기호를 제거합니다. 시작 기호 T가 작품의 오른쪽에 있는 경우 다음과 같이 새 작품을 만듭니다.
S1 → S
여기서 S1은 새로운 시작 기호입니다.
2 단계: 문법에서 null, 단위 및 쓸모 없는 생성을 제거합니다. CFG의 단순화를 참조할 수 있습니다.
3단계: 다른 비터미널 또는 터미널과 함께 존재하는 경우 생산의 RHS에서 터미널을 제거합니다. 예를 들어 생산 S → aA는 다음과 같이 분해될 수 있습니다.
S → RA R → a
4단계: 2개 이상의 비터미널로 RHS를 제거합니다. 예를 들어 S → ASB는 다음과 같이 분해될 수 있습니다.
S → RS R → AS
예:
주어진 CFG를 CNF로 변환합니다. 주어진 문법 G1을 고려하십시오:
라텍스 글꼴 크기
S → a | aA | B A → aBB | ε B → Aa | b
해결책:
1 단계: 시작 기호 S가 RHS에 나타나므로 새로운 프로덕션 S1 → S를 생성합니다. 문법은 다음과 같습니다:
S1 → S S → a | aA | B A → aBB | ε B → Aa | b
2 단계: 문법 G1에는 A → ε null 생성이 포함되어 있으므로 문법에서 이를 제거하면 다음이 생성됩니다.
디자인 패턴 자바
S1 → S S → a | aA | B A → aBB B → Aa | b | a
이제 문법 G1에는 단위 생산 S → B가 포함되어 있으므로 제거 결과는 다음과 같습니다.
S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a
또한 단위 생산 S1 → S를 제거하면 문법에서 이를 제거하면 다음과 같은 결과가 나옵니다.
S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a
3단계: 생산 규칙에서 S0 → aA | AA, S → AA | Aa, A → aBB 및 B → Aa, 터미널 a는 터미널이 아닌 RHS에 존재합니다. 따라서 터미널 a를 X로 교체하겠습니다.
S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a
4단계: 생성 규칙 A → XBB에서 RHS에는 두 개 이상의 기호가 있어 문법 생성에서 이를 제거합니다.
S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB
따라서 주어진 문법에 대해 이는 필수 CNF입니다.
부분 파생 라텍스