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

[gil levi]

תודה, אבל לא הבנתי משהו.

המצבים המקבלים של M יהיו מצבים לא מקבלים בM2 (לא חייבים להיות מצבים דוחים). המצבים הלא מקבלים (לא חייבים להיות דוחים) של M יהיו מצבים מקבלים בM2. נניח שM נכנסת ללולאה אינסופית לכל קלט, אז היא "מהצורה" הזו: נניח שא"ב קלט הוא {0,1}. במצב q1, אם M רואה 0 או 1 היא זזה שמאלה (או ימינה, זה לא משנה) ונשארת במצב q1. היות שq1 הוא מצב לא מקבל בM, הוא יהפוך למצב מקבל בM2, לכן M תקבל משהו. הפתרון ברור לי אם לא מקבל==דוחה, אבל אני חושב שלא לכך התכוונו.

 

[ron369]

ומה עם מכונה בלי מצבים, שעושה כלום?

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

 

[gil levi]

תודה.

 

[ron369]

בהצלחה ../images/Emo13.gif

ותיקון, סיגמה כוכבית.

 

[gil levi]

רביעית ואחרונה ../images/Emo51.gif

4. תהי CFD משפחת השפות המתקבלות על ידי אוטומט מחסנית דטרמיניסטי, המקבל במצב מקבל. כמה מהטענות הבאות נכונות: טענה1: CFD סגורה תחת איחוד. טענה2: CFD סגורה תחת חיתוך. טענה3: CFD סגורה תחת משלים. התשובה היא שרק טענה אחת נכונה. ברור שזו הטענה הראשונה כי CFD מוכלת ב CFL (משפחת השפות חופשיות ההקשר) וCFL סגורה לאיחוד (CFL לא סגורה לשאר הפעולות), אבל אני לא מצליח למצוא דוגמה נגדית לשאר הפעולות (לדעתי CLD מוכלת ממש בCFL אז אני לא יכול לקחת "סתם" שפה ח"ה). מישהו יכול לעזור? תודה מראש.

 

[ron369]

העיניים שלי הסתכלו מעצמן על התשובה

(בטעות!

) אגב, בקשר לדברים הקודמים שכתבתי: אסל"ד - אוטומט סופי לא דטרמיניסטי, אס"ד - אוטומט סופי דטרמיניסטי. בכל מקרה, התשובה שלך שגויה, כי יכול להיות למשל ש L הינה שפה ב-C, וגם ב-D. אם D חלקית ממש ל-C (למשל, D היא המחלקה שמכילה רק את השפה L, ו-C מכילה עוד שפות), בהחלט יכול להיות שגם אם C סגורה לחיסור, למשל, D לא סגורה! (כי יכול להיות שתמונת החיסור נמצאת ב-C אך לא ב-D). נסה למצוא שתי שפות ב-CFL כך שהן גם ב-CFD, אך איחודן וחיתוכן לא ב-CFL (ובפרט לא ב-CFD). מה עם זה: a*b^nc^n, a^nb^nc*? אני מניח שהחיתוך שלהן אינו ב-CFL, (והאיחוד שלהן דווקא כן) ושבכ"ז שתיהן ב-CFD. לא? זכור לי שהיה איזה משהו עם המחסנית שלא היה נחמד. ובקשר לאיחוד של שפות ח"ה (חופשיות הקשר), אתה בטוח? כי יש לי תחושה די משכנעת שאתה טועה. למשל: בהנתן שני דקדוקים ח"ה, נוכל פשוט לבנות דקדוק ח"ה שמקבל מילה אמ"מ היא מתקבלת באחד משניהם, שכן אנחנו יכולים להריץ את: S-> S1, S2, לא? לסיכום, אני לא עושה מעצמי צחוק, נכון? לא נגעתי באוטומטים כבר... חצי שנה? אז אל תתפוס אותי במילה, וקח את דברי בערבון מוגבל.

 

[gil levi]

תודה על התגובה.

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

 

[ron369]

לא, אני חושב שעדיין לא הבנת ../images/Emo8.gif

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

 

[gil levi]

צודק. תודה על התיקון.

 

[shirbi]

הטענה הנכונה היא דווקא השלישית.

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

 

[gil levi]

וגם סיבוכיות.

לקורס קוראים מודלים חישוביים (את"א). הנה אתר הקורס.

 

[gil levi]

אתם אנשים נפלאים!

אני בהלם שענו לי על הכל כל כך מהר. תודה לכולם! אני בכל אופן סיימתי ללמוד להיום. את התשובות אני אקרא מחר. שוב תודה רבה.

 

[gil levi]

שאלה נוספת.

נגדיר את הפעולה הבאה על שפה L:

SqrRot(L)={xy | x,y∈{0,1}*, y^n²x^n∈L}​

מהי השפה:

SqrRot(1*0*)∩0*1*​

 

[gil levi]

והפתרון

השפה היא :

0^n²1^n​

אני לא מבין מדוע זו השפה שמתקבלת. ברור לי שצריך להיות רצף של 0-ים ואחריו רצף של 1-ים, אבל מדוע החזקות הן n^2 ו n? אני חושב שהתוצאה היא

0^t1^k כי 0^t1^k∈ 0*1* ואם נסמן x=0^t y=1^k אז נקבל ש: 1^k)^n²(0^t)^n∈1*0* לכן: 0^t1^k∈SqrRot(1*0*)​

אז מדוע חייבים לדרוש ש t=n² ו k=n? תודה מראש.

 

[ron369]

משהו לא מסתדר לי פה

האם טעית בכתיבת השאלה? שים לב שבפרמטר של SqeRot נמצאת השפה:

0*1*​

ואילו בחיתוך, נמצאת השפה:

1*0*​

ברור ש1* יכול להתקבל, וגם ש 0*. לעומת זאת, קשה לי לראות איך יכול להיות משהו מהשפה 0+1+. סתירה? או שהתבלבלתי?

 

[vinney]

תסתכל על ההגדרה של SQEROT

XY וYX מתהפכים שם באמצע

 

[gil levi]

בדיוק

 

[ron369]

אה, נכון ../images/Emo13.gif

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

 

[gil levi]

אני? לא.. אבל תודה על ההתייחסות...

 

[gil levi]

ועוד אחת (על אנומרטורים)

לשפה אינסופית L ידוע כי קיימים שני אנומרטוים רקורסיביים l1,l2:N-->L שונים כך ש l1 הוא מונוטוני עולה ממש עבור המספרים האי זוגיים ו l2 הוא מונוטוני עולה ממש עבור המספרים הזוגיים. כלומר: עבור כל שני מספרים אי זוגיים a,b, אם a<b אז l1(a)<l1(b) zzz ועבור כל שני מספרים זוגיים a,b אם a<b אז l2(a)<l2(b) zzz. קבעו לאיזו מחלקה (הקטנה ביותר) שייכת L: R RE הפתרון הוא RE אבל הצלחתי "להוכיח" שL בR. איפה הבאג בהוכחה שלי: בכיתה הוכחנו שL רקורסיבית אמ"מ יש לה אנומרטור רקורסיבי מונוטוני עולה. נראה של L יש אנומרטור רקורסיבי מונטוני עולה f: נשים לב ש:

➀ l1(1)<l1(3)<l1(5)<l1(7)<l1(9)<l1(11)<l1(13)<l1(15)<l1(17)<... ➁ l2(2)<l2(4)<l2(6)<l2(8)<l2(10)<l2(12)<l2(14)<l2(16)<l2(18)<...​

f(1) zzz יהיה המינימלי מבין: l1(1), l2(2) zzz. f(2) zzz יהיה: 1. אם f(1)=l1(1) zzz, אזי f(2) zzz יהיה המינימלי מבין l2(2), l1(3) zzz. 2. אם f(1)=l2(2) zzz, אזי f(2) zzz יהיה המינימלי מבין l1(1), l2(4) zzz. נמשיך באותו אופן: בכל שלב ניקח את המינימלי מבין: האיבר הראשון ב ➀ והאיבר הראשון ב ➁ שעדיין לא לקחנו. (ז"א ש f תרשום על הסרט את האיברים שכבר לקחנו מהרשימות האלו, וכשצריך לחשב את האיבר הבא, היא תדע מה ה"אינדקס" של איבר האחרון שלקחנו ברשימה ➀ ומה האינדקס של האיבר האחרון שלקחנו ברשימה ➁ ). f שמקבלת באופן הזה היא מונוטונית עולה ממש, לכן L בR. אז איפה הטעות בהוכחה? תודה מראש.