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