משתמש:חישוביות/HW1

תורת החישוביות – 236343 – תרגיל בית 1

1. לא הגדרנו בהרצאה ובתרגול מה בדיוק התוצאה של נסיון ליפול מהסרט (בזה תלויה הפונקציה המחושבת ע"י מ"ט כזאת שמנסה ליפול מהסרט). נניח שאחרי הקונפ' $(\alpha ,q,0)$ ו-$\delta (q,\alpha _{0})=(q',\sigma ,L)$ המכונה עוברת לקונפ' $(q',\sigma \cdot \alpha _{1...},0)$ (כלומר, הראש נשאר במקום). זאת אומרת שבמקום הנסיון ליפול מהסרט היינו יכולים להשאיר את הראש במקום, בתנאי שנדע שמיקום הראש הינו בקצה הסרט. בשביל זה נוסיף ל-$\Gamma$ את האותיות המיוחדות שיופיעו רק בקצה הסרט, ורק הן יופיעו שם. בכך נחליף את $\Gamma$ ב-$\Gamma '=\Gamma \cup (\Gamma \times \{L\})$ (לסימון Left). נוסיף מצב חדש כדי להכניס משמאל אות חדשה מאלה שהוספנו: $Q'=Q\cup \{q'_{0}\}$. החלפנו את $M=(Q,q_{0},F,\Gamma ,\Sigma ,\flat ,\delta )$ ב-$M'=(Q',q'_{0},F,\Gamma ',\Sigma ,\flat ,\delta ')$, ופונקצית המעברים מוגדרת כלהלן:

$\delta '(q',\sigma ')={\begin{cases}\delta (q',\sigma '),&q'\in Q,\sigma '\in \Gamma \\(q_{1},(\sigma _{1},L),R),&\delta (q',\sigma )=(q_{1},\sigma _{1},R),q'\in Q,\sigma '=(\sigma ,L),\sigma \in \Gamma \\(q_{1},(\sigma _{1},L),S),&\delta (q',\sigma )=(q_{1},\sigma _{1},x),q'\in Q,x\in \{L,S\},\sigma '=(\sigma ,L),\sigma \in \Gamma \\(q_{0},(\sigma ',L),S),&q'=q'_{0}\end{cases}}$

המכונה החדשה לא תנסה ליפול מהסרט, ולכל קלט תיצור אותו פלט אלא האות השמאלית שלו תהיה $(\alpha _{0},L)$ במקום $\alpha _{0}$. נוסיף למכונה עוד אות מיוחדת אחת לסימון סוף הפלט, ועוד מצבים אחרי המצבים הסופיים שיגרמו לראש מה"ט ללכת שמאלה עד הקצה, להחליף את האות השמאלית באות רגילה, וללכת חזרה ימינה עד סוף הפלט המסומן: $\Gamma ''=\Gamma '\cup \{\$\},Q''=Q'\cup \{q_{L},q_{R},q_{f}\},F''=\{q_{f}\}$, ופונקצית המעברים מוגדרת כלהלן:

$\delta ''(q'',\sigma '')={\begin{cases}\delta '(q'',\sigma ''),&q''\in Q'\setminus F,\sigma ''\in \Gamma '\\(q_{L},\$,L),&q''\in F\\(q_{L},\sigma '',L),&q''=q_{L},\sigma ''\in \Gamma \\(q_{R},\sigma ,R),&q''=q_{L},\sigma ''=(\sigma ,L),\sigma \in \Gamma \\(q_{R},\sigma '',R),&q''=q_{R},\sigma ''\in \Gamma \\(q_{f},\flat ,S),&q''=q_{R},\sigma ''=\$\end{cases}}$

בנינו את המכונה הנדרשת $M''=(Q\cup \{q'_{0},q_{L},q_{R},q_{f}\},q'_{0},\{q_{f}\},\Gamma \cup (\Gamma \times \{L\})\cup \{\$\},\Sigma ,\flat ,\delta '')$ ותפקיד המצבים החדשים הוא: $q'_{0}$ – לסמן את האות השמאלית ולהתחיל את החישוב; $F$ – לסמן את סוף הפלט ולהתחיל ללכת שמאלה עד הקצה; $q_{L}$ – ללכת שמאלה עד הקצה ולהסיר סימון מהאות השמאלית; $q_{R}$ – ללכת ימינה עד סימן סוף הפלט, למחוק את הסימן, לעצור.

הגדרת פונקצית המעברים:

$\delta ''(q'',\sigma '')={\begin{cases}\delta (q'',\sigma ''),&q''\in Q\setminus F,\sigma ''\in \Gamma \\(q_{1},(\sigma _{1},L),R),&\delta (q'',\sigma )=(q_{1},\sigma _{1},R),q''\in Q\setminus F,\sigma ''=(\sigma ,L),\sigma \in \Gamma \\(q_{1},(\sigma _{1},L),S),&\delta (q'',\sigma )=(q_{1},\sigma _{1},x),q''\in Q\setminus F,x\in \{L,S\},\sigma ''=(\sigma ,L),\sigma \in \Gamma \\(q_{0},(\sigma '',L),S),&q''=q'_{0}\\(q_{L},\$,L),&q''\in F\\(q_{L},\sigma '',L),&q''=q_{L},\sigma ''\in \Gamma \\(q_{R},\sigma ,R),&q''=q_{L},\sigma ''=(\sigma ,L),\sigma \in \Gamma \\(q_{R},\sigma '',R),&q''=q_{R},\sigma ''\in \Gamma \\(q_{f},\flat ,S),&q''=q_{R},\sigma ''=\$\end{cases}}$

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

$Q=\{q_{0},q_{SR}^{0},q_{SR}^{1},q_{SR}^{0+},q_{00},q_{SUB},q_{SBB},q_{R},q_{f}\}$

$F=\{q_{f}\},\Sigma =\{0,1\},\Gamma =\{0,1,\flat ,\$\}$

טבלת המעברים:

$\delta$	0	1	$\flat$	$	תיאור
$q_{0}$	$q_{SR}^{0},\$,R$	$q_{SR}^{1},\$,R$	$q_{f},\flat ,R$	---	סימון הקצה השמאלי ב-$
$q_{SR}^{0}$	$q_{SR}^{0},0,R$	$q_{SR}^{1},0,R$	$q_{00},\flat ,L$	---	הזזת 0 ימינה (לא ראינו 1-ים בקלט)
$q_{SR}^{1}$	$q_{SR}^{0+},1,R$	$q_{SR}^{1},1,R$	$q_{SUB},1,R$	---	הזזת 1 ימינה
$q_{SR}^{0+}$	$q_{SR}^{0+},0,R$	$q_{SR}^{1},0,R$	$q_{SUB},0,R$	---	הזזת 0 ימינה (ראינו 1-ים בקלט)
$q_{00}$	$q_{00},\flat ,L$	$q_{00},\flat ,L$	---	$q_{f},\flat ,S$	מחיקת הסרט ומעבר שמאלה עד הקצה (קלט אפסי, פלט ריק)
$q_{SUB}$	$q_{SUB},0,L$	$q_{SUB},1,L$	$q_{SBB},1,L$	$q_{R},0,R$	החסרה ללא הלוואה
$q_{SBB}$	$q_{SBB},1,L$	$q_{SUB},0,L$	---	---	החסרה עם הלוואה
$q_{R}$	$q_{R},0,R$	$q_{R},1,R$	$q_{f},\flat ,S$	---	מעבר ימינה עד סוף הפלט המופק

3. המודל בגיל העמידה שקול למודל הסטנדרטי. ברור איך לסמלץ מכונה סטנדרטי במכונת המודל החדש: נחליף את המצבים הסופיים בלולאות אינסופיות $\delta (q_{f},\sigma )=(q_{f},\sigma ,S)$. לסימולציה בכיוון השני נצטרך לגלות לולאות אינסופיות שמהוות עמידה. אחרי שהמכונה נעמדת, משתנים רק מיקום ראשה והאות בתא שעליה הראש מצביע, זה אומר שלאחר ככל היותר $N=\|\Gamma \|\cdot \|Q\|$ צעדים הקונפיגורציה תחזור על עצמה. אז עם הראש נשאר באותו מקום $N$ צעדים ברציפות, נדע בוודאות שהקונפיגורציות הולכות בלולאה, ולפיכך המכונה כבר נעמדה. נצטייד במכונה עם שני סרטים, שכבר יודעים על שקילותה למודל הסטנדרטי, ונקח בתור הא"בים של הסרטים את $\Gamma _{1}=\Gamma ,\Sigma _{1}=\Sigma ,\Gamma _{2}=\{0,1,...,N\},\Sigma _{2}=\{\},\flat _{2}=0$. בסרט השני נמדוד כמה צעדים הראש נשאר באותו מקום. (הראש יהיה באותו מיקום בשני הסרטים, כאילו זה סרט אחד עם שני נתיבים.) נגדיר את פונקצית המעברים כלהלן:

$\delta '(q,\sigma _{1},\sigma _{2})={\begin{cases}(q_{1},\sigma '_{1},0,x)&\delta (q,\sigma _{1})=(q_{1},\sigma '_{1},x),x\in \{L,R\}\\(q_{1},\sigma '_{1},\sigma _{2}+1,S)&\delta (q,\sigma _{1})=(q_{1},\sigma '_{1},S),\sigma _{2}<N\\(q_{f},\sigma '_{1},N,S)&\delta (q,\sigma _{1})=(q_{1},\sigma '_{1},S),\sigma _{2}=N\end{cases}}$ ,כש-$q_{f}$ הינו המצב הסופי היחיד שנוסיף למצבים המקוריים.

המכונה החדשה $(Q\cup q_{f},q_{0},\{q_{f}\},\Gamma ,\Sigma ,\flat ,\{0,1,...,\|\Gamma \|\cdot \|Q\|\},\{\},0,\delta ')$ תחשב את אותה פונקציה כמו המכונה המקורית.

4. המכונה שנבנה פשוט תרשום על גבי הסרט את המילה $\epsilon$ ואז תפעיל את המכונה המקורית. נניח ש-$\epsilon =\epsilon _{1}\epsilon _{2}...\epsilon _{n}$

$\Gamma '=\Gamma \cup \{\$\},Q'=Q\cup \{q'_{0},q_{1},...,q_{n},q_{n+1}\}$

המכונה תתחיל מלסמן את הקצה השמאלי של הסרט ב-$, אח"כ תרשום את $\epsilon$ מאות השניה ימינה עד הסוף, אח"כ תסמן את סוף הקלט ב-$\flat$, ולבסוף תחזיר את ראש שמאלה עד הקצה, תרשום את האות הראשונה של $\epsilon$ במקום $, ותפעיל את החישוב המקורי. במצב $q_{k}$ המכונה תרשום את האות ה-$k$ של $\epsilon$.

המכונה תהיה $(Q',q'_{0},F,\Gamma ',\Sigma ,\flat ,\delta ')$ כש-$\delta '$ נגדרת כלהלן:

$\delta '(q',\sigma ')={\begin{cases}(q_{2},\$,R)&q'=q'_{0}\\(q_{k+1},\epsilon _{k},R)&q'\in \{q_{2},q_{3},...,q_{n}\}\\(q_{1},\flat ,L)&q'=q_{n+1}\\(q_{1},\sigma ',L)&q'=q_{1},\sigma '\not =\$\\(q_{0},\epsilon _{1},S)&q'=q_{1},\sigma '=\$\\\delta (q',\sigma ')&q'\in Q,\sigma '\in \Gamma \end{cases}}$