CFG מייצג דקדוק ללא הקשר. זהו דקדוק פורמלי המשמש ליצירת כל התבניות האפשריות של מחרוזות בשפה פורמלית נתונה. ניתן להגדיר דקדוק G נטול הקשר על ידי ארבעה טפולים כ:

 G = (V, T, P, S) 

איפה,

G הוא הדקדוק, המורכב מקבוצה של כלל הייצור. הוא משמש ליצירת מחרוזת של שפה.

ט הוא הסט הסופי של סמל מסוף. זה מסומן באותיות קטנות.

IN הוא הסט הסופי של סמל לא טרמינלי. זה מסומן באותיות גדולות.

פ הוא קבוצה של כללי ייצור, המשמשת להחלפת סמלים שאינם מסופים (בצד שמאל של הייצור) במחרוזת עם סמלים טרמינליים אחרים או שאינם מסוף (בצד ימין של הייצור).

עדכון מ- join sql

ס הוא סמל ההתחלה המשמש לגזירת המחרוזת. נוכל לגזור את המחרוזת על ידי החלפה חוזרת ונשנית של לא-טרמינל בצד ימין של הייצור עד שכל הלא-טרמינלים הוחלפו בסמלי טרמינל.

דוגמה 1:

בנה את ה-CFG עבור השפה שיש בה כל מספר של א' מעל הסט ∑= {a}.

פִּתָרוֹן:

כידוע הביטוי הרגולרי לשפה הנ'ל הוא

 r.e. = a* 

כלל ההפקה עבור הביטוי הרגולרי הוא כדלקמן:

 S → aS rule 1 S → ε rule 2 

עכשיו אם אנחנו רוצים לגזור מחרוזת 'aaaaaa', נוכל להתחיל עם סמלי התחלה.

 S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa 

שם. = a* יכול ליצור קבוצה של מחרוזת {ε, a, aa, aaa,.....}. יכול להיות לנו מחרוזת ריק כי S הוא סמל התחלה וכלל 2 נותן S → ε.

דוגמה 2:

בנה CFG עבור הביטוי הרגולרי (0+1)*

פִּתָרוֹן:

js מוגדר

ה-CFG יכול להינתן על ידי,

 Production rule (P): S → 0S | 1S S → ε 

הכללים הם בשילוב של 0 ו-1 עם סמל ההתחלה. מאז (0+1)* מציין {ε, 0, 1, 01, 10, 00, 11, ....}. בקבוצה זו, ε הוא מחרוזת, כך שבכלל, נוכל להגדיר את הכלל S → ε.

דוגמה 3:

בנה CFG עבור שפה L = כאשר w € (a, b)*.

פִּתָרוֹן:

המחרוזת שניתן ליצור עבור שפה נתונה היא {aacaa, bcb, abcba, bacab, abbcbba, ....}

הדקדוק יכול להיות:

hashtable לעומת hashmap

 S → aSa rule 1 S → bSb rule 2 S → c rule 3 

עכשיו אם אנחנו רוצים לגזור מחרוזת 'abbcbba', נוכל להתחיל עם סמלי התחלה.

 S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3 

לפיכך ניתן לגזור כל מחרוזת מסוג זה מכללי הייצור הנתונים.

דוגמה 4:

בנה CFG עבור השפה L = a^נב²ⁿכאשר n>=1.

פִּתָרוֹן:

המחרוזת שניתן ליצור עבור שפה נתונה היא {abb, aabbbb, aaabbbbbb....}.

הדקדוק יכול להיות:

 S → aSbb | abb 

עכשיו אם אנחנו רוצים לגזור מחרוזת 'aabbbb', נוכל להתחיל עם סמלי התחלה.

 S → aSbb S → aabbbb