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

[vinney]

תן לי להבין משהו

לפי מה קבעת שהF שלך יודע לחשב את כל השפה?

 

[gil levi]

אמממממ

אם אנחנו לא מחשבים את כל השפה, אז בעצם משלב מסויים אנחנו לוקחים איברים רק מאחת הרשימות: ➀, ➁. אבל L אינסופית, לכן לא ייתכן ש"כל" האיברים ברשימה אחת יהיו קטנים מ"כל" האיברים ברשימה האחרת, לכן מתישהו נעבור לרשימה השנייה.

 

[vinney]

נגיד...

בכל מקרה, מה שהוכחת זה לא R, זה RE, וזה בדיוק מה שהיית אמור להוכיח, לא?

 

[gil levi]

כמו שמסיח ומדיח כתב

בכיתה הוכח ששפה היא בR אמ"מ יש לה אנומרטור מונוטוני עולה.

 

[ron369]

אנומרטור = פונקציה שהתמונה שלה היא

השפה?

 

[gil levi]

אנומרטור

היא פונ' חשיבה ועל מקבוצת המספרים הטבעיים לשפה.

 

[ron369]

הטעות היא שזה נכון שזה מונוטוני

עולה, אבל לא בהכרח בשני איברים בכל פעם! כלומר, יכול להיות למשל שהאיבר ה"חמישי" בקבוצה מתקבל מ: l(1000000) או l(2^100000) או (וכולי'). הדבר יכול להתרחש בשתי הפונקציות, מכיוון שהן רק "חצי" מונוטוניות, ולכן ה"ספירה" יכולה למשל להתחיל בדילוג על האיבר הראשון - ולא למנות אותו שנית במשך זמן "אינסופי" (בשתי הרשימות). דוגמא נגדית: אני לא בטוח באיזה מודל אתם משתמשים לכל הדברים הללו, אך עבור פונקציה קבועה כלשהי, בקבוצה RE, בוודאי יש אינסוף תכניות שמחשבות אותה (כשבכל פעם אתה מוסיף פקודה כלשהי).

 

[gil levi]

תודה רבה.

 

[מסית ומדיח]

נראה לי ש...

אף אחד לא אמר לך שהזוגיים של l2 יחד עם האי זוגיים של l1 מכסים את כל השפה. יכול להיות למשל ש-

l1 = l2(x+1)​

והפונקציה שאתה מגדיר היא לא אינומרטור.

 

[vinney]

חבר'ה

אני מפספס משהו? שפה שיש לה אנומרטור זאת שפה בRE, זה בדיוק מה שהוא היה צריך להוכיח, הוא בטעות הניח ששפה שיש לה אנומרטור היא בR, אבל זה לא נכון (לא נכון לכל שפה, זאת אומרת). מדובר בשכבה 0 בהייררכיה של חומסקי (איש מעניין מאוד בפני עצמו). לגבי הטענה שלך, אם L1 או L2 אנומרטורים (והם כן) אז כל אחד מהם מכסה את כל השפה. אני לא ניסיתי להוכיח את זה, אבל לפי דעתי, הבניה שלו כן מבטיחה שהשילוב שלו מכסה את כל השפה (זה גם מה ששאלתי אותו, בהתחלה).

 

[מסית ומדיח]

אם האינומרטור מונוטוני אז היא ב-R

כי אפשר לעבור על המילים באינומרטור אחת אחת, ואתה יודע מתי לעצור בגלל המונוטוניות. בכל מקרה אני חושב שהבניה שלו לא נכונה כי היא משתמשת רק במילים במקומות האי זוגיים של l1 והזוגיים של l2. אם למשל מתקיים עבור האינומרטורים:

l1(x) = l2(x+1)​

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

 

[gil levi]

אהההה... לא שמתי לב....

תודה רבה.

 

[gil levi]

מספר שאלות נוספות.

אני מצטער שאני ככה מפציץ בשאלות, זה בגלל שאני פותר מבחנים עם שאלות אמריקאיות ובפתרונות רק מסומנת התשובה הנכונה אבל אין הסבר. שאלה ראשונה: נתונה בעיית ההכרעה הבאה: קלט: אוטומט מחסנית P. שאלה: האם L(P)zzz מכילה יותר מ n מילים באורך זוגי (כאשר n מספר טבעי הנתון מראש). קבעו לאיזו מחלקה שייכה הבעיה: R RE\R coRE\R אף לא אחת מהנ"ל.

 

[gil levi]

והתשובה

הבעיה בR. מישהו יכול להסביר לי מדוע הבעיה כריעה? אני מניח שזה קשור לכך שn מספר סופי ונתון מראש, אז ניסיתי להוכיח שהבעיה הבאה כריעה: קלט: אוטומט מחסנית P. שאלה: האם L(P) zzz מכילה מילה מאורך זוגי. אבל לא הלך.... מישהו יכול לעזור? תודה מראש.

 

[gil levi]

שאלה שניה:

נגדיר:

A={M | M is a Turing machine ∧ L(M)∈NP\P}​

בחר את התשובה הנכונה: A∈R ללא שום הנחות. A∉R ללא שום הנחות. A∈R אם ורק אם P=NP A∈R אם ואר אם P≠NP

 

[gil levi]

והתשובה:

A∈R אם ורק אם P=NP. כיוון אחד ברור לי: אם P=NP אז NP\P=∅ והוכחנו שלבדוק אם דקדוק חסר הקשר יוצר את השפה הכריעה זו בעיה בR (אפשר לעבור מאוטומט מחסנית לדקדוק חסר הקשר), לכן A בR. את הכיוון השני אני לא מבין. למה לבדוק אם L(M)∈NP\P זו בעיה לא כריעה? למה אם זו בעיה כריעה אז NP=P (או NP\P=∅)? תודה מראש.

 

[gil levi]

שאלה שלישית:

תהי L השפה:

L={<G1,G2,G3> | G1,G2,G3∈CFG ∧ L(G1)∩L(G2)∩L(G3)=∅}​

(CFG זו קבוצת הדקדוקים חסרי ההקשר). קבעו לאיזו מחלקה שייכת L: R RE\R coRE\R אף לא אחת מהנ"ל.

 

[gil levi]

והתשובה:

coRE\R הצלחתי להראות שהמשלימה של L היא בRE (כי אפשר לרוץ על כל המילים במקביל בשלושת הדקדוקים ואם מילה מתקבלת בשלושתם אז "נדע" מכך) אבל לא הצלחתי להראות שהשפה לא כריעה. חשבתי על רדוקצית מיפוי אל ALL_CFG (שפת כל הדקדוקים חסרי ההקשר שיוצרים את כל *Σ) אבל לא הצלחתי. מישהו יכול לעזור? תודה מראש.

 

[gil levi]

שאלה רביעית:

תהי L שפה. עבור מספר טבעי n נסמן ב lex zzz את המחרוזת ה n בסידור לקסיקוגרפי של מחרוזות L. נגיד שלL יש אנומרטור "מסודר" אם קיים לה אנומרטור (פונ' על וניתנת לחישוב) g:N-->L המקיים:

∀n |g|≤|lex|​

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

 

[gil levi]

והתשובה

א. אם לשפה יש אנומרטור מסודר אז היא רקורסיבית ולכל שפה רקורסיבית יש אנומרטור מסודר. הצלחתי להוכיח שלכל שפה רקורסיבית יש אנומרטור מסודר אבל את הכיוון השני לא הצלחתי להוכיח, כלומר: לא הצלחתי להוכיח שקיומו של אנומרטור מסודר גורר שהשפה רקורסיבית. ניסית לנסות להשתמש בתכונות של האנומרטור כדי למצוא אלגוריתם (שתמיד עוצר) לבדיקה אם מילה w היא בL, אבל לא הצלחתי. מישהו יכול לעזור? אגב, אני ממש לא מצפה שיענו לי על כל השאלות. כל עזרה שהיא תתקבל בשמחה. תודה מראש.