דקדוק רגולרי

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

הגדרה

דקדוק ליניארי ימני (או דקדוק רגולרי ימני) $$ G $$ מוגדר על ידי הרביעייה $G=(N,\Sigma ,P,S)$ בדומה לדקדוק חופשי-הקשר אך עם כללי יצירה מוגבלים יותר:

$(A\to a)$ כך ש- $$ A $$ הוא משתנה ו- $$ a $$ הוא טרמינל.
$(A\to aB)$ כך ש- $$ B $$ הוא משתנה
$(A\to \epsilon )$

באופן דומה ניתן להגדיר דקדוק ליניארי שמאלי, על ידי החלפת כלל הגזירה השני ל $(A\to Ba)$ .

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