מה היתה התשובה לשאלה הזאת?
((a* U 0 U epsilon*)*b)* over {a,b,c,d} - size of minimal DFS
לדעתי התשובה אמורה להיות 3 (מקבל, לא מקבל ומלכודת), אבל לא הייתה אפשרות כזאת, אז בחרתי 4
מה היתה התשובה לשאלה הזאת?
Forum
» Discussions / Q&A, Spring 2011
» מה היתה התשובה לשאלה הזאת?
כך אני ראיתי את זה:
בעצם מדובר בכל המחרוזות על איי ועל בי, שהן או המילה הריקה או מסתיימות ב-בי.
כלומר: שני מצבים: או שהאות האחרונה הייתה איי, או שהאות האחרונה הייתה בי.
המצב ההתחלתי זה המצב בו האות האחרונה הייתה בי, והוא גם המקבל.
איי כוכב מעביר למצב השני, הלא מקבל, ובי כוכב מחזיר למצב הראשון, המקבל.
התשובה הנכונה היא 2.
אני מקווה שאני צודק.
:)
שיט, בכלל לא שמתי לב שיש גם את סי ואת די.
הו וול.
לא הגיוני שזה 4, אם אפשר ב-3. אני סימנתי 2, כי אפשר להתחיל ממצב מקבל, להישאר בו עם בי, ללכת ללא מקבל עם איי, להישאר בלא מקבל עם איי, ולעבור מהלא מקבל למקבל עם בי.
אבל צריך בור בשביל c,d
אחרת זה לא דטרמיניסטי
גם לדעתי צריך להיות 3.. [המספר הטבעי היחיד שלא היה אפשר לבחור בו..]
כיוון שהביטוי הוא בעצם
((a*)b)*
כלומר כל המחרוזות הכוללות את איי ובי בלבד (גם באופן ריק) שאינן נגמרות באיי
התשובה היא 4
q0 - accepting
q1 - getting a's in a loop
q2 - accepting, getting b's in a loop
q3 - BOR for c,d
DELTA:
q0(a)->q1
q0(b)->q2
q1(a)->q1
q1(b)->q2
q2(a)->q1
q2(b)->q2
qi(c)->q3
qi(d)->q3
ברור שזה טאות והתשובה היא 3. השאלה איך הם יתחשבו לזה בציון?
שום טעות התשובה היא 4
מצב התחלתי, בור בישביל סי ודי, מצב שמקבלים תווי איי, ממנו מצב שמקבלים בי בודד. מהמצב שקיבל בי ניתן לעבור בחזרה למצב התחלתי
מה ההבדל בין המצב שקיבל בי לבין המצב ההתחלתי?
צד שני שחושבים על זה, מצב התחלתי זה המצב הראשון, ממנו חץ לעצמו עבור איי, חץ למצב שני שהוא מקבל בעזרת בי.
משניהם חץ לבור בעזרת סי ודי.
ממצב מקבל בעזרת בי במגיעים לעצמו, בעזרת איי מגיעים למצב הראשון…
וזה ניראה עכשיו 3 מצבים! :(
אני לא בטוח במאה אחוז במה שאני אומר, אבל הטיעונים והתשובות שנכתבו בשרשור הזה לא כ"כ משכנעות אותי ….
ישנן 2 מחלקות שקילות: המילה הריקה או כל המילים שנגמרות ב "בי"
לכן מצב מקבל עבור המילה הריקה
מקבל לא מקבל עבור כל השאר
מעבר מהמצב הלא מקבל למקבל כאשר מקבלים "בי"
יותר פשוט ממה שזה נראה ….
אין פה מה להשתכנע
אפשר לעשות את זה ב3 מצבים - כמו שיראלה כתבה זה מעולה
מבין האופציות שניתנו בשאלה, התשובה עם מס המצבים המינמימלי היא 4
וזה רק כי אי אפשר ב2
(כי חייבים בנוסף לתחילי המקבל, מצב אחד שניתן לחזור ממנו למקבל, ומצב אחד שלא ניתן לחזור ממנו למקבל)
ואם במחלקות שקילות עסקינן - שתי המחלקות שאמרת אינן מחלקות את" כל העולם" אלה רק את המילים שאתה כן רוצה לקבל, ולכן זה לא מספיק
אני מקווה שהם יביאו ניקוד מלא לכל מי שסימן 2 או 4, כי גם לי במבחן יצא 3 והקפתי 2.
/forum/t-342407/#post-
