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

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