התלבטות קשה-סגירות של שפות רגולריות

[Bill Gatesss]

התלבטות קשה-סגירות של שפות רגולריות

שלום לכולם ! אני תלמיד י"א, מסיים השנה 5 יחידות מדעי המחשב (שנה שעברה עשיתי 2 + 1 אקסס) נתקלנו בהתלבטות לגבי פתרון לשאלה שהיתה במבחן המגן, וכן, זה כולל את המורה. כאשר שפת L (רגולרית) מורכבת מאיחוד של 6 שפות נניח, האם שרשור של L עם L, שזה L*L, האם חייב ששתי השפות המיוצגות ב L*L יהיו אותן שפות מתוך 6 השפות האפשריות ? אסביר מעבר ואדגים; נניח ששפת L מורכבת מאיחוד של 6 שפות - L1 או L2 או L3 או L4 או L5 או L6 אם ניקח את שפת L, היא יכולה להיות פעם אחת L3 נניח, ופעם אחרת L5, או כל אחת משש האפשרויות. האם ב L*L, חייבת לבוא לידי ביטוי אותה שפה משש השפות, בשני מופעי ה-L ? כלומר L2*L2 נניח ? ****או**** האם L*L יכול לבטא שרשור של שפות שונות, המרכיבות למעשה את L למשל L*L יוכל להיות מבוטא ע"י L3*L1 (שכל אחת מהן בעצם שייכת ל L !) אם תשאלו אותי, נראה לי הגיוני שיתאפשרו מופעים שונים של חלקי שפת L בביטוי L*L. או במלים אחרות - האפשרות השניה. מצד שני, המורה טוענת שההגדרה של שרשור, L*L, היא למעשה L בריבוע, ואז חייבת לחזור על עצמה אותה מילה בדיוק. אך גם המורה מתלבטת קשות ואין ממש החלטה בעניין אשמח לשמוע דעותיכם ! תודה, אבנר

 

[vinney]

אני חושב שאתה קצת מפספס את ההגדרה

איחוד קבוצות זאת קבוצה המכילה את כל הערכים מהקבוצות באיחוד. במקרה שלנו L מכילה את כל המילים מL1, L2, L3, L4, L5 וL6. לא פעם ככה ופעם ככה, יש רק פעם אחת, ובה L מכילה את כולן. נסמן את M = L*L שרשור של L עם עצמה. מהאמור לעיל, מתקבל שM מכילה את כל|הסדגש| הקומבינציות של מילים המהווים שרשור VW, כשV וגם W הן מילים מתוך L1, או L2, או L3, או L4 או L5, או L6.

 

[Bill Gatesss]

אוקיי ../images/Emo26.gif

כלומר אתה מחזק את הטענה שלי, ש L*L יכול להיות W1*W2 ולאו דווקא W1*W1. בזה שאמרתי "פעם ככה ופעם ככה" כמובן שלא התכוונתי לכך, אלא כדי לומר ש L יכול להיות W1 ובאותה עת L יכול להיות גם W2 במקרה אחר, עם אותה שפת L תודה על התגובה המהירה !