דקדוק רגולרי

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

הגדרה

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

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

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

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

ראו גם

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

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000