שאלה- אוטומטים ושפות פורמליות.

[מכור אנונימי לקולה]

שאלה- אוטומטים ושפות פורמליות.

היי, מקווה שיש פה מישהו שמבין בנושא.
1. L1,...,Ln שפות רגולריות. האם השפה

L={w| שייכת לחצי (או יותר) מהשפות w}

רגולרית?
2. האם השפות הלא רגולריות סגורות לאיטרציה?

ב1, אני לא בטוח איך להתחיל אפילו. ב2, נראה לי שהתשובה היא לא, אבל אני לא מוצא דוגמא נגדית.

 

[1ca1]

תשובה

לגבי 1 - יש לך n שפות נתונות.
תיקח את כל תתי-הקבוצות האפשריות מגודל n/2 והלאה.
לכל אחת כזו, אתה מסוגל לבנות אס"ד שמקבל את החיתוך הזה נכון?
ומכאן תיקח אס"ד (נניח לא-דטרמיניסטי, זה לא משנה) שיעשה איחוד של כולן, הוא יבחר אקראית לאיזה קבוצת שפות (מגודל n/2) המילה שייכת ויריץ עליה את האס"ד המתאים, סה"כ הכל סופי כאן ואחלה.

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

 

[מכור אנונימי לקולה]

תודה!