#computational_models

אוטומט מחסנית

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

על המחסנית אפשר לעשות מספר פעולות

נוכל להוציא מראש המחסנית בלי להכניס כלום.
נוכל להוציא מראש המחסנית ומייד להכניס משהו אחר לראש המחסנית
נוכל לא להוציא ולא להכניס כלום לראש המחסנית.
נוכל להכניס לראש המחסנית בלי להוציא.

Pasted image 20240112230944.png|350

הגדרה פורמלית

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

Δ : (Q \times (Σ \cup {ε}) \times (Γ \cup {ε})) \to P (Q \times Γ^{*})

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

הגדרה מתמטית של תהליך החישוב

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

כעת, שתי קונפיגורציות $C_{1, 2}$ נסמן $C_{1} ⊢_{P} C_{2}$ אם ניתן לעבור מ $C_{1}$ ל $C_{2}$ על ידי מעבר יחיד. באותו אופן נסמן $C_{1} ⊢_{P}^{*} C_{2}$ אם ניתן לעבור מ $C_{1}$ ל $C_{2}$ בסדרת צעדים.

סך הכל שפת האוטומט מוגדרת להיות

L (P) = {w | \exists_{u \in Γ^{*}, f \in F} : (q_{0}, w, ε) ⊢_{P}^{*} (f, ε, u)}

הגדרה מתמטית של תהליך החישוב

כעת, שתי קונפיגרציות $C_{1, 2}$ נסמן $C_{1} ⊢_{P} C_{2}$ אם ניתן לעבור מ $C_{1}$ ל $C_{2}$ על ידי מעבר יחיד. באותו אופן נסמן $C_{1} ⊢_{P}^{*} C_{2}$ אם ניתן לעבור מ $C_{1}$ ל $C_{2}$ בסדרת צעדים.

סך הכל שפת האוטומט מוגדרת להיות

L (P) = {w | \exists_{u \in Γ^{*}, f \in F} : (q_{0}, w, ε) ⊢_{P}^{*} (f, ε, u)}

שקילות אוטומט מחסנית לשפה חסרת הקשר

שפה $L$ הינה חסרת הקשר אם ורק אם קיים אוטומט מחסנית $P$ כך ש $L (P) = L$ . והמסקנה המתבקשת מכך היא שכל שפה רגולרית היא שפה חסרת הקשר. כי כל אוטומט סופי הוא אוטומט מחסנית בלי להשתמש במחסנית.

טכניקה כללית לבניית אוטומט מחסנית על פי כללי הדקדוק

תמיד יהיו שלושה מצבים בלבד מצב התחלתי, מצב מקבל, ומצב ביניים
דוחפים למחסנית במעבר אפסילון $S $$ מהמצב ההתחלתי למצב הביניים. ממצב הביניים נעבור למצב מקבל כשנשאר רק $ במחסנית.
במצב הביניים עושים את הדברים הבאים :

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

Pasted image 20220710232836.png|450

חיתוך של שפה רגולרית עם שפה חסרת הקשר

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

דקדוק רגולרי ושפות רגולריות

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

דקדוק רגולרי ימני

הכללים הם אחת מהצורות הבאות.

\begin{matrix} A \to σ B \\ A \to σ \\ A \to ε \end{matrix}

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

דקדוק רגולרי שמאלי

הכללים הם אחת מהצורות הבאות.

\begin{matrix} A \to B σ \\ A \to σ \\ A \to ε \end{matrix}

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

משפט שפה $L$ תקרא רגולרית אמ״מ קיים לה דקדוק רגולרי ימני או שמאלי המקבל אותה.