חלוקה מימין

חלוקה מימין

student (guest) 26 Jul 2016 20:33

מישהו יכול בבקשה להביא לי דוגמא נגדית לכך ששפות חסרות הקשר לא סגורות תחת 'חלוקה מימין' ?

sapir (guest) 27 Jul 2016 09:43

יש לי רעיון להוכחה שהן סגורות תחת חלוקה מימין עם שפה *רגולרית:
אפשר להגדיר הומומורפיזם שלכל מילה יסמן את הסוף שלה ששייך לשפה השניה.
כעת נבצע חיתוך עם השפה הראשונה כדי להשאיר רק את המילים שהסוף שלהן שייך לשפה השניה.
לבסוף עם הומומורפיזם נוסף שמעביר למילה הריקה כל תו מסומן נקבל את כל המילים ששייכות לחלוקה מימין.

משום שיש צורך בחיתוך, הפעולות שעשיתי סגורות רק עם שפות רגולריות.*

לכן לדעתי אין סגירות עם שפות לא רגולריות, ניתן להראות זאת למשל עם הדוגמה שראינו בהרצאה לחיתוך של שתי שפות ח"ה:
0^n1^n2^* and 0^*1^n2^n
נקבל שהחיתוך מימין של השפה משמאל עם השפה מימין הוא:
0^n1^n2^n
שהיא לא ח"ה.

אשמח להערות אם ההוכחה נראית נכונה :-)

סטודנט (guest) 27 Jul 2016 17:05

תודה רבה

סטודנט (guest) 27 Jul 2016 17:15

אפשר קצת הסבר על הדוגמא למטה שהבאת. כי גם המילים
o^n
נמצאים בחלוקה
כי אפשר להוסיף להם
1^n*2^n
מהשפה מימין
ולקבל מילה בשפה משמאל..
בנוסף גם מילים מהצורה
0^n*1^n
נמצאים בחלוקה מימין, כי אפשר להוסיף להם את המילה הריקה מהשפה מימין ולקבל מילה מהשפה משמאל..

את מדברת על חלוקה מימין או חיתוך?

sapir (guest) 27 Jul 2016 20:55

נכון אתה צודק, כנראה שהדוגמה הזאת לא טובה לחלוקה מימין