לדלג לתוכן

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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

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

סגירות לאיחוד

[עריכה]

יהיו שפות ח"ה, ויהיו הדקדוקים ח"ה המתאימים.

השפה הינה חסרת הקשר, מכיוון שניתן ליצור את הדקדוק כך ש

כלומר המשתנה הראשון יכול להוביל אל , אשר יוצר את כל המילים של , או אל , אשר יוצר את כל המילים של .

סגירות לשרשור

[עריכה]

יהיו שפות ח"ה, ויהיו הדקדוקים ח"ה המתאימים.

השפה הינה חסרת הקשר, מכיוון שניתן ליצור את הדקדוק כך ש

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

סגירות להפיכה לאחור

[עריכה]

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

קל לראות שהדקדוק יוצר בדיוק את כל המילים ההפוכות מאלו מיוצרות על-ידי .

חיתוך עם שפה רגולרית

[עריכה]

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

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

באופן פורמלי, בהנתן אוטומט סופי עבור (רגולרית) ואוטומט מחסנית עבור (ח"ה), נוכל לבנות אוטומט מחסנית חדש

כך שמתקיים:

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

פעולות שאינן סגורות עבור שפות חסרות הקשר

[עריכה]

חיתוך

[עריכה]

קל לראות שהשפות הינן חסרות הקשר, אבל השפה אינה חסרת הקשר (זאת מוכיחים בעזרת למת הניפוח לשפות חסרות הקשר)

משלים

[עריכה]

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

הפרש

[עריכה]

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



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