כתבו ביטוי רגולרי (ב"ר) עבור שפת המילים מעל \Sigma=\{a,b\} שמתחילות ב-aa או שאינן מסתיימות ב-b. אפשר רק לנמק את התשובה מבלי להוכיח נכונות באופן פורמלי.
אני לא מצליח לחשוב על ביטוי רגולרי מספק לבעיה.
אשמח לעזרה.
הביטוי הרגולרי שמתאים הוא (aa)\cdot\Sigma^{*}+\Sigma^{*}\cdot a. נפריד לכיוונים:
-
נראה כי לכל w\in L מתקיים w\in L[r]. מילה שמתחילה ב-aa תתקבל על-ידי (a\cdot a)\cdot\Sigma^{*}. מילה שאינה מסתיימת ב-b היא או אפסילון, או שהיא מסתיימת ב-a ולכן תתקבל על-ידי \Sigma^{*}\cdot a. לכן לכל w\in L מתקיים w\in L[r].
-
נראה כי לכל w\in L[r] מתקיים w\in L. אם מילה התקבלה ע"י הב"ר הנ"ל אזי היא בהכרח מהצורה של אחד משלושת הביטויים ולכן מקיימת את התנאי של השפה. לכן, לכל w\in L[r] מתקיים w\in L.
סה"כ קיבלנו L[r]=L, כנדרש.