דקדוק רגולרי

בשפות פורמליות דקדוק רגולרי הוא דקדוק המתאר שפה רגולרית.

הגדרה

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

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

את הכלל השני ניתן להחליף ב- $(A\to Ba)$ כדי לקבל דקדוק רגולרי שמאלי

ראו גם

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