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

gil levi

New member
מספר שאלות במודלים חישוביים.

החלטתי לפצל למספר הודעות בשביל שיהיה מסודר. 1. נתונות שתי בעיות L1, L2. הראתי שבהנתן x לL1 אפשר לבנות ממנו (על ידי הפונ' f) קלט f(x) zzz לבעיה L2 כך ש:
f(x)∈L2 ⇒ x∈L1​
ובהנתן קלט y ל L2 אפשר לבנות ממנו (על ידי הפונ' g) קלט g(y) zzz לבעיה L1 כך ש:
g(y)∈L1 ⇒ y∈L2​
הבעיה היא ש g שונה מf, ז"א שבהינתן קלט לL1 אני יכול להפוך אותו לקלט לL2 בדרך מסוימת ובהנתן קלט לL2 אני יכול להפוך אותו לקלט לL1 אבל בדרך אחרת . האם ניתן להסיק מכאן שקיימת רדוקצית מיפוי בין L1 ל L2 ? תודה מראש.
 

gil levi

New member
שאלה שניה

2.תהיינה L1 ו L2 שפות כלשהן ותהא L3=L1L2, כלומר: L3 היא השרשור של L1 ושל L2. איזו מהטענות הבאות נכונה: טענה1: אם L3 וL1 רגולריות אזי L2 בהכרח רגולרית. טענה2: אם L3 רגולרית וL1 סופית, אזי L2 בהכרח רגולרית. הפתרון הוא ששתי הטענות אינן נכונות, אבל אני לא מצליח למצוא דוגמא נגדית. מישהו יכול לעזור? תודה מראש.
 

gil levi

New member
כן. זה הפתרון של המתרגל.

אבל הוא כתב שהפתרון "טענה 2 נכונה וטענה 1 לא נכונה" גם התקבל.
 

ahab

New member
לגבי טענה 1

קח את L1 כשפה *a, ואת L2 כ-a^nb^n L1 רגולרית, L2 אינה רגולרית, ו-L3 (השפה *a*b) רגולרית.
 

shirbi

New member
אהממ אהממ...

בכל המילים בשפה L3 יש תמיד יותר a-ים מאשר b-ים, ולכן היא לא רגולרית.
 

ron369

New member
אבל... אבל 2 נכון!

אני הייתי חושד לשפיותו של המתרגל שלך, אם זה יכול להיות רגולרי ותמיד לא רגולרי, לטענתו (?) בכל מקרה, נניח ש L2 לא רגולרית, ו (בשלילה) ש - L3 כן. ולכן, קיים אסל"ד שמקבל אותה (את L3). כעת נוכיח שקיים אסל"ד עבור L2. הוא יפעל כך: 1) בדוק האם קיימת רישא כלשהי מתוך L1, כך שעם רישא זו, המילה שמתקבלת היא ב-L3. עשה זאת כמובן בצורה אי דטרמיניסטית. 2) החזר תשובה בהתאם. ברור שאפשר לבנות אסל"ד שמבצע בדיקה זו, מכיוון ש L1 סופית (נכון? האוטומטים שלי די חלודים). הגענו לסתירה, ולכן הטענה הוכחה. מש"ל.
 

shirbi

New member
נסיון להפריך את 1:

L1 היא *a L2 היא a^n כאשר n ראשוני. כמובן ש L1 רגולארית וש L2 לא רגולארית. כמובן ש L3 היא גם רגולארית.
 

shirbi

New member
נסיון להפריך את 2:

בחר L1 - השפה הריקה. תקבל כמובן שגם L3 היא השפה הריקה, ללא תלות בבחירת L2. בחר לך L2 לא רגולרית כרצונך.
 

ron369

New member
טוב, אז 2 לא נכון...

מקרי קצה שוליים
 

vinney

Well-known member
לא הבנתי

אם אתה משרשר שפה ריקה עם השפה L, אז אתה מקבל L, לא שפה ריקה, לא ? (ז"א במקרה שלך L3 וL2 יהיו זהות).
 

shirbi

New member
לא.

השפה הריקה איננה השפה שמכילה את המילה הריקה, אלא השפה שלא מכילה אף מילה. שרשור של שתי שפות A ו B פרושו כל המילים מהצורה xy כך ש x שייכת ל A ו y שייכת ל B. מכיוון שבמקרה שלנו A שפה ריקה, אין אף x מתאים, ולכן השפה AB היא שפה ריקה גם כן.
 

gil levi

New member
שאלה שלישית.

3. תהא D מכונת טיורינג המקבלת כקלט תיאור של מכונת טיורינג M ומחזירה כפלט תיאור של מכונת טיורינג M2, כך ש M2 מתקבלת על ידי הגדרת המצבים המקבלים בM כלא מקבלים ב M2, וכמו כן הגדרת המצבים הלא מקבלים ב M ככן מקבלים בM2. מבלד שינויים אלו, M2 זהה לחלוטין ל M. איזה מהטענות הבאות נכונה: טענה1: אם M דטרמיניסטית וL(M) zzz אינה השפה הריקה, אז בהכרח L(M)!=L(M2) zzz. טענה2: לכל מכונת טיורינג דטרמיניסטית M מתקיים, L(M)!=L(M2) zzz. הפתרון הוא שטענה 1 נכונה וטענה2 לא נכונה. אני לא מבין מדוע טענה2 לא נכונה. אם L(M)=∅ zz אז M דוחה הכל או נכנסת ללולאה אינסופית על כל קלט אם גם וגם. אם היא דוחה כל קלט, אז המצב שבוא היא דוחה הופך למקבל בM2 ולכן M2 מקבל משהו (או שהיא קיבלה משהו לפני שהיא הגיעה למצב הדוחה של M). בכל מקרה, במצב הראשון ב M, שבו היא קוראת את התו הראשון, M2 כבר מקבלת, אז איך ייתכן ש L(M2)=∅ zzz? מה אני מפספס כאן? תודה מראש.
 

ron369

New member
תשרשר את התשובות בהודעה שונה, או

שלפחות תשים "ספויילר"... הטענה כנראה לא נכונה פשוט כי המכונה הריקה מקבלת... כלום. בלי קשר למצבים מקבלים או לא מקבלים. האמת היא שאצלנו הגדירו את זה באופן מעט שונה, כך שאני לא בטוח לגמרי בתשובה שלי, אבל אם ניחשתי נכונה את ההגדרות שלכם...
 

gil levi

New member
אפילו לא ההגדרות שלנו!

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

shirbi

New member
הזכרת את התשובה בעצמך...

אם M נכנסת ללולאה אינסופית עבור כל אחד מהקלטים, אז השפה שלה היא כמובן הקבוצה הריקה. השפה של M2 תהיה גם הקבוצה הריקה, מכיוון שגם היא לא תעצור על שום קלט. לכן השפות שלהן שוות.
 
למעלה