דקדוק רגולרי

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

הגדרה[עריכת קוד מקור | עריכה]

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]