מודלים חישוביים (20604)

https://github.com/adielBm/20604

מבחן לדוגמה 1

שאלה 1

• א. הוכיחו שהשפה הבאה לא רגולרית:
  • תשובה:
    • נניח בשלילה ש- רגולרית.
    • קיים שמקיים את תנאי למת הניפוח.
    • ניקח את המילה . שנמצאת כמובן בשפה , כאשר ו-. כאשר מורכבת מ- ים בלבד ואינה ריקה.
    • לפי הלמה, אם ננפח למטה, כלומר נקבל את המילה , שבה השמטנו לפחות אחת, (ולא -ים או -ים) אינה נמצאת ב- , בסתירה ללמת הניפוח.
    • מסקנה: אינה רגולרית.
• ב.בנו NFA עבור הב”ר הבא: . יש להסתפק באוטומט בן 3 מצבים. הסבירו בקצרה את רעיון הבניה.
  • תשובה:
    • 
    • מצב : מצב התחלתי “מזהה אפס או יותר אחדים בהתחלת הקלט” אוטומט NFA “מנחש” מתי מגיע תור של אפסים ואז עובר למצב .
    • במצב האוטומט “דואג” לזהות 0 אפס או יותר פעמים ואז כאשר מגיע 1 ראשון עובר למצב
    • מצב : מצב מקבל אוטומט מוכן לקבל 1ים בסוף הקלט ורק אותם.
• ג. בנו ב”ר מעל א”ב עבור השפה הבאה: .
  • תשובה:

שאלה 2

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

שאלה 3

• א. האם השפה הבאה ניתנת להכרעה על ידי מ”ט. הוכיחו.
  • תשובה: השפה ניתנת להכרעה על ידי מ”ט:
    • :
      • Compute .
      • For each input of length at most :
        • Simulate on for at most steps.
        • If halts, then accept.
      • Reject.
        
    • אם , אזי קיימת מילה כך ש- עוצר עליה תוך פחות מ- צעדים, מילה זו אינה יכולה להיות ארוכה מ- , ולכן המכונה כן עוברת עליה, ומקבלת אותה.
    • אם , אזי לא עוצר על אף מילה באורך קטן מ- , ולכן המכונה לא מקבלת אף מילה, ולכן לא מקבלת את השפה .
• ב. האם השפה הבאה ניתנת לזיהוי? הוכיחו. .
  • תשובה: השפה מזוהה-טיורינג.
    • נסמן את סדרת המילים ב .
    • “עבור קלט כאשר היא מ”ט:
      • לכל :
        • נריץ את על כל אחד מ- , לכל היותר צעדים.
        • אם מקבלת מילה כלשהי (שאינה סומנה עדיין על הסרט), נוסיף 1 לקאונטר , ונרשום אותה על הסרט.
        • אם , נקבל.”
    • אם אכן , אז בעצם קיימים לפחות 3 מילים ב- שעבורם תקבל במספר סופי של צעדים. המ”ט שבנינו אינה יכולה להיכנס ללופ שהרי הגבלנו את הריצות של במספר הצעדים.
• ג. האם השפה הבאה ניתנת לזיהוי? .
  • תשובה: כן. השפה ניתנת לזיהוי (ואף כריעה). אם אכן הוא תיאור של מ”ט, אזי השפה היא בת-מניה, שהרי לא קיימת שפה שאינה בת-מנייה מעל אלפבית סופי. אם כן השפה הנתונה היא שפת כל התיאורים של מ”ט. והיא כריעה.

שאלה 4

• א. הוכיחו שהבעיה הבאה היא NP שלמה
  • רמז: רדוקציה לבעיית SAT.
  • תשובה:
    • נראה רדוקציה פולי’ מ- ל- , כלומר: .
      • נגדיר פונקציה כך: , כאשר הוא משתנה חדש שאינו מופיע ב- .
      • כיוון ראשון: אם , אז צד שמאל של , כלומר , מסופק, לכן גם וגם מספקים את , כלומר .
      • כיוון שני: אם , אזי אינה ספיקה, ולכן גם אינה ספיקה, כלומר .
      • מסקנה: .
      • לכן, .
    • מכך, ובגלל שגם היא NP-שלמה (משפט 7.37), נובע לפי משפט 7.36 ש- היא NP-שלמה.
• ב. משולש בגרף לא מכוון מוגדר כתת-גרף בן 3 צמתים כך שיש קשת בין כל זוג של צמתי המשולש (קליקה בגודל 3). הוכיחו ששפה הבאה שייכת למחלקה P:
  • ֹֹתשובה: נראה אלגוריתם פולינומיאלי עבור הבעיה:
    • 1. עבור כל שלשה של צמתים :
      • 2. אם , נקבל.
    • 3. אם סיימנו בלי למצוא משולש, נדחה.
    • לגרף עם צמתים יש לכל היותר שלשות צמתים. לכן שלב 2 יבוצע לכל היותר פעמים. לכן כל השלבים הם רצים בזמן פולינומיאלי. לכן .

מבחן לדוגמה 2

שאלה 1

• א. תנו דוגמא לשתי שפות רגולריות ו- המקיימות: אף שפה לא מוכלת בשנייה ובנוסף, .
  • תשובה:
    • ,
    • ,
• ב. האם ייתכן: שפה רגולרית, שפה לא רגולרית אבל: לא רגולרית ובו זמנית רגולרית?
  • תשובה: כן. נראה דוגמה:
    • השפה רגולרית.
    • השפה אינה רגולרית (דוגמה 1.73).
    • האיחוד הוא , רגולרית.
    • החיתוך הוא , שהיא אינה רגולרית.
• ג. תהי סדרה אינסופית של שפות רגולריות. האם האיחוד האינסופי של כל השפות בהכרח יהיה שפה רגולרית?
  • תשובה: לא בהכרח. דוגמה נגדית:
    • ניקח את השפות , שהן כל אחת רגולרית. אמנם איחודן הוא , שהיא אינה רגולרית (דוגמה 1.73).
• ד. בנו ב”ר עבור שפה של NFA הבא:
  • תשובה:

שאלה 2

• א. תהי שפה חסרת הקשר המיוצרת בעזרת דקדוק חסר-הקשר . בנו דקדוק חסר הקשר המייצר את השפה . נמקו.
  • תשובה:
    • ,
      • where .
    • הסבר: השפה היא השפה המתקבלת על ידי חיבור אפס או יותר מחרוזות של השפה . לכן, ניתן להוסיף כלל חדש שמאפשר לייצר מחרוזות של ברצף, ואפשר גם לסיים את הגזירה עם , כלומר לא לייצר מחרוזת כלל.
• ב. אנו מבצעים תהליך מעבר CFG לדקדוק בצורת חומסקי.
  • לאחר מספר צעדים התקבל הדקדוק הבא:
  • בצעד הבא רוצים לסלק מעבר אפסילון . רשמו דקדוק שיתקבל לאחר צעד זה.
  • תשובה:
• ג. בנו PDA עבור השפה הבאה: . הסבירו את הפתרון.
  • תשובה:
    • 
    • בהתחלה, דוחפים למחסנית כדי לסמן את תחילת המחסנית.
    • לכל שקוראים בסרט, דוחפים למחסנית .
    • אחר כך עוברים ל-ים, כל שקוראים בסרט, מוצאים מהמחסנית.
    • בסוף הסרט:
      • אם קוראים מהמחסנית, אז מקבלים. כי זה אומר ש .
      • אם קוראים מהמחסנית, אז מקבלים. כי זה אומר ש .
• ד. נתון CFG הבא: . האם את הסדרות הבאות אפשר לגזור בדקדוק זה? אם כן בנו עצי גזירה עבורן.
  • תשובה: אפשר לגזור את שתיהן.

שאלה 3

• א. האם השפה הבאה ניתנת להכרעה? הוכיחו.
  • תשובה:
    • : (where is the input alphabet of )
      • For each input : (כל הרישות באורך 5 לכל היותר )
        • Simulate on for at most steps. If does not halt in step 4, then accept.
      • Reject.
        
    • האלגוריתם בסוף יסתיים כי יש מספר סופי של קלטים באורך 5 לכל היותר מעל אלפבית סופי וגם כי יש מספר סופי של צעדים שעל כל קלט מריצים את M. אם עברנו על כל הקלטים האפשריים ולא קיבלנו, אז דוחים.
• ב. תהי שפה הניתנת לזיהוי על ידי מ”ט ותהי שפה שלא ניתנת לזיהוי על ידי מ”ט. נסתכל בשפה הבאה: . האם – ניתנת להכרעה? ניתנת לזיהוי? הוכיחו.
  • תשובה:
    • נניח בשלילה ש- ניתנת לזיהוי.
      • אזי קיימת מ”ט שמזהה את .
      • נבנה מ”ט : “עבור כל קלט :
        • נריץ את על , אם מקבל, נקבל. אם דוחה, נדחה.”
      • אם , אז , ולכן ולכן מקבל את , ולכן מקבל את .
      • אם כן מצאנו מ”ט המזהה את . בסתירה לנתון בשאלה.
      • מסקנה: אינה ניתנת לזיהוי.
      • לכן, גם אינה ניתנת להכרעה.

שאלה 4

• א. נסתכל ב-2 שפות הבאות:
  • WVC: given a graph , a weight function , constant . then belongs to WVC if has a vertex cover of total weight of most .
  • VC: given a graph and integer . Then belongs to VC if has a vertex cover of size at most .
  • נניח שידוע ש- שפה NP שלמה. הוכיחו ש- שפה NP שלמה.
  • תשובה:
    • נראה רדוקציה פולי’ מ- ל- . כלומר נראה ש: .
    • נגדיר פונקציה כך: , כאשר לכל .
    • בבירור . והפונקציה ניתנתה לחישוב בזמן פולינומיאלי.
• ב. הוכיחו שהשפה היא שפה NP שלמה.
  • גרף לא מכוון שייך לשפה אם קיימת ב- קליקה שמכילה חצי מהצמתים שלו.
  • רמז: רדוקציה מהבעייה . שייך לשפה אם בגרף לא מכוון יש קליקה בגודל .
  • תשובה:
    • ראשית, , כי בהינתן קבוצת צמתים בגודל , ניתן לבדוק בזמן פולינומיאלי אם יש קשת בין כל זוג צמתים בקבוצה זו.
    • נראה רדוקציה פולי’ מ- ל- . כלומר נראה ש: .
    • נגדיר פונקציה כך: , כאשר:
      • אם : נגדיר את להיות גרף עם ו- .
      • אם : נגדיר את להיות גרף עם ו- יכיל את הצמתים של וגם נוסיף לו צמתים חדשים (שלא מחוברים לשום צומת אחר), כאשר . (ואז מתקיים ).
        • מתקיים ש: ל- יש קליקה בגודל אם ורק אם ל- יש קליקה בגודל
      • אם : נגדיר את להיות גרף כאשר יכלול את כל הצמתים של וגם נוסיף לו צמתים חדשים, כאשר . (ואז ). ו- יכיל את כל הקשתות של וגם נוסיף קשתות בין כל הצמתים החדשים, וגם מכל צומת חדש לכל צומת ב- .
        • מתקיים ש: ל- יש קליקה בגודל אם ורק אם ל- יש קליקה בגודל .
      • אם ,
      • אם כן: .
      • מאחר ש: CLIQUE היא NP-שלמה (מסקנה 7.43), נובע ש- גם היא NP-שלמה (לפי משפט 7.36).

מבחן לדוגמה 3

שאלה 1

• א. בנו DFA עבור כל אחד מהברי”ם הבאים. תנו הסבר קצר.
  • • תשובה:
      • 
  • תשובה:
    • 
• ב. הפכו את ה NFA הבא ל- DFA שקול.
  • 
  • תשובה:
    • 
• ג. בנו DFA מעל עבור השפה הבאה:
  • .
    • תשובה:

שאלה 2

• א. ו- ב. ראו מועד 2024b-94 שאלה 2
• ג. האם השפה הבאה חסרת הקשר? .
  • תשובה:
    • נניח בשלילה ש- חסרת הקשר.
      • אזי קיים אורך ניפוח .
      • ניקח את המילה .
      • לפי הלמה ניתן לכתוב , כאשר ו- .
        • מקרה 1: אם מכילה לפחות אחד, אז בוודאי אינה מכילה -ים, אם כן מכילה לפחות -ים, אבל יהיה בה בדיוק -ים. כלומר לא יתכן ש-. ואז . סתירה.
        • מקרה 2: אם אינה מכילה -ים, אז היא מכילה לפחות אחד או לפחות אחד. אם כן כאשר ננפח למטה, נקבל שמספר ה--ים או ה--ים ירד, אבל מספר ה--ים נשאר אותו דבר. ואז גם לא יתכן ש-. ואז . סתירה.
    • מסקנה: אינה חסרת הקשר.

שאלה 3

ראו מועד 2024b-94 שאלה 3.

שאלה 4

• א. הוכיחו ששפה הבאה לא כריעה:
  • הדרכה: רדוקציה מבעיה .
  • תשובה:
    • נניח בשלילה ש- ניתנת להכרעה ע”י מ”ט .
      • נשים לב שעבור מ”ט עם מצב מקבל , מתקיים ש- הוא useless state אםם .
      • נבנה מ”ט כך: “עבור כל קלט , כאשר היא מ”ט:
        • נריץ את על .
        • אם מקבל, אז נדחה. אחרת, נקבל.”
      • מ”ט זו מכריעה את , כי אם אז הוא useless state, ואם אז אינו useless state.
      • אבל אינה ניתנת להכרעה לפי משפט 5.2. סתירה.
    • מסקנה: אינה ניתנת להכרעה.
• ב. הוכיחו שלא קיימת רדוקציית מיפוי מ- ל- . (תרגיל 5.5 בספר)
  • רמז: הוכחה בדרך השלילה ותכונות ידועות של ו- .
  • תשובה:
    • נניח בשלילה ש- בעזרת רדוקציית מיפוי .
    • אזי .
    • באופן שקול: .
    • כלומר .
    • כלומר .
    • כמו כן ידוע ש- אינה מזוהה -טיורינג (מסקנה 4.23), ו- היא כן מזוהה -טיורינג (תרגיל 4.5 בספר). אבל אם קימת רדוקציית מיפוי מ- ל- נובע ש- מזוהה -טיורינג, (או ש- אינה מזוהה -טיורינג). סתירה.
    • מסקנה: לא קיימת רדוקציית מיפוי מ- ל- .
• ג. ידוע ש- ובנוסף ידוע ש- שפת רגולרית. האם בהכרח שפה רגולרית? (תרגיל 5.4 בספר)
  • תשובה: לא בהכרח. דוגמה נגדית:
    • השפה אינה רגולרית.
    • השפה סופית ולכן רגולרית.
    • נגדיר פונקציה: . (פונקציה זו ניתנת לחישוב כי חסרת הקשר ולכן גם ניתנת להכרעה),
      • כמו כן מתקיים , ולכן זו פונקציית רדוקציית מיפוי: .

שאלה 5

ראו מועד 2024b-94 שאלה 4.

מועד 2024b-65

שאלה 1

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

שאלה 2

• א. תהיינה C,B,A שפות חסרות-הקשר.
  • קבעו לגבי כל אחת מהשפות הבאות אם היא שפה חסרת הקשר. יש להוכיח את טענתכם.
• תשובה:
  • השפה אינה בהכרח חסרת הקשר. דוגמה נגדית: ניקח את ו- להיות שתי שפות ריקות. ואת להיות שפה שאינה חסרת הקשר.
  • השפה היא חסרת הקשר, מאחר ששפות חסרות הקשר סגורות תחת איחוד ושרשור.
• ב. נתון הדקדוק הבא:
  • הוכיחו שהדקדוק זה יכול לגזור את המחרוזות .
    • תשובה: נראה גזירה:
  • האם אפשר לגזור בדקדוק הזה את המחרוזת:
    • תשובה: לא. המילה לא יכולה להתחיל באות .

שאלה 3

יהיה גרף לא מכוון. נגדיר את שתי השפות הבאות:

• א.הוכיחו שהשפה שייכת למחלקה P.
  • תשובה: תיאור אלגוריתם: “עבור קלט כאשר הוא מספר הצמתים בגרף :
    • נסמן את צומת ב- .
    • עבור כל מ- עד :
      • אם קיימת קשת המחברת בין צומת המסומנת ב- לצומת שאינה מסומנת, נסמן את ב- .
        
    • אם מסומנת בערך קטן או שווה ל- , נקבל, אחרת, נדחה.”
• ב. הוכיחו שהשפה היא NP-שלמה.
  • רמז: אפשר להניח ש- היא NP-שלמה;
  • נזכיר ש- היא שפת כל המחרוזות כאשר הוא גרף, ו -ו -הם צמתים בגרף וקיים מסלול המילטוני מהצומת לצומת .
  • תשובה:
    • ראשית, היא NP. כי אם יש לנו מסלול באורך גדול או שווה ל- , נוכל לבדוק את המסלול הזה בזמן פולינומיאלי.
    • נראה ש- היא NP-שלמה:
      • בעזרת רדוקציה מ- ל- : “עבור קלט כאשר ו- הם צמתים בגרף :
        • יהי מספר הצמתים בגרף .
        • נדפיס את .”
      • אם , אזי מכיל מסלול המילטוני באורך , מ- ל- , אזי .
      • אם , אזי מכיל מסלול פשוט באורך , מ- ל- , אבל ל- יש צמתים, אזי המסלול הוא מסלול המילטוני, כלומר .