דקדוק רגולרי

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

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

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

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

לקריאה נוספת
 

שפות פורמליות