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

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

$A\to BC$

$A\to xBy$

$A\to \varepsilon$

כאשר $A,B,C$ משתנים ו-$x,y$ טרמינלים. כלומר, כל דקדוק חסר-הקשר ניתן להביע על-ידי דקדוק שכל כלל בו הוא אחד מהצורות לעיל. צורה זו אינה מינימלית. למשל, את הכלל $A\to xBy$ ניתן להחליף בכללים יותר פשוטים, בהן כל משתנה הופך או לשני משתנים או לאות בודדת. צורה זו ידועה בתור הצורה הנורמאלית של חומסקי.

הצורה הנורמלית של חומסקי לדקדוקים חסרי-הקשר

משפט: כל שפה חסרת הקשר שאינה ריקה, ואינה מכילה את המילה הריקה, ניתן ליצירה על-ידי דקדוק ח"ה $G=(V,\Sigma ,R,S)$ שכל כלל בו הוא אחד משתי הצורות הבאות: $A\to BC$ $A\to x$ כאשר $A,B,C\in V$ משתנים ו-$x\in \Sigma$ טרמינל.

הוכחה: נראה אלגוריתם להמרת כל דקדוק ח"ה לצורה הנורמלית של חומסקי. על מנת להגיע לצורה הנדרשת, עלינו להתמודד עם מספר אתגרים:

1. ביטול כללי-אפסילון, דהיינו, כללים מהצורה $A\to \varepsilon$
2. ביטול כללי-יחידה, דהיינו כללים מהצורה $A\to B$ עבור שני משתנים A,B.

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

ביטול מעברי-אפסילון

נשים לב כי אנו מניחים כי השפה אינה מכילה את המילה הריקה, אחרת לא נוכל לייצר מילה זו ללא כללי-אפסילון. על מנת לבטל כללי-אפסילון, נביט בכל המשתנים שיכולים לייצר אפסילון, כלומר, כל המשתנים בהם ניתן לאחר כמה גזירות, להגיע למילה הריקה, $A\Rightarrow ^{*}\varepsilon$. על-מנת לבטל את כלל האפסילון מבלי לשנות את השפה, נביט בכל פעם שמשתנה יוצר את המשתנה A, למשל עבור $B\to CAD$ ייתכנו שני מקרים. בראשון, A הופך אפסילון. מקרה זה קל להחלפה בכלל $B\to CD$. מאידך, A יכול להפוך למילה אחרת שאינה אפסילון, ולכן הכלל $B\to CAD$ חייב להשאר, אבל נדאג שבמקרה זה A לא יכול להפוך להיות אפסילון, על-ידי ביטול הכללים מהצורה $X\to \varepsilon$, לכל משתנה $X\in V$.

ראשית נמצא את כל המשתנים שיוצרים אפסילון. דבר זה קל לביצוע בצור איטרטיבית: ראשית נסמן את כל המשתנים בהם קיים הכלל $A\to \varepsilon$. לאחר מכן, נבדוק את כל המשתנים בהם יש כלל $A\to BC$ כאשר ידוע שגם B וגם C יכולים ליצור אפסילון. נחזור על הבדיקה שוב ושוב עד שלא נמצאים יותר משתנים חדשים שעשויים לייצור אפסילון.

כעת נחליף כל כלל מהצורה $A\to \gamma _{1}B\gamma _{2}$ בו משתנה B יכול ליצור אפסילון, לכלל $A\to \gamma _{1}\gamma _{2}\mid \gamma _{1}B\gamma _{2}$, ונמחק את כל הכללים מהצורה $A\to \varepsilon$.

טענה: בהנתן דקדוק ח"ה G, אשר יוצר את השפה $L(G)$, הבנייה לעיל יוצרת דקדוק $G'$ שאינו מכיל כללי-אפסילון, וכן $L(G')=L(G)\smallsetminus \{\varepsilon \}$

הוכחה: תהי $w\in L(G')$. לא ייתכן כי זו המילה הריקה, כי ב-$G'$ אין כללים המייצרים אפיסלון. נראה באינדוקציה ש$w$ מיוצרת גם על-ידי הדקדוק $G$.

בסיס: $S\Rightarrow w$, נובע כי ב-$G$ קיים הכלל $S\to w$ או כלל מהצורה $S\to wA$ כאשר A יכול ליצור אפסילון (כי ככה בנינו את הכללים של $G'$. מכאן נובע שגם ב$G$, $S\Rightarrow w$.

צעד האינדוקציה: נניח כי $w$ נוצר על-ידי ביצוע $n>1$ גזירות. אזי,

$S\Rightarrow _{G'}X_{1}X_{2}\cdots X_{k}\Rightarrow _{G'}^{*}w$

כמו מקודם, הכלל הראשון חייב לנבוע מתוך כלל של $G$ מהצורה $S\to _{G}Y_{1}Y_{2}\cdots Y_{m}$ כאשר חלק מהמשתנים $Y_{i}$ יכולים ליצור אפסילון, ובהעדר חלק מהם, נשאר בדיוק מחרוזת הXים. מכאן ש-$S\Rightarrow _{G}^{*}X_{1}X_{2}\cdots X_{k}$ והטענה נובעת.

הכיוון השני מוכח על-ידי אינדוקציה דומה.

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

ביטול מעברי-יחידה

הרעיון העומד מאחורי ביטול כללי יחידה (דוגמאת $A\to B$) הוא מציאת כלל האפשרויות הנובעות מכלל היחידה. למשל, עבור הדקדוק $A\to B\ ,\ B\to 0\mid 1$ נוכל לבטל את מעבר היחידה ולהוסיף במקומו את הכללים $A\to 0\mid 1$ ישירות. רעיון זה לא תמיד מצליח - למשל, אם קיים מעגל של משתנים $A\to B\ ,\ B\to C\ ,\ C\to A$, לא נוכל לבצע החלפה פשוטה.

כדי לפתור בעיה זו מוצאים את כל זוגות המשתנים $X,Y$ כך ש$X\Rightarrow ^{*}Y$. פעולה זו ניתנת לביצוע בצורה איטרטיבית (בדומה למציאת כל המשתנים היוצרים אפסילון, כפי שהוסבר מעלה). ביטול כללי היחידה מתבצע על ידי האלגוריתם הבא. בהנתן דקדוק ח"ה $G=(V,\Sigma ,P,S)$ נגדיר דקדוק $G_{1}=(V,\Sigma ,P_{1},S)$:

1. מצא את כל זוגות המשתנים $X,Y$ כך ש$X\Rightarrow ^{*}Y$.
2. לכל זוג משתנים $X,Y$ כנ"ל, עבור כל כלל $B\to \alpha$ שאינו כלל יחידה, הוסף ל-$P_{1}$ את הכלל $A\to \alpha$.

טענה: מתקיים $L(G)=L(G_{1})$. ההוכחה באינדוקציה. פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.

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

הצורה הנורמאלית של גרייבאך

משפט: כל שפה חסרת הקשר שאינה ריקה, ואינה מכילה את המילה הריקה, ניתן ליצירה על-ידי דקדוק ח"ה $G=(V,\Sigma ,R,S)$ שכל כלל בו הוא מהצורה הבאה: $A\to x\gamma$ כאשר $x\in \Sigma$ הוא טרמינל, ו $\gamma \in V^{*}$ מחרוזת של (אפס או יותר) משתנים.

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

הפרק הקודם: למת הניפוח לשפות חסרות הקשר

צורות נורמליות לדקדוקים חסרי הקשר

הפרק הבא: דו-משמעות