אוטומטים ושפות פורמליות/דקדוקים חסרי הקשר

כעת נרצה לנתח את התכונות של השפות המוכרעות על-ידי אוטומט מחסנית.

על מנת לנתח שפות אלו, נצטרך להגדיר אובייקט חדש הנקרא דקדוק. בהמשך נראה כי הדקדוק אותו נגדיר מתאר בדיוק את כלל השפות המוכרעות על-ידי אוטומט מחסנית.

הגדרה

דקדוק חסר הקשר $G$ מוגדר על ידי הרביעיה $G=(V,\Sigma ,R,S)$, כאשר:

1. $V$ - קבוצת משתנים
2. $\Sigma$ - קבוצת אותיות סופיות (טרמינלים). קבוצה זו מהווה את האלפבית של השפה הנוצרת.
3. $R$ - קבוצת כללי יצירה. כל כלל הופך משתנה למחרוזת של אותיות ומשתנים$(A\to \alpha )\in R\qquad A\in V,\alpha \in (V\cup \Sigma )^{*}$
4. $S$ - סימן ההתחלה. משתנה מתוך $V$.

אומרים שהדקדוק $G$ יוצר מילה $x$, אם ניתן להתחיל מהמשתנה $S$, ועל-ידי ביצוע אחד או יותר מכללי היצירה שב-$R$, להגיע אל המילה $x\in \Sigma ^{*}$. מסמנים במקרה זה $S\Rightarrow ^{*}x$.

השפה הנוצרת על-ידי הדקדוק $G$, היא אוסף כל המחרוזות $x$, אותן ניתן לייצר מ-$S$, על ידי כללי היצירה המוגדרים ב-R. באופן פורמלי,

$L(G)=\{x\mid S\Rightarrow ^{*}x\}$

דוגמא

הדקדוק חסר ההקשר הבא מייצר את השפה $L=\{0^{n}1^{n}\mid n\geq 0\}$:

$S\to 0S1$
$S\to \varepsilon$

בדוגמא זו, $G=(V=\{S\},\Sigma =\{0,1\},R,S)$ כאשר כללי היצירה נתונים לעיל.

למשל, ניצור את המילה 000111:

$S\Rightarrow 0S1\Rightarrow 00S11\Rightarrow 000S111\Rightarrow 000\varepsilon 111$

או בצורה מקוצרת $S\Rightarrow ^{*}000111$. בשלוש הגזירות הראשונות השתמשנו בכלל היצירה $S\Rightarrow 0S1$ וברביעית בכלל $S\Rightarrow \varepsilon$.

תרגיל : מה השפה המוגדרת על-ידי הדקדוק $S\to aSa\mid bSb\mid \varepsilon$?
$L=\{ww^{R}|w\in \{a,b\}^{*}\}$, כלומר כל הפולינדרומים בעלי אורך זוגי.

עץ יצירה

ניתן להציג את יצירת המילה בתור עץ-יצירה. למשל, נתון הדקדוק המתואר על ידי שני כללי היצירה: $S\to a\mid SS$. דקדוק זה מאפשר ניתן לייצר את המילה aaa באופן הבא,

$S\Rightarrow SS\Rightarrow aS\Rightarrow aSS\Rightarrow aaS\Rightarrow aaa$

ניתן לתאר את שרשרת הגזירות על-ידי עץ-יצירה:

בצורה זו המילה המתקבלת הינה עלי העץ, הנקראים משמאל לימין (סדר העלים בסריקת עומק-תחילה, DFS).

הקשר בין שפות חסרות הקשר לאוטומט מחסנית

בחלק זה נראה כי אוטומט מחסנית שקול לדקדוק חסר הקשר.

יצירת אוטומט מדקדוק חסר הקשר

כיוון זה קל - ומזכיר מאד, מבחינת הרעיונות, ביצוע סריקת DFS בעץ - על ידי מחסנית.

נניח כי נתון דקדוק $G=(V,\Sigma ,R,S)$. נבנה ממנו אוטומט המבצע את האלגוריתם להלן:

מתיאור זה ניתן להבין מדוע דקדוק חסר הקשר הוא הכלי המתאים לתיאור שפות המתקבלות על-ידי אוטומט. מכיוון שהזיכרון של האוטומט הוא מחסנית, האוטומט מוגבל לפעולות מחסנית, ולאלגוריתמים שניתנים למימוש קל על-ידי מחסנית (למשל DFS). דקדוק חסר הקשר ממפה כל מילה בשפה ל"עץ יצירה" המתאים למילה, כאשר המילה היא למעשה עלי העץ לפי הסדר המתקבל בסריקת DFS.

1. האוטומט מתחיל על-ידי הכנסה של הסימן ההתחלתי S למחסנית.
2. בכל צעד מוציאים את הסימן שבראש המחסנית:
   1. אם הסימן שנשלף הינו משתנה, בוחרים באופן לא-דטרמיניסטי את אחד מחוקי היצירה המתאימים לאותו המשתנה, ומכניסים את הסימנים המתאימים למחסנית (כלומר, אם שלפנו את המשתנה A, ובחרנו בכלל היצירה $A\to aSbb$, נכניס למחסנית $b,b,S,a$ (בסדר הפוך, כדי שה-a יהיה בראש המחסנית)).
   2. אם הסימן הינו טרמינל - משווים את האות לאות הקלט הנוכחית (כלומר, קיים מעבר לכל אות קלט עם האות המקבילה בראש המחסנית).

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

יצירת דקדוק מאוטומט סופי

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

נניח כי נתון לנו אוטומט מחסנית $M=(Q,\Sigma ,\Gamma ,Q,q_{0},F,\delta )$, ונניח כי תמיד בעת קבלת המילה, המחסנית של האוטומט ריקה (קל להפוך כל אוטומט-מחסנית לאוטמט המרוקן את המחסנית לפני הקבלה.) כמו כן נניח כי קיים רק מצב מקבל יחיד $F=\{q_{F}\}$ (גם דרישה זו קלה להשגה, למשל על-ידי מעבר אפסילון מכל המצבים המקבלים למצב מקבל יחיד, והפיכת המצבים המקבלים המקוריים למצבים רגילים).
מהאוטומט הנתון נבנה דקדוק $G=(V,\Sigma ,R,S)$. נתאר כעת את המרכיבים השונים של הדקדוק:

• טרמינלים - מהווים את האלפבית של השפה.
• משתנים - כל המשתנים יהיהו מהצורה $V_{q_{1},q_{2}}$כאשר $q_{1},q_{2}\in Q$ הינם מצבים כלשהם של האוטמט. נרצה שהמשתנה $V_{q_{1},q_{2}}$ ייצר את כל המחרוזות שמקבל אוטומט המתחיל במצב $q_{1}$ (עם מחסנית ריקה) ומסיים במצב $q_{2}$ (שוב, עם מחסנית ריקה, לפי ההנחות שאנחנו עובדים). במילים אחרות, $V_{q_{1},q_{2}}$ מתאר את פעולת האוטומט ממצב $q_{1}$ ועד למצב $q_{2}$ בהנחה שהאוטומט לא קורא את תוכן המחסנית מעבר לנקודה שהיא נמצאת כרגע, אבל אולי משתמש בה (ואז מרוקן אותה חזרה למצב ההתחלתי).
• מצב התחלתי - מתיאור המשתנים לעיל, ברור כי השפה של האוטמט מיוצרת על-ידי $V_{q_{0},q_{F}}$, המתאר את כל המחרוזות שהאוטומט מקבל אם התחיל במצב $q_{0}$ עם מחסנית ריקה, וסיים במצב המקבל (היחידי) עם מחסנית ריקה. לכן משתנה זה יהיה המשתנה ההתחלתי שלנו: $S=V_{q_{0},q_{F}}$
• כללי יצירה - כעת נגדיר את כללי היצירה של הדקדוק לפי התנהגות המכונה. נפריד לשלושה מקרים שונים:
  1. האוטומט התחיל במצב $q_{1}$ וסיים במצב $q_{2}$, אבל במהלך הדרך, הגיע למצב $p$ כאשר המחסנית היתה ריקה. עבור מקרים מסוג זה נוסיף את כלל היצירה $V_{q_{1},q_{2}}\to V_{q_{1},p}V_{p,q_{2}}$, שמשמעותו שכל המחרוזות שהאוטומט "מקבל" אם התחיל במצב $q_{1}$ וסיים במצב $q_{2}$, בלי לקרוא את התוכן הקיים על המחסנית עצמה, הוא למעשה כל המחרוזות שהאוטמט "מקבל" בין $q_{1}$ ל-$p$, משורשרות לכל המחרוזות שהאוטמט "מקבל" כשמתחיל ב-$p$ ומסיים ב-$q_{2}$. לכן, לכל שלשת מצבים $\forall q_{1},q_{2},p\in Q$ נוסיף את כלל היצירה $V_{q_{1},q_{2}}\to V_{q_{1},p}V_{p,q_{2}}$
  2. המקרה השני הוא שהאוטמט, במהלך הדרך בין $q_{1}$ ל-$q_{2}$ לעולם לא מגיע למצב בו המחסנית ריקה (בהנחה שהתחיל עם מחסנית ריקה). במקרה זה, בצעד הראשון האוטמט קורא מהקלט את הסימן x, מכניס למחסנית אות כלשהי a, ועובר למצב $p_{1}$. בצעד האחרון נניח שהאוטומט במצב $p_{2}$ כאשר הוא קורא מהקלט את האות y, עובר למצב $q_{2}$ ובהכרח מוציא מהמחסנית את האות a - לא ייתכן שנשלפה אות אחרת כי אף פעם במהלך הדרך המחסנית לא רוקנה, ולכן הסימן שהוכנס בצעד הראשון עדיין שם. כלל היצירה המתאים למקרה זה הוא מהצורה $V_{q_{1},q_{2}}=xV_{p_{1},p_{2}}y$. חשוב לציין שכלל יצירה כנ"ל קיים רק אם המכונה יכולה לעבור מ-$q_{1}$ ל-$p_{1}$, ומ-$p_{2}$ ל-$q_{2}$ על ידי קריאת x,y מהקלט (בהתאמה), ועל-ידי הכנסה למחסנית ושליפה של אותה האות a. במילים אחרות, נוסיף את כללי היצירה הבאים $V_{q_{1},q_{2}}\to xV_{p_{1},p_{2}}y$ אם מתקיימים התנאים $\forall q_{1},q_{2},p_{1},p_{2}{\text{ s.t. }}\exists x,y\in \Sigma \cup \{\varepsilon \},a\in \Gamma {\text{ and }}\delta (q_{1},x,\varepsilon )\to (p_{1},a),\delta (p_{2},y,a)\to (q_{2},\varepsilon )$
  3. התנאי השלישי הוא מקרה הקצה $V_{q,q}$ בו שני המצבים זהים. משתנה זה למעשה מייצר את המחרוזות המתקבלות על-ידי האוטומט אם התחיל וסיים באותו מצב, מבלי לקרוא את התוכן הקיים על המחסנית. נוסף על המקרים המתוארים במקרה (2) לעיל, צריך לזכור שייתכן כי המצב של האוטומט לא השתנה בכלל, המתאים למקרה בו לא נקראה אף אות קלט. בשל כך נוסיף את כלל היצירה $V_{q,q}\to \varepsilon$ עבור כל מצב $q\in Q$. קל לראות שאלמלא כלל-יצירה זה, כמות המשתנים רק גדלה ולעולם לא נסיים עם מחרוזת שכולה טרמינלים.

הכללים לעיל מכסים את כלל האפשרויות של פעולת האוטומט, למעט המקרה בו האוטומט לא כותב דבר למחסנית (מעבר מהצורה $a,\varepsilon \to \varepsilon$) או קורא וכותב בו-זמנית $x,a\to b$. אבל ניתן להמיר כל אוטומט מחסנית כך שמעברים מהסוג הנ"ל לא יופיעו בו (למשל, על-ידי הוספת מצבי ביניים שכותבים למחסנית ואז מוציאים, וכד').

הפרק הקודם: אוטומט מחסנית

דקדוקים חסרי הקשר

הפרק הבא: תכונות של שפות חסרות הקשר