שאלה על שפות רגולריות
- פותח הנושא liorgu
- פורסם בתאריך
זה הרעיון שלי..
אם אנחנו מחפשים שפה שמכילה את כל המילים שהמילים בL הן לא תתי מילים שלהן אז אפשר להגיד ש-אלה כל המילים בסיגמא כוכבית פחות כל המילים שהן תתי מילים בL(פחות=חיתוך גג). (קל למצוא אוטומט שמוכיח רגולריות עבור Ls-שפת תתי המילים של L) ואם אני לא טועה עם משפט קליני ידוע שכל שפה שמורכבת מחיתוך של שפות רגולריות גם היא רגולרית...אני לא ממש למדתי את המשפט הזה אז אם אני טועה זו לא התשובה P: אבל אם כן, זה רגולרי למדי.
אם אנחנו מחפשים שפה שמכילה את כל המילים שהמילים בL הן לא תתי מילים שלהן אז אפשר להגיד ש-אלה כל המילים בסיגמא כוכבית פחות כל המילים שהן תתי מילים בL(פחות=חיתוך גג). (קל למצוא אוטומט שמוכיח רגולריות עבור Ls-שפת תתי המילים של L) ואם אני לא טועה עם משפט קליני ידוע שכל שפה שמורכבת מחיתוך של שפות רגולריות גם היא רגולרית...אני לא ממש למדתי את המשפט הזה אז אם אני טועה זו לא התשובה P: אבל אם כן, זה רגולרי למדי.
ויני, שאלה לי אלייך
איך זה שאתה נמצא כאן תמיד?! כלומר, נכון שאתה מנהל הפורום.. אבל אתה נמצא כאן בצהריים, בערב, מוקדם בבוקר וראיתי אותך גם בלילה! חשבתי שלפחות הלילה יהיה רק שלי כדי שאוכל להיות מסתורי ומגניב אבל לאאאא אז חשבתי לעצמי "אולי בבוקר מוקדם מוקדם אשיג בלעדיות מעל כולם" ושוב אתה מופיע >< ארררר
איך זה שאתה נמצא כאן תמיד?! כלומר, נכון שאתה מנהל הפורום.. אבל אתה נמצא כאן בצהריים, בערב, מוקדם בבוקר וראיתי אותך גם בלילה! חשבתי שלפחות הלילה יהיה רק שלי כדי שאוכל להיות מסתורי ומגניב אבל לאאאא אז חשבתי לעצמי "אולי בבוקר מוקדם מוקדם אשיג בלעדיות מעל כולם" ושוב אתה מופיע >< ארררר
פיתרון
הדרך שלי שונה אבל נראה לי נכונה(אני מקווה ) הרעיון כזה בשפה המקורית רגולרית, לכן קיים אוטומט סופי דטרמיניסטי המקיים אותה. לוקחים את כל המצבים שמהם ניתן להגיע למצב מקבל (ניתן בקלות למצוא אותם , זה גם בחלוקה למחלקות שקילות בדיוק כל המצבים ואולי פחות אחד שממנו אי אפשר אף פעם להגיע למצב מקבל. ושמים את כל המצבים האלא בתור מצב מקבל. זוהי בדיוק השפה של כל התת מילים של השפה המקורית, כלומר כל תת מילה בשפה המקורית תיהיה פה ובגלל שקיים אוטומט שמקיים אותה הרי שפה זו רגולרית. כעת השפה ההפכית לשפה זאת גם היא רגולרית וזה בדיוק מה שאתה צריך.
הדרך שלי שונה אבל נראה לי נכונה(אני מקווה ) הרעיון כזה בשפה המקורית רגולרית, לכן קיים אוטומט סופי דטרמיניסטי המקיים אותה. לוקחים את כל המצבים שמהם ניתן להגיע למצב מקבל (ניתן בקלות למצוא אותם , זה גם בחלוקה למחלקות שקילות בדיוק כל המצבים ואולי פחות אחד שממנו אי אפשר אף פעם להגיע למצב מקבל. ושמים את כל המצבים האלא בתור מצב מקבל. זוהי בדיוק השפה של כל התת מילים של השפה המקורית, כלומר כל תת מילה בשפה המקורית תיהיה פה ובגלל שקיים אוטומט שמקיים אותה הרי שפה זו רגולרית. כעת השפה ההפכית לשפה זאת גם היא רגולרית וזה בדיוק מה שאתה צריך.
פיתרון אמיתי
לא ברור לי אם זה איך שרשמתם את הפתרון לא כל כך ברור לי הציור כי הוא לא גמור. אבל הרעיון שלי הוא מצבים גוררים. הסבר:תחילה קיים אס"ד לשפה הראשונה L. ניקח את כל מצבי האוטומט שמסומנים ב Q0--QN ונבנה אוטומט עם מצבים Q0 טאג,Q1 טאג--QN טאג ועוד מצב החלתי שנסמנו QS כאשר קיים מעבר בין QI טאג לQJ טאג אמ"ם QJ הוא מצב מקבל. קיימת קשת בין QS לבין Q0 טאג אמ"ם Q0 המקורי מצב מקבל. נסמן באסלד זה כל המצבים כמצבים מקבלים למאל QS. בנינו אסל"ד שמקבל את השפה שכל תת מילה שלו היא מילה בשפה המקורית. ולכן שפה זאת רגולרית ולכן גם השפה ההפוכה רגולרית והיא מה שצריך.
לא ברור לי אם זה איך שרשמתם את הפתרון לא כל כך ברור לי הציור כי הוא לא גמור. אבל הרעיון שלי הוא מצבים גוררים. הסבר:תחילה קיים אס"ד לשפה הראשונה L. ניקח את כל מצבי האוטומט שמסומנים ב Q0--QN ונבנה אוטומט עם מצבים Q0 טאג,Q1 טאג--QN טאג ועוד מצב החלתי שנסמנו QS כאשר קיים מעבר בין QI טאג לQJ טאג אמ"ם QJ הוא מצב מקבל. קיימת קשת בין QS לבין Q0 טאג אמ"ם Q0 המקורי מצב מקבל. נסמן באסלד זה כל המצבים כמצבים מקבלים למאל QS. בנינו אסל"ד שמקבל את השפה שכל תת מילה שלו היא מילה בשפה המקורית. ולכן שפה זאת רגולרית ולכן גם השפה ההפוכה רגולרית והיא מה שצריך.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.