שאלה במודלים חישוביים.

[gil levi]

שאלה במודלים חישוביים.

השאלה בתמונה. הפתרון הוא:

f(L)={a,b}*​

אבל אם ניקח את המילה x=0011 אזי:

f(x) = {aavw|v,w∈b*}⊂{a,b}*​

והמילה x מכילה שני אפסים רצופים. או לחילופין, אם ניקח w∈f(x) zzz, אז w היא ב *{a,b}, אבל אין לה מקור ב L. אז איך זה יכול להיות ש f(L) = {a,b}* zzz ? תודה מראש.

 

[gil levi]

שאלה נוספת במודלים חישוביים.

(פיצלתי את השאלות למספר הודעות כדי שיהיה מסודר). השאלה: הוכיחו שעבור א"ב Σ שמכיל תו אחד, כל שפה חסרת הקשר מעל Σ היא גם רגולרית. הפעם הפתרון בתמונה. אני מבין את הפתרון, אבל אני לא מבין למה (בשורה ה14) אפשר להניח ש:

m≡m' (mod k)​

רק כדי להיות בטוח שאני מבין את הסימון, הכוונה ששארית החלוקה של m ב K זהה לשארית החלוקה של 'm ב K? אם כן, אז אני לא מבין מדוע הניחו כך והתעלמו בבפתרון מהמקרה ההפוך. מישהו יכול להסביר לי בבקשה? תודה מראש.

 

[מסית ומדיח]

הסבר

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

 

[gil levi]

שאלה אחרונה במודלים חישוביים.

הוכיחו שהבעיה הבאה אינה כריעה: קלט: מכונת טיורינג M. שאלה: האם M(ε)=17 ? הפתרון שלי הוא לפי משפט רייס: הבעיה לא טריוויאלית כי אם נגזיר מ"ט (מכונת טיורינג) M1 שהפלט שלה הוא 0 לכל קלט ומ"ט M2 שהפלט שלה הוא 17 לכל קלט, נקבל שעבור M1 התשובה היא "לא" ועבור M2 התשובה היא "כן". תהיינה M3 וM4 מ"ט שמחשבות את אותה פונ' חלקית. ברור ש:

(M3(ε)=17) ⇔ (M4(ε)=17)​

(כי M3 ו M4 מחשבות את אותה פונ' חלקית). מכאן שהבעיה סמנטית ולא טריוויאלית, לכם לפי משפט רייס היא אינה כריעה. ∎ האם הפתרון שלי נכון? אני שואל כי בפתרון שנתנו לנו בנו רדוקציה ל HALT0 , מה שנראה לי הרבה יותר מסובך, ובגלל זה אני לא בטוח. תודה מראש.

 

[nullity]

אאל"ט

בראש עמוד השאלות נאמר לכם לא להשתמש במשפט רייס

 

[gil levi]

דווקא לא.

ואיך אתה יודע מזה? אתה גם לוקח עכשיו מודלים באת"א?

 

[nullity]

לקחתי בסמסטר שעבר

וגם אם לא, אני יכול להגיד לך שזה מה שהיה כתוב אז, ו99% שהפיתרונות לא שונו בהתאם

 

[ahab]

למה שזה לא יהיה?

שים לב שההשמה מייחסת ל-1 כל רצף של bים, כולל הרצף הריק. כלומר, המקור של aab יכול להיות 001, ויכול גם להיות 011101.

 

[gil levi]

תודה.