דקדוק רגולרי

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

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

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

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

ראו גם
 שפה רגולרית
 ההיררכיה של חומסקי
 תורת האוטומטים - מונחים

לקריאה נוספת


קטגוריה:שפות פורמליות