הצורה הנורמלית של חומסקי
ויקיפדיה האנציקלופדיה encyclopedia
בתורת השפות הפורמליות, אומרים כי דקדוק חסר הקשר ניתן להצגה בצורה הנורמלית של חומסקי (אותה הגה נועם חומסקי)[1][2] אם כל כללי הגזירה שלו הם מהצורה הבאה:
כאשר , ו- הם משתנים שאינם טרמינלים, היא טרמינל[3], היא משתנה הגזירה ההתחלתי ו- היא המחרוזת הריקה. כמו כן ו- לא יכולים להיות המשתנה ההתחלתי, וכלל הגזירה השלישי מופיע בדקדוק אם"ם , כאשר היא השפה הנגזרת מ-.
כל דקדוק המוגדר באמצעות הצורה הנורמלית של חומסקי הוא חסר הקשר, וכל דקדוק חסר הקשר יכול להיכתב באופן שקול כדקדוק בצורה הנורמלית של חומסקי (כלומר, ששפותיהם זהות). כיום קיימים מספר אלגוריתמים שעושים את ההעברות הנ"ל בין דקדוקים. החיסרון של שינויים אלו הוא שהם יכולים לגרום להתנפחות לא רצויה בגודל הדקדוק (המוגדר על ידי סכום הגדלים של כללי הגזירה שלו). אלגוריתמים שונים יכולים לקחת דקדוק בגודל ולהופכו לדקדוק בגדלים הנעים, במקרה הגרוע ביותר, בין לבין .