פרק 2 הגדרות דקדוקיות

אם עד עכשיו התעסקנו בעיקר באוטומטים שבדקו האם המילה הנתונה שייכת לשפה כרגע נעבור לדון בדקדוקים ש תפקידם לייצר מילים.

הגדרה

דקדוק פורמלי מכיל:
א. קבוצה סופית לא ריקה V של משתנים דקדוקיים
ב. קבוצה סופית לא ריקה T של סימנים טרמינליים זרים ל V כלומר
ג. משתנה דקדוקי התחלתי
ד. קבוצה סופית של הפקות

הגדרה

הפקה היא כלל גזירה כאשר ו-

הגדרה

הגדרת שפה הנוצרת על ידי דקדוק
- היא אוסף של כל המילים הטרמינליות הניתנות לגזירה מהמשתנה ההתחלתי של הדקדוק במספר סופי של הפקות מ-
נדגים:
נגדיר את הדקדוק של השפה




נתחיל להפיק מילים:


אם זה עדיין לא ברור צפה בהדגמת פלאש:

.איתן 2002. כל הזכויות שמורות למערכת המידע איתן©