דקדוק רגולרי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

הגדרה[עריכת קוד מקור | עריכה]

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

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

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

ראו גם[עריכת קוד מקור | עריכה]