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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
מ אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/צורות נורמליות הועבר ל[[אוטומטים ושפות פורמליות/תכונות של שפות חסרות הקשר/צורות נורמ...
Gran (שיחה | תרומות)
שורה 41:
}}
 
{{להשלים|====ביטול כללי מעברי-יחידה}}====
לסיום, נראה כיצד ניתן לבטל כללי-יחידה.
הרעיון העומד מאחורי ביטול כללי יחידה (דוגמאת <math>A\to B</math>) הוא מציאת כלל האפשרויות הנובעות מכלל היחידה. למשל, עבור הדקדוק <math>A\to B \ ,\ B\to 0 \mid 1</math> נוכל לבטל את מעבר היחידה ולהוסיף במקומו את הכללים <math>A\to 0 \mid 1</math> ישירות. רעיון זה לא תמיד מצליח - למשל, אם קיים מעגל של משתנים <math>A\to B \ , \ B\to C\ , \ C\to A</math>, לא נוכל לבצע החלפה פשוטה.
{{להשלים|ביטול כללי יחידה}}
 
כדי לפתור בעיה זו מוצאים את כל זוגות המשתנים <math>X, Y</math> כך ש<math>X\Rightarrow^* Y</math>. פעולה זו ניתנת לביצוע בצורה איטרטיבית (בדומה למציאת כל המשתנים היוצרים אפסילון, כפי שהוסבר מעלה). ביטול כללי היחידה מתבצע על ידי האלגוריתם הבא. בהנתן דקדוק ח"ה <math>G=(V,\Sigma, P, S)</math> נגדיר דקדוק <math>G_1 = (V, \Sigma, P_1, S)</math>:
#מצא את כל זוגות המשתנים <math>X, Y</math> כך ש<math>X\Rightarrow^* Y</math>.
#לכל זוג משתנים <math>X,Y</math> כנ"ל, עבור כל כלל <math>B\to \alpha</math> שאינו כלל יחידה, הוסף ל-<math>P_1</math> את הכלל <math>A\to \alpha</math>.
{{טענה|תוכן=מתקיים <math>L(G)=L(G_1)</math>. ההוכחה באינדוקציה. {{להשלים}} }}
 
על-ידי ביטול מעברי-אפסילון ומעברי-יחידה מתקבל דקדוק בצורה הנורמאלית של חומסקי.
}}