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

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

לדוגמה:

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

כללי ההפקה של דקדוק G1 עומדים בכללים שצוינו עבור GNF, כך שהדקדוק G1 הוא ב- GNF. עם זאת, כלל הייצור של Grammar G2 אינו עומד בכללים שצוינו עבור GNF שכן A → ε ו-B → ε מכיל ε (רק סמל התחלה יכול ליצור ε). אז הדקדוק G2 אינו ב-GNF.

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

שלב 1: המר את הדקדוק ל-CNF.

אם הדקדוק הנתון אינו ב-CNF, המר אותו ל-CNF. אתה יכול להפנות את הנושא הבא כדי להמיר את ה-CFG ל-CNF: צורה רגילה של Chomsky

שלב 2: אם הדקדוק קיים רקורסיה שמאלית, הסר אותה.

דוגמה לשם משתמש

אם הדקדוק החופשי של ההקשר מכיל רקורסיה שמאלית, הסר אותה. אתה יכול להפנות את הנושא הבא כדי למנוע רקורסיה שמאלית: רקורסיה שמאלית

שלב 3: בדקדוק, המר את כלל הייצור הנתון לצורת GNF.

אם כלל ייצור כלשהו בדקדוק אינו בצורת GNF, המר אותו.

t ff

דוגמא:

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

פִּתָרוֹן:

מכיוון שהדקדוק G הנתון כבר נמצא ב-CNF ואין רקורסיה שמאלה, אז נוכל לדלג על שלב 1 ושלב 2 וללכת ישירות לשלב 3.

כלל הייצור A → SA אינו ב-GNF, אז אנו מחליפים את S → XB | AA בכלל הייצור A → SA כמו:

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

כלל הייצור S → XB ו-B → XBA אינו ב-GNF, לכן אנו מחליפים את X → a בכלל הייצור S → XB ו-B → XBA כ:

 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 

כעת נסיר ייצור אפס C → ε, נקבל:

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

כלל הייצור S → AA אינו ב-GNF, אז אנו מחליפים את A → aC | aBAC | א | aBA בכלל ייצור S → AA כמו:

 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 | aBAC | א | aBA בכלל ייצור C → 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 

מכאן שזוהי צורת הגנ'פ לדקדוק ג'.

אוטומטים סופיים לא דטרמיניסטיים