ועוד שאלה באוטומטים

[FigureSkater]

מישהו יכול לעזור באוטומטים?

יש לי שאלה אשמח אם מישהו יוכל לעזור, פשוט אין לי מושג איך פותרים: הנה השאלה: ו- הן שפות רגולריות מעל . הוכח באמצעות בניית אוטומט ש- הבאה רגולרית: ; ; לכל i, , } קיימת , וקיים k, , כך ש: (אם n=1 כל היא בלבד) ו

 

[FigureSkater]

סליחה, מצרף קובץ

 

[FigureSkater]

ועוד שאלה באוטומטים

בבקשה אם מישהו יכול לעזור, ישבתי על זה כבר שעתיים תהי L שפה מעל א"ב , כך שכל מחלקת שקילות של יחס השקילות RL היא סופית. האם L רגולרית? אם בהכרח כן - הוכח; אם בהכרח לא - הוכח; אחרת - תן דוגמא לכל אפשרות

 

[FigureSkater]

מצרף קובץ

 

[1ca1]

בבקשה

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

 

[FigureSkater]

משפט mn

מה זה משפט MN?

 

[1ca1]

Myhill-Nerode

http://en.wikipedia.org/wiki/Myhill-Nerode_theorem

 

[vinney]

המטרה של הפורום זה לא לפתור שיעורי בית...

 

[FigureSkater]

אכן

רק מבקש הכוונה- הפורם נועד ללבן נושאים במדמח

 

[1ca1]

עדיף להעלות pdf או תמונה

בד"כ אני לא פותח doc, ולכן למשל לא עניתי על השאלה השנייה שלך...

 

[FigureSkater]

תכף מעלה

פדפ

 

[FigureSkater]

pdf

מצורף pdf של השאלה

 

[1ca1]

תשתמש באוטומט לא דטרמיניסטי

לניחוש חלוקה וגדלי מילים