תרגול

פתרון א':
נבנה $\epsilon-NFA$ עבור $L_{-\sigma}$ באופן הבא:

כאשר:

כעת נוכיח את נכונות האוטומט. כלומר, נראה כי $L(B)=L_{-\sigma}$ באמצעות הכלה דו כיוונית.
כיוון ראשון, $L_{-\sigma}\subseteq L(B)$:
תהי $u \in L_{-\sigma}$. מהגדרת $L_{-\sigma}$ קיימת $w \in L$ כך ש-$u=w_{-\sigma}$. $w \in L$ ולכן מהגדרת שפת $NFA$, קיימת ל-$A$ ריצה מקבלת על $w$.
מהגדרת $B$, הריצה הזו קיימת גם ב-$B$, פרט לכך שאם קוראים באוטומט $A$ את האות $\sigma$ אז ב-$B$ קוראים $\epsilon$.
לא שינינו את המצבים ההתחלתיים והמקבלים, לכן זו ריצה מקבלת של $B$ על $u$. לכן, $u \in L(B)$ מהגדרת שפת אוטומט.
מהגדרת הכלה $L_{-\sigma}\subseteq L(B)$.
כיוון שני, $L(B)\subseteq L_{-\sigma}$:
תהי $u \in L(B)$. מהגדרת שפת אוטומט, קיימת ל-$B$ ריצה מקבלת על $u$. מהגדרת $B$, אותה ריצה קיימת ב-$A$ פרט לכך שאם עברנו במעבר $q \overunderset{\epsilon}{B}{\longrightarrow}p$ אז ב-$A$ קיים המעבר $q \overunderset{\sigma}{A}{\longrightarrow}p$.
לא שינינו מצבים התחלתיים או מקבלים מ-$A$ ולכן זוהי ריצה מקבלת של $A$ על המילה $w$, שהתקבלה מ-$u$ ע"י הוספת $\sigma$ אות(אולי). לכן, $u=w_{-\sigma}$ ומתקיים $w \in L(A)$. מהנתון $L=L(A)$ ולכן $w \in L$. סה"כ מהגדרת $L_{-\sigma}$ נקבל $u \in L_{-\sigma}$.
מהגדרת הכלה, $L(B) \subseteq L_{-\sigma}$.
לכן, ע"פ הכלה דו כיוונית $L(B)=L_{-\sigma}$.

פתרון ב':
נבנה עבור $L_{+\tau}$ אוטומט סופי א"ד באופן הבא: $C=(Q,\Sigma \cup \left\{ \tau \right\},I,\tilde{R},F)$ כאשר $\tilde{R}=R \cup \left\{ (q,\tau,q)|q \in Q \right\}$.

הוכחה:
השפות $L_{0},L_{1},L_{2}$ רגולריות ולכן קיימים להן $DFA$-ים $A_{0},A_{1},A_{2}$ כך ש-$L(A_{i})=L_{i}$ לכל $i \in \left\{ 0,1,2 \right\}$ נסמן:

נבנה $\epsilon-NFA$:

כאשר:

∎