דקדוק רגולרי

בשפות פורמליות דקדוק רגולרי הוא דקדוק המתאר שפה רגולרית. ישנם שני סוגים של דקדוקים רגולריים: דקדוק ליניארי ימני ודקדוק ליניארי שמאלי.

הגדרהעריכה

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

  •   כך ש-  הוא משתנה ו-  הוא טרמינל.
  •   כך ש-  הוא משתנה
  •  

באופן דומה ניתן להגדיר דקדוק ליניארי שמאלי, על ידי החלפת כלל הגזירה השני ל  .

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

ראו גםעריכה

לקריאה נוספתעריכה