PDA

צפה בגרסה המלאה : עזרה דחופה- תרגיל במודלים



MaayanK5
17-01-2013, 15:25
השאלה הזו הייתה בבגרות 2000 ואני לא מוצאת תשובות...
אשמח אם תעזרו לי, זה ממש דחוף ...

M אוטומט סופי דטרמינסטי לא מלא.
נסמן ב-L את השפה המתקבלת על ידי M
נבנה אוטומט 'M מתוך M באופן הבא:
האוטומט 'M יהיה זהה לאוטומט M, אבל כל מצב שהוא מקבל של M יהפוך למצב לא מקבל ב 'M, וכל מצב שאינו מקבל בM יהפוך למצב מקבל ב 'M.
נסמן ב 'L את השפה המתקבלת על ידי 'M
א. האם L1 ⊆ L2 ?
ב. האם 'L שווה לL משלים?

תודה על העזרה, ואם אפשר גם להסביר את התשובות ... :P

avishay12456
17-01-2013, 18:26
א. אני מניח שזה אמור להיות L ו-'L, רק לא בטוח איזה אחד זה מי. בכל מקרה התשובה תהיה לא משום שהשפות זרות, כל המילים שמתקבלות ב-L לא מתקבלות ב-'L ולהפך לפי הגדרה.
ב. כן, זאת בדיוק הגדרת המשלים (כל המילים מעל הא"ב שלא שייכות לשפה מרכיבות את שפת המשלים).