כתבו ביטוי רגולרי עבור שפה של מילים עם תנאים

הביטוי הרגולרי שמתאים הוא (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, כנדרש.