אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/צורות נורמליות לדקדוקים חסרי הקשר: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 18:
{{הוכחה|
נראה אלגוריתם להמרת כל דקדוק ח"ה לצורה הנורמאלית של חומסקי. על מנת להגיע לצורה הנדרשת, עלינו להתמודד עם מספר אתגרים:
#ביטול כללי-אפסילון, דהיינו, כללים מהצורה <math>A\to\varepsilon</math>
#ביטול כללי-יחידה, דהיינו כללים מהצורה <math>A\to B</math> עבור שני משתנים A,B.
נושא נוסף הינו משתנים חסרי-משמעות, למשל, משתנים שלעולם לא ניתן להגיע אליהם אם מתחילים במשתנה ההתחלתי S ומתקדמים אך ורק לפי כללי הגזירה. אנו נניח שבדקדוק הנתון אין משתנים שלט ניתן להגיע אליהם, כלומר, כלל המשתנים בעלי משמעות.
====ביטול מעברי-אפסילון====
נשים לב כי אנו מניחים כי השפה אינה מכילה את המילה הריקה, אחרת לא נוכל לייצר מילה זו ללא כללי-אפסילון. על מנת לבטל כללי-אפסילון, נביט בכל המשתנים שיכולים לייצר אפסילון, כלומר, כל המשתנים בהם ניתן לאחר כמה גזירות, להגיע למילה הריקה, <math>A\Rightarrow^* \varepsilon</math>. על-מנת לבטל את כלל האפסילון מבלי לשנות את השפה, נביט בכל פעם שמשתנה יוצר את המשתנה A, למשל עבור <math>B\to CAD</math> ייתכנו שני מקרים. בראשון, A הופך אפסילון. מקרה זה קל להחלפה בכלל <math>B\to CD</math>. מאידך, A יכול להפוך למילה אחרת שאינה אפסילון, ולכן הכלל <math>B\to CAD</math> חייב להשאר, אבל נדאג שבמקרה זה A לא יכול להפוך להיות אפסילון, על-ידי ביטול הכללים מהצורה <math>X\to \varepsilon</math>, לכל משתנה <math>X\in V</math>.
ראשית נמצא את כל המשתנים שיוצרים אפסילון. דבר זה קל לביצוע בצור איטרטיבית: ראשית נסמן את כל המשתנים בהם קיים הכלל <math>A\to \varepsilon</math>. לאחר מכן, נבדוק את כל המשתנים בהם יש כלל <math>A\to BC</math> כאשר ידוע ש'''גם B וגם C''' יכולים ליצור אפסילון. נחזור על הבדיקה שוב ושוב עד שלא נמצאים יותר משתנים חדשים שעשויים לייצור אפסילון.
כעת נחליף כל כלל מהצורה <math>A\to \gamma_1B\gamma_2</math> בו משתנה B יכול ליצור אפסילון, לכלל <math>A\to \gamma_1\gamma_2 \mid \gamma_1 B \gamma_2</math>, ונמחק את כל הכללים מהצורה <math>A\to \varepsilon</math>.
{{טענה|תוכן=בהנתן דקדוק ח"ה G, אשר יוצר את השפה <math>L(G)</math>, הבנייה לעיל יוצרת דקדוק <math>G'</math> שאינו מכיל כללי-אפסילון, וכן <math>L(G')=L(G)\smallsetminus\{\varepsilon\}</math>}}
{{הוכחה|תהי <math>w\in L(G')</math>. לא ייתכן כי זו המילה הריקה, כי ב-<math>G'</math> אין כללים המייצרים אפיסלון. נראה באינדוקציה ש<math>w</math> מיוצרת גם על-ידי הדקדוק <math>G</math>.
בסיס: <math>S\Rightarrow w</math>, נובע כי ב-<math>G</math> קיים הכלל <math>S\to w</math> או כלל מהצורה <math>S\to wA</math> כאשר A יכול ליצור אפסילון (כי ככה בנינו את הכללים של <math>G'</math>. מכאן נובע שגם ב<math>G</math>, <math>S\Rightarrow w</math>.
צעד האינדוקציה: נניח כי <math>w</math> נוצר על-ידי ביצוע <math>n>1</math> גזירות. אזי,
<center><math>S\Rightarrow_{G'}X_1X_2\cdots X_k\Rightarrow^*_{G'}w</math></center>
כמו מקודם, הכלל הראשון חייב לנבוע מתוך כלל של <math>G</math> מהצורה <math>S\to_G Y_1Y_2\cdots Y_m</math> כאשר חלק מהמשתנים <math>Y_i</math> יכולים ליצור אפסילון, ובהעדר חלק מהם, נשאר בדיוק מחרוזת הXים. מכאן ש-<math>S\RightArrow^*_{G} X_1X_2\codts X_k</math> והטענה נובעת.
הכיוון השני מוכח על-ידי אינדוקציה דומה. {{להשלים}}
}}
לסיום, נראה כיצד ניתן לבטל כללי-יחידה.
{{להשלים|ביטול כללי יחידה}}
}}
| |||