אוטומט סופי

הגדרה:
Pasted image 20240112231606.png

דוגמאות:
Pasted image 20220709191856.png

Pasted image 20220709191914.png
המצבים המקבלים הם $q_{2, 4}$ .
Pasted image 20220709191952.png
יגיע למצב $q_{1}$ .

Pasted image 20220709192020.png
נזכיר שזו מתארת את פונקציית המעברים כלומר בהנתן מצב וקלט, הפלט יהיה המצב החדש ולכן התשובה זה $q_{1}$ .

Pasted image 20220709192115.png
נזכיר שזאת היא הפעלה פונקציית המצבים על המחרוזת לפי הסדר. כלומר
$δ (q_{5}, b) \to q_{1}$ וממשיכים כעת להפעיל את פונקציית המצבים על $q_{1}$ עם האות הבאה, הלוא היא $a$ . וכן הלאה. לכן התוצאה תהיה $q_{4}$ .

Pasted image 20220709192340.png
כדי להבין מה שפת האוטומט מומלץ להבין איך מגיעים עם הקלט הקצר ביותר למצב מקבל, ומשם לפתח את זה. כעת, נשים לב ששפת האוטומט על הקלט הכי קצר הוא $b a$ או $a b$ זה רמז שיעזור לנו להבין משם מה קורה. סך הכל נקבל ששפת האוטומט תהיה

{w \in {a, b}^{*} | (# a_{w} mod 3) + (# b_{w} mod 2) = 2

Pasted image 20220709202521.png

Pasted image 20220709202544.png
נזכיר שבאוטומט מכפלה לחיתוך קבוצת המצבים היא קבוצה של זוגות סדורים כך שאיבר אחד בזוג יהיה מאוטומט A והאיבר השני בזוג יהיה מאוטומט $B$ . זאת בעייה קומבינטורית פשוטה, נקבל שיש סך הכל במקרה זה 12 אפשרויות לזוגות.

Pasted image 20220709202813.png
גם כאן קבוצת המצבים המקבלים היא זוג סדור ולכן יש 2 מצבים מקבלים אפשריים.

Pasted image 20220709202926.png
בגדול הטכניקה עבור אופרטורים כאלה על שפות האוטומט הוא אותו דבר, בנייה של זוג סדור, ההבדל היחיד הוא רק בקבוצת המצבים המקבלים.
סך הכל במקרה זה קבוצת המצבים המקבלים תהיה

(F^{A} \times Q^{B}) \cup (Q^{A} \times F^{B})

כלומר יש סך הכל , $2 ֿ \cdot 2$ עבור צד שמאל של האיחוד ו $6 \cdot 1$ עבור צד ימין. אלה לא קבוצות זרות אבל יש להן רק שתי איברים משותפים אחד לכן סך הכל יהיו $8$ מצבים מקבלים.

Pasted image 20220709203926.png
לאוטומט $C$ אין מצבים מקבלים בכלל ולפי הגדרת זוג סדור $A \times \emptyset = \emptyset$ . לכן יש 0 מצבים מקבלים באוטומט המכפלה לחיתוך.

Pasted image 20220709204158.png

האוטומט שבנינו פה הוא הרחבה של האוטומט $D$ שכן המצבים המקבלים של שניהם זהים. עם זאת, ניתן לראות שבסך הכל יש פה שרשור לשפת $L (D)$ שכן ההבדל היחיד הוא שנוצר מצב התחלתי חדש שכל עוד יש $b$ נשארים בו ורק $a$ שובר אותו ונכנס ל $q_{0}^{D}$ . סה״כ

L (E) = {b}^{*} \circ {a} \circ L (D)

Pasted image 20220709204830.png
כעת נשים לב שאנחנו מתחילים בתוך מצב ששייך ל $Q^{D}$ ולכן אין שום משמעות למצב ההתחלתי $q_{0}^{E}$ ולכל המעברים הבאים לידי ביטוי באמצעותו. סך הכל השפה תהיה $L (D)$ .

Pasted image 20220709205036.png
כעת המצב ההתחלתי של $E$ הוא מצב התחלתי בעצמו. כלומר השפה תהיה

L (E^{'}) = {b}^{*} \circ ({ε} \cup L (D))

נשים לב, הסיבה שלא איחדנו פשוט את הסגור קלין על $b$ עם שפת האוטומט $D$ היא שבאופן של איחוד לא ניתן להגדיר מילים שמתחילות ב $b$ ומסתיימות באיזשהי מילה השייכת לשפת האוטומט $D$ .

Pasted image 20220709205522.png

לא נכון, מספיק להגדיר שהמצב ההתחלתי הוא מצב מקבל. למעשה זהו תנאי הכרחי ומספיק. כלומר אם המחרוזת הריקה היא בשפת האוטומט (כאשר הוא סופי דטרמיניסטי) זה בהכרח אומר שהמצב ההתחלתי הוא מצב מקבל והפוך.

Pasted image 20220709205729.png
כמובן שלא נכון

Pasted image 20220709205745.png
נכון ההגדרה של אוטומט סופי דטרמיניסטי היא חמישייה סדורה שאחד האיברים בה הוא המצב ההתחלתי. בהגדרה חייב להיות אחד כזה.

Pasted image 20220709205908.png
לא נכון למשל אוטומט המתאר את ${a}^{*}$ .

Pasted image 20220709205948.png
לא נכון קצת לא אינטואיטיבי אבל ניתן לבנות אוטומט עם שני מצבים מקבלים ולאחד מהם לא ניתן להגיע כלל.

Pasted image 20220709210039.png
נכון זה אומר למעשה שחייב להיות מצב שתוקע אותנו מלהגיע אי פעם למצב מקבל באוטומט. למשל, אוטומט מעל $Σ = {a, b}$ המקבל רק את המחרוזת $a$ . כיוון שבהגדרה של אוטומט סופי דטרמיניסטי, חייב להגדיר מסלול עבור כל קלט, אנחנו נצטרך להגדיר שעבור $b$ או עבור $a$ לאחר שנשלח $a$ כבר פעם אחת, האוטומט ייכנס למסלול שלא יגיע למצב מקבל לעולם.

Pasted image 20220709210334.png
הפרכה אותו א״ב כמו מקודם רק שהפעם שפת האוטומט תהיה ${a}^{*}$ . גם במצב זה הקלט $b$ ישלח אותנו למצב תקוע. למרות שהשפה היא אינסופית.

Pasted image 20220709210517.png
נכון המקרה הקצה היחיד הוא המחרוזת הריקה אבל בתרחיש זה עדיין מתקיים התנאי יהיה מצב אחד יותר מאורך המחרוזת.

אוטומט סופי לא דטרמיניסטי

Pasted image 20220709210714.png
נשים לב שבאוטומט סופי לא דטרמינסטי, פונקציית המעברים היא לקבוצת החזקה של קבוצת המצבים כי כל קלט יכול להחזיר כמה מצבים.

והסגור קלין על פונקציית המעברים היא זהה במשמעותה למה שאמרנו על סגור קלין על פונקציית המעברים באוטומט סופי דטרמינסטי. פשוט קריאה של מחרוזת ולא תו.

כאן יתקיים ש

Δ^{*} (q_{0}, b b b) = {q_{2}, q_{3}, q_{4}}

Pasted image 20220709211418.png

באותו אופן יתקיים ש

Δ^{*} (q_{0}, b b a) = {q_{3}}

Pasted image 20220709211524.png
כן אם נעשה מעבר אפסילון ל $q_{4}$ ואז נקרא $b$ .

Pasted image 20220709211601.png
לא

Pasted image 20220709211619.png
לא

Pasted image 20220709211725.png
נזכיר שאוטומט למשלים זה אותו אוטומט בידיוק עם המצבים המקבלים ההפוכים לכן $q_{0}$ יהיה מצב מקבל וזהו תנאי הכרחי ומספיק בשביל שאפסילון תהיה שייכת לשפת האוטומט. חשוב לשים לב שכאן אפסילון זה המחרוזת הריקה ולא המעבר אפסילון

עוד משהו שחשוב לשים לב אליו לפי מה שאמרתי למעלה, אם שפה מסויימת היא רגולרית אז המשלים של אותה שפה היא רגולרית גם כן כרגע הראתי איך לבנות לה אוטומט.

(שפה L הינה שפה רגולרית אם קיים אוטומט סופי דטרמיניסטי A המקיים L(A) = L)

Pasted image 20220709221016.png

({a} \circ {b}^{*}) \circ {b}^{*}

Pasted image 20220709221516.png
אלגוריתם ההמרה באופן כללי אומר להוסיף מעברים במקום איפה שיש מעברי אפסילון כלומר. אם יש מעבר אפסילון בין $q_{i}$ ל $q_{i - 1}$ אז אנחנו נלך ל $q_{i - 2}$ ונוסיף ממנו את המעברים המתאימים ל $q_{i}$ . המעברים המתאימים הם המעברים מ $q_{i - 2}$ ל $q_{i - 1}$ . זה אפשרי בגלל המודול הלא דטרמינסטי.

(נזכיר את ההגדרה של $C L (q)$ שהיא קבוצת כל המצבים שניתן להגיע אליהם מ $q$ ללא קריאת קלט). כעת נזכיר שמה שמשתנה באלגוריתם ההמרה הוא פונקצייה המצבים והמצבים ההתחלתיים , המצבים ההתחלתיים החדשים יהיו המצב ההתחלתי הקודם וכל מה שניתן להגיע אליו מהמצב ההתחלתי ללא קריאת קלט.

Δ^{N} (q, σ) = ⋃_{p \in Δ^{ε} (q, σ)} C L (p)

Q_{0}^{N} = ⋃_{p \in Q_{0}^{ε}} C L (P)

זה עובד כי $C L (q)$ באופן לא מפתיע מכיל את עצמו.
לכן אלו הם הרכיבים היחידים שמשתנים.

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

Pasted image 20220709223518.png
לפי אלגוריתם המעבר יהיו $8$ מעברים סך הכל.

Pasted image 20220709225706.png
נזכיר מהו אלגוריתם ההמרה מאוטומט לא דטרמינסטי לאוטומט דטרמינסטי
החמישייה החדשה של האוטומט הדטרמיניסטי נראת כך

\begin{matrix} Q^{D} = P (Q^{N}) \\ Σ^{D} = Σ^{N} \\ δ^{D} (R, σ) = ⋃_{q \in R} Δ^{N} (q, σ) \\ F^{D} = {R \in Q^{D} : | R \cap F^{N} \neq \emptyset} \\ q_{0}^{D} = Q_{0}^{N} \end{matrix}

נשים לב שכעת מצב הוא קבוצה . לכן המצב ההתחלתי מייצג את קבוצת המצבים ההתחלתיים של האוטומט הלא דטרמינסטי.

Pasted image 20220709232728.png
לפי מה שאמרנו זאת קבוצת החזקה של קבוצת המצבים לכן $2^{4}$ מצבים.
כמה מצבים מקבלים?
לפי מה שאמרנו זה יהיה כל הקבוצות שמכילות בתוכן את $F^{A}$ . סך הכל בנוסף למצבים המקבלים הרגילים מתווספים עוד 3 (זאת בעייה קומבינטורית וקל להוכיח אותה). לכן $5$ מצבים מקבלים.

Pasted image 20220709235502.png
לא נכון כדי שמילה לא תהיה בשפה המקבלת אוטומט לא דטרמינסטי צריך שלא תהיה בכלל קריאה של המילה שתגיע למצב מקבל. מנגד כדי שמילה תהיה בשפה מספיק שתהיה קריאה אחת שמגיעה למצב שכזה.

Pasted image 20220709235615.png
לא נכון, יש שקילות בין המודל הדטרמינסטי למודל הלא דטרמינסטי.

Pasted image 20220709235650.png
נכון כמו שאמרנו, $C L (q)$ תמיד יחיל את $q$ .

Pasted image 20220709235751.png
נכון. נובע ישירות מאלגוריתם ההמרה הנ״ל.

Pasted image 20220709235845.png
התהליך שהאוטומט עושה, הינו באופן הבא, האוטומט מבצע את כל המעברים הרגילים של $Q^{A}$ עד הגעה למצב מקבל. שם באופן לא דטמינסטי על הקלט $b$ מחליט האם להמשיך לעבור במצבים של הראשון או לעבור ל $B$ . כיוון שהמעבר הזה הוא על הקלט $b$ בלבד, אין מדובר באיחוד של השפות אלא בשרשור שלהן. כמו כן נשים לב שהמצבים המקבלים של $N$ . הם המצבים המקבלים של $B$ בלבד. כלומר, על מנת להגיע למצב מקבל באוטומט החדש המודל הלא דטרמינסטי חייב להכנס למעברים של האוטומט $B$ . סך הכל שפת האוטומט תהיה

{w_{1} b w_{2} | w_{1} \in L (A), w_{2} \in L (B)}

Pasted image 20220710000512.png

כעת האי דטרמיניזם בא לידי ביטוי במעבר אפסילוני, כלומר אין פה שרשור של $b$ , עם זאת זה נראה כאילו מעבר האפסילון עובר לאן ש $B$ היה עובר מקריאת הקלט $a$ במצב ההתחלתי, כלומר פוסחת על הקלט הזה. כלומר השמטנו את האות $a$ מהקלט שהיה מגיע למצב מקבל ב $B$ . ובכתיב מתמטי

{w_{1} w_{2} | w_{1} \in L (A), a \circ w_{2} \in L (B)}

Pasted image 20220710001203.png
Pasted image 20220710001521.png
מילת המפתח כאן היא או . ברגע שאומרים דבר כזה, הכי קל יהיו לבנות שתי אוטומטים דטרמינסטים לכל אחד מהאפשרויות, ולחבר בינהם עם מצב התחלתי חדש ומעברי אפסילון. זה בידיוק מה שעשינו למעלה. האוטומט העליון מ $q_{1}$ הוא דטרמינסטי לשפת כל המילים ש $a a$ מופיע בהן והאוטומט התחתון מ $q_{4}$ הוא דטרמינסטי לשפת כל המילים שהן באורך אי זוגי. $q_{0}$ מחבר בינהן עם שתי מעברי אפסילון.

Pasted image 20220710001739.png

א תכונה זו עבדה רק באוטומט סופי דטרמינסטי מהסיבה הפשוטה שהמודל הלא דטרמינסטי לא מבטיח שאם קלט לא מגיע למצב מקבל הוא שייך לשפת המשלים. יכול להיות מספר מעברים לכל קלט גם כזה שבשפה וגם כזה שלא.

הכי קל יהיה להדגים את זה עם אוטומט שמקבל את השפה $Σ^{*}$ כאשר $Σ = {a, b}$ .

Pasted image 20220710002008.png
לפי מה שאמרנו מקודם . אם נהפוך את המצבים המקבלים על פניו, השפה המקבלת את האוטומט אמור להיות המילה הריקה. אך זה לא המצב.

ב לא ייתכן. האוטומט המשלים הוא גם כן אוטומט סופי. לפי מה שהראנו לכל אוטומט סופי לא דטרמינסטי ישנו אוטומט סופי דטרמינסטי שקול. אטען טענה חזקה יותר: אם $N$ הוא אוטומט סופי לא דיטרמינסטי ו $D$ הוא האוטומט הסופי הדטרמינסטי השקול. אז $\overset{―}{D}$ יהיה האוטומט הדטרמינסטי השקול היא $\overset{―}{N}$ .

Pasted image 20220710002540.png

הוכחה יהי שפה $L$ רגולרית. קיים לה אוטומט סופי דטרמינסטי ובאופן שקול קיים אוטומט סופי לא דטרמינסטי המקבל אותה נסמנו $A$ $(Q^{A}, Σ, Δ^{A}, Q_{0}^{A}, F^{A})$ . כעת נבין מה רוצים מאיתנו בתרגיל. רוצים את היכולת בסופו של דבר, להשמיט אות ממחרוזת ששייכת לשפה $L$ אבל לאפשר לה עדיין שייכת לשפת האוטומט החדש. לשם כך נשאלת השאלה אולי אפשר לבנות מעברי אפסילון בין המצבים עצמם באוטומט הלא דטרמינסטי שהגדרנו. אבל זה יהיה בעייתי כיוון שהמצב המקבל עדיין יאפשר את המילים בשלמותן בעוד ש dropout לא מאפשר. לכן מה שנעשה הוא נשכפל את כל המצבים בידיוק כפי שהם ונייצר קבוצת מצבים חדשה.

Q^{N} = Q^{A} \cup Q^{A^{'}}

כאשר $Q^{A^{'}} = {q^{'} | q \in Q^{A}}$ . כעת נוכל לחבר בין כל מעבר לעוקב המשוכפל שלו במעבר אפסילון למשל אם יש מעבר מ $q_{i}$ ל $q_{j}$ נגדיר מעבר אפסילון מ $q_{i}$ ל $q_{j}^{'}$ . מעבר לזה המעברים בתוך $A^{'}$ יהיו זהים למעברים ב $A$ כלומר עבור קלט $σ$ אם אני במצב השייך לשכפול נזוז לעוקב בשכפול אחרת נזוז רגיל.
המצב ההתחלתי נשאר אותו דבר והמצב המקבל יהיה המצב המקבל בקבוצב $A^{'}$ כלומר אותם מצבים מקבלים רק בשכפול. ככה באופן לא דטרמינסטי נדלג מתישהו על קלט בודד ואז נשאר בתוך המצבים המשוכפלים. באופן פורמלי נגדיר את החמיישה הבאה עבור $N$ (את קבוצת המצבים הגדרנו למעלה אז אדלג עליה).

\begin{matrix} Σ^{N} = Σ \\ Q_{0}^{N} = {q_{0}^{A}} \\ F^{N} = {p^{'} | p \in F^{A}} \\ Δ^{N} (q, σ) = {\begin{cases} {δ (q, σ)} & q \in Q^{A} \\ {δ (q, σ)^{'}} & q \in Q^{A^{'}} \\ {p^{'} | \exists_{α \in Σ} : p = δ (q, α)} & σ = ε \end{cases} \end{matrix}

Pasted image 20220710010321.png

תהי $L$ שפה רגולרית. אז קיים לה אוטומט סופי דטרמינסטי המקבל אותה (בכוונה אני בוחר במודל הדטרמינסטי הפעם). נסמנו $A = (Q, Σ, δ, q_{0}, F)$ . נגדיר את האוטומט הלא דטרמינטי $N$ באופן הבא

\begin{matrix} Q^{N} = Q \\ Σ^{N} = Σ \\ q_{0}^{N} = q_{0} \\ F^{N} = F \\ Δ (q, σ) = {δ (q, t) : t \in Σ} \end{matrix}

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

Pasted image 20220710011118.png
נרצה לבנות מעין אוטומט מכפלה לא דטרמינסטי. קבוצת המצבים תהיה המכפלה הקרטזית של כל הצירופים האפשריים של המצבים מ $L_{1}$ ו $L_{2}$ . קבוצת המצבים המקבלים גם כן תהיה המכפלה הקרטזית של קבוצת המצבים המקבלים $L_{1}, L_{2}$ . פונקציית מעברים תהיה פונקצייה שבהינתן קלט $σ$ מפעילה אותו כמו שהיה מופעל באוטומט של $L_{1}$ אבל באופן לא דטרמינסטי בוחרת אות אקראית ומתקדמת באוטומט של $L_{2}$ . נשים לב שנגיע למצב מקבל רק אם המילה שייכת ל $L_{1}$ וגם קיימת מילה ב $L_{2}$ באותו האורך כלומר המצבים המקבלים הם $F_{1} \times F_{2}$ .