דקדוק רגולרי

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

הגדרה

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

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

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

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

ראו גם

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

לקריאה נוספת

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