CNF oznacza postać normalną Chomsky'ego. CFG (gramatyka bezkontekstowa) ma postać CNF (normalna postać Chomsky'ego), jeśli wszystkie reguły tworzenia spełniają jeden z następujących warunków:

• Rozpocznij generowanie symbolu ε Na przykład A → ε.
• Nieterminal generujący dwa nieterminale. Na przykład S → AB.
• Nieterminal generujący terminal. Na przykład S → a.

Na przykład:

 G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c} 

Reguły tworzenia Gramatyki G1 odpowiadają regułom określonym dla CNF, więc gramatyka G1 jest w CNF. Jednakże reguła tworzenia Gramatyki G2 nie spełnia reguł określonych dla CNF, ponieważ S → aZ zawiera terminal, po którym następuje nieterminal. Zatem gramatyki G2 nie ma w CNF.

logika pierwszego rzędu

Kroki konwersji CFG na CNF

Krok 1: Usuń symbol startu z RHS. Jeśli symbol startu T znajduje się po prawej stronie dowolnej produkcji, utwórz nową produkcję jako:

 S1 → S 

Gdzie S1 jest nowym symbolem startu.

Krok 2: W gramatyce usuń produkcje zerowe, jednostkowe i bezużyteczne. Możesz zapoznać się z Uproszczeniem CFG.

Krok 3: Wyeliminuj terminale z RHS produkcji, jeśli istnieją z innymi nie-terminalami lub terminalami. Na przykład produkcję S → aA można rozłożyć jako:

 S → RA R → a 

Krok 4: Wyeliminuj RHS z więcej niż dwoma terminalami nieterminalowymi. Na przykład S → ASB można rozłożyć jako:

 S → RS R → AS 

Przykład:

Konwertuj podany CFG na CNF. Rozważmy podaną gramatykę G1:

przykład nazwy użytkownika

 S → a | aA | B A → aBB | ε B → Aa | b 

Rozwiązanie:

Krok 1: Stworzymy nową produkcję S1 → S, gdy na RHS pojawi się symbol startu S. Gramatyka będzie taka:

 S1 → S S → a | aA | B A → aBB | ε B → Aa | b 

Krok 2: Ponieważ gramatyka G1 zawiera produkcję zerową A → ε, usunięcie jej z gramatyki daje:

mysql pokaż użytkownikom

 S1 → S S → a | aA | B A → aBB B → Aa | b | a 

Teraz, ponieważ gramatyka G1 zawiera produkcję jednostkową S → B, jej wydajność usuwania:

 S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a 

Usuń także produkcję jednostkową S1 → S, jej usunięcie z gramatyki daje:

 S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a 

Krok 3: W regule produkcji S0 → aA | Aa, S → aA | Aa, A → aBB i B → Aa, terminal a istnieje na RHS z nieterminalami. Zastąpimy więc terminal a X:

 S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a 

Krok 4: W regule produkcyjnej A → XBB, RHS ma więcej niż dwa symbole, co usuwa go z gramatyki:

 S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB 

Dlatego dla danej gramatyki jest to wymagany CNF.

dla każdego maszynopisu