ביטוי רגולרי מעל א"ב $\Sigma$ מוגדר בהגדרה רקורסיבית ונגדיר אותו כך:

• כל אות $\sigma \in\Sigma$ היא ביטוי רגולרי.
• הביטוי $\emptyset$ הוא ביטוי רגולרי.
• המילה $\epsilon$ היא ביטוי רגולרי.

אלו מקרי הבסיס. כעת, נרצה להרחיב את ההגדרה באמצעות הצעד:
יהיו $r_{1},r_{2}$ ביטויים רגולריים. אזי גם הביטויים הבאים רגולריים:

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

פתרון א':

פתרון ב':

הביטוי: $b^*a^*$
הוכחה:

הוכחת הטענה:
⇒: אם $w$ מילה שבה כל האותיות $b$ מגיעות לפני האותיות $a$ אזי היא מהצורה $b\dots ba\dots a$ שאינה מכילה את הרצף $ab$.
⇐: אם $w$ לא מכילה את הרצף $ab$. נניח בשלילה שקיימת $b$ שמגיעה אחרי $a$. לכן, $w$ היא מהצורה $\_\_a\_\_b\_\_$.
נראה באינדוקציה כי חייב להיות $ab$ ב-$w$.
∎
נראה כי מתקיים $L[a^*b^*]=L_{1}$ ע"י הכלה דו כיוונית.
תהי $w \in L_{1}$. ע"פ הגדרת $L_{1}$ המילה $w$ לא מכילה את הרצף $ab$. ע"פ טענת העזר שלנו, כל ה-$a$-ים ב-$w$ מופיעים אחרי ה-$b$-ים. לכן, הצורה של $w$ היא: $b\dots ba\dots a$ ואז $w \in[b]^*[a]^*$ ולכן $w \in L[r]$.
תהי $w \in L[r]$, אזי, מהגדרת $L[r]$ מתקיים $w=b^ma^n$ כאשר $n,m \in \mathbb{N}$. לכן, $w$ היא מהצורה $b\dots ba\dots a$ ולכן, במילה לא מופיע הרצף $ab$ ולכן, ע"פ הגדרת $L_{1}$ מתקיים $w \in L_{1}$.
לכן, ע"פ הכלה דו כיוונית $L_{1}=L[r]$.
∎