אוטומטים-מחלקות שקילות עבור שפה

[אורןפרי1]

אוטומטים-מחלקות שקילות עבור שפה

קבוצת כל המילים מעל {a,b} המתחילות ב-aa ומסתיימות ב-b האם ניתן לומר שכביטוי רגולרי זו השפה (aab)+zzz או aab*zzz

 

[vinney]

לא

ולא אתה מנסה לנחש? במקרה הראשון זאת שפה שבנויה מ"aab" שחוזרים על עצמם, ובמקרה השני זאת שפה שמתחילה בaa ואז יש 0 ויותר bים. לא זה ולא זה נכון.

 

[yythe1]

כביטוי רגולרי זה כך

aa (aUb)* b​

 

[גיל14]

בד"כ מסמנים ב+, כלומר

aa(a+b)*b

 

[yythe1]

לא קריטי , העיקר הכוונה ושזה ברור : )

 

[אורןפרי1]

אוקיי תודה ובעניין מחלקות השקילות

בקובץ המצורף.. ועוד שאלה דומה L={a^i b^j c^k| 0<=i;i+j<=k}zzz Sigma={a,b,c}zzz האם אפשר לומר שהיבטוי הרגולרי הוא ab)+k*zzz) כאשר הפלוס מעל ab

 

[vinney]

בוודאי שלא

+ אומר שיש מופע אחד לפחות, אבל במקרה שלך, גם מילה ריקה היא בשפה

 

[אורןפרי1]

צודק אז זה צריך להיות

(a)*(b)*(c) מה יהיה מעל C פלוס או כוכבית? ומה לגבי המחלקות שקילות שצירפתי בתגובה הקודמת ?

 

[vinney]

לא, זה עדיין לא נכון

שים לב, שמספר המופעים של C לא יכול להיות קטן ממספר המופעים של a ו b, אבל יכול להיות שווה להם. אצלך c מופיע בדיוק פעם אחת, שזה אומר שזה יכול להיות קטן מa+b מצד אח, וגדול מצד שני, תלוי במה הם, וזה לא מה שנדרש. אם מעל c מופיעה כוכבית, אז הביטוי יכלול את השפה שתיארת, אבל לא רק אותה. מכיוון שהשפה אינה רגולרית, אי אפשר לרשום ביטוי רגולרי שיתאר אותה במדויק. לגבי מה שצירפת: 1 נכון 2 לא נכון (שים לב, מה קורא אם אחרי b אין יותר a? אצלך זה בפנים, בפועל זה בחוץ, וגם - למה מתחיל מaa?) 3 לא נכון. למשל aabbaa יהיה ב3, ואצלך לא 4 נכון שים לב שמדובר באוטומט לא דטרמיניסטי, ולכן זה מאוד בעייתי לרשום את מחלקות השקילות (תכל'ס, גם איפה שרשמתי נכון, בגלל האי-דטרמיניזם, יכול להיות מצב שאותה מילה תהיה בפנים או בחוץ, תלוי במה האוטומט מחליט לעשות, לכן לפני שאתה מחלק למחלקות שקילות, צריך קודם להביא את האוטומט למצב דטרמיניסטי)

 

[אורןפרי1]

כן אבל

אם אני מעביר את האוטומט לדטרמינסטי אז יוצא שיש לי 6 מצבים. ולא כמו עכשיו 4 ז"א S0={epsilon}zzz S1={a}zzz S2={aa}zzz S3={aaa*}zzz S4={aaa*b*}zzz S5={ab(ab)*}zzz מוזר ..

 

[אורןפרי1]

ולגבי השאלה השנייה

נניח ש-i,j=0 אז k=0 ז"א C מופיע לפחות פעם אחת.ואז מעל C יכול להיות כוכבית אבל המצב הבעייתי הוא שלמשל i,j=3 ואז k=6 ומעלה. ואז אם הכנסנו את המילה aaabbbc היא תתקבל למרות שהיא לא אמורה.. אז מעל C צריך להיות משהו אחר

 

[vinney]

כאמור, זאת לא שפה רגולרית

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

 

[אורןפרי1]

אכן זו שפה לא רגולרית

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

 

[vinney]

לא הבנתי מה בדיוק אתה רוצה להראות

להציג ביטוי רגולרי לשפה זה לא בדיוק מחלקת שקילות, זה דרך אחרת לתאר את השפה (שברור שהיא שקולה לעצמה).

 

[אורןפרי1]

לרשום את מחלקות השקילות של היחסRL

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

 

[vinney]

קראת את הערך בויקיפדיה על משפט נרוד?

הם מדגימים שם איך עונים על השאלה שלך בפירוט רב מאוד, אז במקום שאעתיק לך הכל - פשוט תקרא

 

[אורןפרי1]

אחלה תודה רבה על הקישור

בהקשר לשפה שיש לי הקבוצות Sk={a^ib^jc^k} k>=0 Tk={a^ib^jc^k} k>0 ואז אני מראה עבור i,j כלשהם שונים זה מזה a^i , a^j אינם שייכים לאותה מחלקת שקילות - כלומר, קיימת מילה Z שמפרידה בינן.

 

[אורןפרי1]

?