פרק 3 שפות חסרות הקשר
הגדרה
הדקדוק קרוי חסר הקשר אם כל ההפקות ב-
הן מהצורה:
כאשר
כל דקדוק רגולרי הוא חסר הקשר כי בכל מקרה משתנה הולך למשהו.(טרמינל או משתנה וטרמינל)
מקור השם חסר הקשר הוא שבכל פעם שמופיע משתנה X אפשר ,לא משנה ההקשר (פירושו לא משנה איזו טרמינלים נמצאים מימינו ומשמאלו) להמירו ל-h.
עניין ההקשר יתברר הרבה יותר אחרי שנסביר דקדוק תלוי הקשר והירארכיה של חומסקי.
הגדרה
השפה L קרויה חסרת הקשר אם קיים דקדוק חסר הקשר
כך ש- 
כעת נראה שעל ידי דקדוק זה נוכל לקבל שפות שלא יכולנו לקבל על ידי דקדוק רגולרי.
לדוגמא:
היא שפה חסרת הקשר
דקדוק חסר הקשר מתיר הפקה 
רק עבור 
נגדיר שני מקרים פרטיים של דקדוק חסר הקשר שיעזרו לנו בהמשך.
הגדרה
דקדוק
קרוי דקדוק מסתעף אם אין ב- הפקות
מהצורה 
נוכיח שקילות לדקדוק חסר הקשר:
משפט 3.1
לכל דקדוק חסר הקשר קיים דקדוק חסר הקשר מסתעף 
,כך ש- 
הוכחה
קיימים שני מקרים:
מקרה 1:
קיים ב- מעגל 
נרצה לבטל את כל המעגל אך עדיין להישאר באותה שפה. נוכל לבטל את המעגל ונחליף כל
הופעה של 
ב- 
. כיוון שממילא כל ה-
הלכו בינם לבין עצמם לכן בזה שצמצמנו את כולם לא שנינו כלום.
מקרה 2:
קיימת ב- סידרה
: 
אנו נרצה לבטל
את כל המעברים הללו .נבטל את 
ונחליף כל הפקה 
ב- 
.את כל זה נעשה
בלולאה כל פעם על האיבר האחרון עד שנבטל את כל הסדרה.