חזור לתיקייה: תרגול

12 - משפט מייהיל-נרוד

חיפוש בתיקיה
Ctrl K
לחץ כאן או הקש Ctrl K כדי לחפש בכל התיקיה
  • כללי

12 - משפט מייהיל-נרוד

02340129

מבוא לתורת הקבוצות ואוטומטים למדמח

רשימות תרגול לקריאה בשבת

משפט מייהיל-נרוד

הופק מתוך תקיית התואר של שקד

uni-folder.vercel.app

הערה

זה יהיה במבחן!!!!!!!!!

הגדרה 1 (שקילות מייהיל-נרוד)

תהא L⊆Σ∗L \subseteq \Sigma^*L⊆Σ∗ שפה ויהיו x,y∈Σ∗x,y \in\Sigma^*x,y∈Σ∗.
נגדיר יחס ∼L\underset{L}{\sim}L∼​ שקילות מייהיל-נרוד באופ הבא:
  ⟺  x∼Ly\iff x \underset{L}{\sim}y⟺xL∼​y לכל מילה z∈Σ∗z \in\Sigma^*z∈Σ∗ מתקיים xz∈L  ⟺  yz∈Lxz \in L \iff yz \in Lxz∈L⟺yz∈L.

כלומר, x,yx,yx,y שקולות מייהיל-נרוד לפי LLL   ⟺  \iff⟺ לא קיים זנב מפריד z∈Σ∗z \in \Sigma^*z∈Σ∗ עבורו xz∈Lxz \in Lxz∈L וגם yz∉Lyz \not\in Lyz∈L או להפך.

הערה

שימו ש-∼L\underset{L}{\sim}L∼​ הוא יחס מעל Σ∗\Sigma^*Σ∗.

בהרצאה הוכחנו כי היחס ∼L\underset{L}{\sim}L∼​ הוא יחס שקילות ולכן מחלק את Σ∗\Sigma^*Σ∗ למחלקות שקילות.

דוגמה

L={ak∣k≡0(mod  2)},Σ={a}L=\left\{ a^k| k \equiv 0(mod\; 2) \right\}, \Sigma=\left\{ a \right\}L={ak∣k≡0(mod2)},Σ={a}

דוגמה למילים שקולות מייהיל-נרוד:

a,aaaa, \qquad aaaa,aaa

נוכיח זאת: יהי z∈Σ∗z \in\Sigma^*z∈Σ∗

  • אם ∣z∣|z|∣z∣ זוגי אז ∣xz∣,∣yz∣|xz|,|yz|∣xz∣,∣yz∣ אי זוגיים ולכן xz,yz∉Lxz,yz \not\in Lxz,yz∈L.
  • אם ∣z∣|z|∣z∣ אי-זוגי אז ∣xz∣,∣yz∣|xz|,|yz|∣xz∣,∣yz∣ זוגיים ולכן xz,yz∉Lxz,yz \not\in Lxz,yz∈L.

כלומר, לכל z∈Σ∗z \in\Sigma^*z∈Σ∗ מתקיים xz∈L  ⟺  yz∈Lxz \in L \iff yz \in Lxz∈L⟺yz∈L.

דוגמה למילים שאינן שקולות:

ε,a\epsilon, \qquad aε,a

נראה זנב מפריד בדמות z=az=az=a שעבורו aa∈Laa \in Laa∈L אך a∉La \not\in La∈L.

משפט

שפה LLL היא רגולרית   ⟺  \iff⟺ ביחס ∼L\underset{L}{\sim}L∼​ יש מספר סופי של מחלקות שקילות.

בנוסף, אם ביחס ∼L\underset{L}{\sim}L∼​ יש מספר סופי של מחלקות שקילות, זהו מספר המצבים המינימאלי ב-DFADFADFA עבור LLL.

תרגיל

הוכיחו באמצעות משפט מייהיל-נרוד שהשפה הבאה רגולרית מעל Σ={a,b}\Sigma=\left\{ a,b \right\}Σ={a,b}.

L={w∈Σ∗∣a מסתיימת ב-w}L=\left\{ w \in\Sigma^* | a\R{\text{ מסתיימת ב-}}w \right\}L={w∈Σ∗∣a מסתיימת ב-w}

הוכחה:
נוכיח כי יש מספר סופי של מחלקות שקילות ביחס ∼L\underset{L}{\sim}L∼​, ואז לפי משפט מייהיל, LLL רגולרית.
נטען שמחלקות השקילות הן

S1={w∈Σ∗∣a מתסיימת ב-w}S_{1}=\left\{ w \in\Sigma^*|a\R{\text{ מתסיימת ב-}}w \right\}S1​={w∈Σ∗∣a מתסיימת ב-w} S2={w∈Σ∗∣a לא מסתיימת ב-w}S_{2}=\left\{ w \in\Sigma^*|a\R{\text{ לא מסתיימת ב-}}w \right\}S2​={w∈Σ∗∣a לא מסתיימת ב-w}

נוכיח שאלו אכן מחלקות השקילות:

  1. האיחוד הוא Σ∗\Sigma^*Σ∗: נוכיח כי S1∪S2=Σ∗S_{1}\cup S_{2}=\Sigma^*S1​∪S2​=Σ∗ בהכלה דו כיוונית. (תרגיל לבית!)
  2. הקבוצות לא ריקות: S1≠∅S_{1}\neq \emptysetS1​=∅ כי a∈S1a \in S_{1}a∈S1​ ו-S2≠∅S_{2}\neq \emptysetS2​=∅ כי b∈S2b \in S_{2}b∈S2​.
  3. אם x,y∈Six,y \in S_{i}x,y∈Si​ אז x∼Lyx \underset{L}{\sim}yxL∼​y:
    • יהיו x,y∈S1x,y \in S_{1}x,y∈S1​. מהגדרת S1S_{1}S1​, x,y∈Σ∗x,y \in\Sigma^*x,y∈Σ∗ ומסתיימות ב-aaa. נראה כי אין ביניהן זנב מפריד ולכן x∼Lyx \underset{L}{\sim}yxL∼​y.
      יהא z∈Σ∗z \in \Sigma^*z∈Σ∗.
      א. אם zzz מסתיימת ב-aaa או z=εz=\epsilonz=ε אז xz,yzxz,yzxz,yz מסתיימות ב-aaa ולכן xz∈Lxz \in Lxz∈L וגם yz∈Lyz \in Lyz∈L.
      ב. אם zzz מסתיימת ב-bbb אז xz,yzxz,yzxz,yz מסתיימות ב-bbb ולכן xz∉L∧yz∉Lxz \not\in L \land yz \not\in Lxz∈L∧yz∈L.
    • יהיו x,y∈S2x,y \in S_{2}x,y∈S2​. (המקרה שקול ולכן תרגיל לבית!!!!!)
  4. אם x∈Si,y∈Sjx \in S_{i},y \in S_{j}x∈Si​,y∈Sj​ עבור i≠ji\neq ji=j אז x̸∼Lyx \not \underset{L}{\sim}yxL∼​y:
    תהי x∈S1x \in S_{1}x∈S1​ ותהי y∈S2y \in S_{2}y∈S2​. מהגדרת הקבוצות xxx מסתיימת ב-aaa ו-yyy לא מסתיימת ב-aaa לכן z=εz=\epsilonz=ε הוא זנב מפריד כי נקבל
    xz∈L∧yz∉Lxz \in L \land yz \not\in Lxz∈L∧yz∈L
    לכן, x̸∼Lyx \not \underset{L}{\sim}yxL∼​y.
    ∎

בהוכחת משפט מייהיל-נרוד ראיתם שניתן לייצג את המצבים באס"ד מינימלי עבור LLL, בעזרת מחלקות השקילות כך:

Q={[w]L∣w∈Σ∗}Q=\left\{ [w]_{L}|w \in\Sigma^* \right\}Q={[w]L​∣w∈Σ∗} q0=[ε]Lq_{0}=[\epsilon]_{L}q0​=[ε]L​ F={[w]∣w∈L}F=\left\{ [w]|w \in L \right\}F={[w]∣w∈L} δ([w],σ)=[wσ]\delta([w],\sigma)=[w\sigma]δ([w],σ)=[wσ]

נראה אוטומט עבור השפה מהתרגיל האחרון.

Full_firstAutomation start q0 S2 start->q0 q1 S1 q1->q1 a q1->q0 b q0->q1 a q0->q0 b
תרגיל

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

L={a2n∣n∈N}L=\left\{ a^{2^n}|n \in \mathbb{N} \right\}L={a2n∣n∈N}

לכל Σ={a}\Sigma=\left\{ a \right\}Σ={a}.

הוכחה:
נוכי שביחס ∼L\underset{L}{\sim}L∼​ יש ∞\infty∞ מחלקות שקילות, וממשפט מייהיל-נרוד נסיק ש-LLL לא רגולרית.
נראה שלכל m,n∈Nm,n \in \mathbb{N}m,n∈N כך ש-m<nm<nm<n מתקיים שמחלקות השקילות של a2n,a2ma^{2^n},a^{2^m}a2n,a2m שונות.
כדי להראות זאת, מספיק להראות זנב מפריד בין המילים ואז נסיק a2m̸∼La2na^{2^m}\not\underset{L}{\sim}a^{2^n}a2mL∼​a2n ולכן [a2m]≠[a2n][a^{2^m}]\neq[a^{2^n}][a2m]=[a2n].
נבחר z=a2n∈Σ∗z=a^{2^n}\in\Sigma^*z=a2n∈Σ∗. נסמן x=a2n,y=a2mx=a^{2^n},y=a^{2^m}x=a2n,y=a2m.

xz=a2na2n=a2n+2n=a2⋅2n=a2n+1∈Lxz=a^{2^n}a^{2^n}=a^{2^{n}+2^n}=a^{2\cdot 2^n}=a^{2^{n+1}} \in Lxz=a2na2n=a2n+2n=a2⋅2n=a2n+1∈L yz=a2ma2n=a2m+2n=a2m(1+2n−m)yz=a^{2^m}a^{2^n}=a^{2^m+2^n}=a^{2^m(1+2^{n-m})}yz=a2ma2n=a2m+2n=a2m(1+2n−m)

כיוון ש-n>mn>mn>m אז n−m>0n-m>0n−m>0. לכן, 1+2n−m>11+2^{n-m}>11+2n−m>1 מספר אי זוגי ואז 2m(1+2n−m)2^m(1+2^{n-m})2m(1+2n−m) לא יכול להיות חזקה של 2 כי בחזקה של 2 כל הגורמים בכפל הם מספרים זוגיים. סה"כ, yz∉Lyz \not\in Lyz∈L. לכן, zzz הוא זנב מפריד בין x,yx,yx,y ולכן x̸∼Lyx \not \underset{L}{\sim}yxL∼​y.
לכן, לכל m<n∈Nm<n \in \mathbb{N}m<n∈N מתקיים [a2n]≠[a2m][a^{2^n}]\neq [a^{2^m}][a2n]=[a2m] ולכן יש ∞\infty∞ מחלקות שקילות ביחס ∼L\underset{L}{\sim}L∼​.
∎

תרגיל

תהי LLL שפת כל המילים מעל Σ={a,b}\Sigma=\left\{ a,b \right\}Σ={a,b} שאינן מכילות את הרצף bbbbbb.
בנו אס"ד עבור LLL והוכיחו שהוא מינימלי.

נבנה אס"ד עבור LLL:

A=(Q,Σ,q0,δ,F)A=(Q,\Sigma,q_{0},\delta,F)A=(Q,Σ,q0​,δ,F)

כאשר:

Full_firstAutomation start q0 q0 start->q0 q0->q0 a q1 q1 q0->q1 b q1->q0 a q2 q2 q1->q2 b q2->q2 a,b
Q={q0,q1,q2},Σ={a,b},F={q0,q1}Q=\left\{ q_{0},q_{1},q_{2} \right\},\Sigma=\left\{ a,b \right\},F=\left\{ q_{0},q_{1} \right\}Q={q0​,q1​,q2​},Σ={a,b},F={q0​,q1​}

כאשר δ\deltaδ ניתנת להסקה מהציור.
בנינו אס"ד עבור LLL עם 3 מצבים. לכן, ממשפט מייהיל-נרוד נסיק שביחס ∼L\underset{L}{\sim}L∼​ יש לכל היותר 3 מחלקות שקילות.
נראה כעת, כי ביחס ∼L\underset{L}{\sim}L∼​ יש לפחות 3 מחלקות שקילות ואז נסיק שביחס יש בדיוק 3 מחלקות שקילות, ולכן AAA שבנינו הוא מינימאלי.
נראה זאת ע"י כך שנראה שקיימות 3 מילים שאינן שקולות ביחס ∼L\underset{L}{\sim}L∼​ ולכן נקבל שיש לפחות 3 מחלקות שקילות.
נסתכל על המילים x,y,w∈Σ∗x,y,w \in\Sigma^*x,y,w∈Σ∗ כאשר x=ε,y=b,w=bbx=\epsilon,y=b,w=bbx=ε,y=b,w=bb.

  • מתקיים x̸∼Lyx \not \underset{L}{\sim}yxL∼​y כי z=bz=bz=b זנב מפריד שכן xz=b∈L∧yz=bb∉Lxz=b \in L \land yz=bb \not\in Lxz=b∈L∧yz=bb∈L.
  • מתקיים y̸∼Lwy \not \underset{L}{\sim}wyL∼​w כי z=εz=\epsilonz=ε זנב מפריד שכן yz=b∈L∧wz=bb∉Lyz=b \in L \land wz=bb \not\in Lyz=b∈L∧wz=bb∈L.
  • מתקיים x̸∼Lwx \not \underset{L}{\sim}wxL∼​w כי z=εz =\epsilonz=ε זנב מפריד שכן xz=ε∈L,wz=bb∉Lxz=\epsilon \in L,wz=bb \not\in Lxz=ε∈L,wz=bb∈L.

לכן, קיבלנו כי יש לפחות 3 מחלקות שקילות. עם החלק הקודם נסיק שיש בדיוק 3 מחלקות שקילות. לכן, לפי משפט מייהיל-נרוד, AAA הוא אס"ד מינימאלי.