CNF מייצג צורה רגילה של חומסקי. CFG (דקדוק חופשי בהקשר) הוא ב-CNF (צורת חומסקי רגילה) אם כל כללי הייצור עומדים באחד מהתנאים הבאים:

• התחל סמל יצירת ε לדוגמה, A → ε.
• לא טרמינל היוצר שני לא טרמינלים. לדוגמה, S → AB.
• לא טרמינל יוצר טרמינל. לדוגמה, S → א.

לדוגמה:

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

כללי הייצור של Grammar G1 עומדים בכללים שצוינו עבור CNF, כך שהדקדוק G1 הוא ב-CNF. עם זאת, כלל הייצור של Grammar G2 אינו עומד בכללים שצוינו עבור CNF שכן S → aZ מכיל טרמינל ואחריו לא טרמינלי. אז הדקדוק G2 אינו ב-CNF.

base64 פענוח ב-js

שלבים להמרת CFG ל-CNF

שלב 1: הסר את סמל ההתחלה מה-RHS. אם סמל ההתחלה T נמצא בצד ימין של הפקה כלשהי, צור הפקה חדשה כ:

 S1 → S 

כאשר S1 הוא סמל ההתחלה החדש.

שלב 2: בדקדוק, הסר את הפקות האפס, היחידה וההפקות חסרות התועלת. אתה יכול לעיין בפישוט של CFG.

שלב 3: הסר טרמינלים מה-RHS של הייצור אם הם קיימים עם טרמינלים אחרים או מסופים אחרים. לדוגמה, ניתן לפרק את הייצור S → aA כך:

 S → RA R → a 

שלב 4: הסר RHS עם יותר משני מסופים שאינם מסופים. לדוגמה, ניתן לפרק את S → ASB כ:

 S → RS R → AS 

דוגמא:

המר את ה-CFG הנתון ל-CNF. שקול את הדקדוק הנתון G1:

קו תחתון בסימון

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

פִּתָרוֹן:

שלב 1: ניצור ייצור חדש S1 → S, כאשר סמל ההתחלה S מופיע ב-RHS. הדקדוק יהיה:

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

שלב 2: מכיוון שדקדוק G1 מכיל ייצור A → ε null, הסרתו מהדקדוק מניבה:

java system.out.println

 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 הנדרש.

שעועית ג'אווה