אז מה הקשר בין אוטומטים ופונקציות יוצרות?

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

ובכן, אם יש לנו שפה רגולרית $latex L$, אפשר לשכוח מהמבנה הפנימי העשיר שלה ולהתמקד בשאלה כמותית - כמה מילים יש מכל אורך? נסמן ב-$latex a_{n}$ את מספר המילים ב-$latex L$ מאורך $latex n$. אפשר כעת להתאים ל-$latex L$ פונקציה יוצרת $latex f_{L}\left(x\right)$ שמתארת את הסדרה $latex a_{n}$ (למי שתוהה, יש מילה אחת מאורך 0 - “המילה הריקה”, כך ש-$latex a_{0}$ יכול להיות שווה 1). כל זה טוב ויפה - כעת השאלה היא כיצד ניתן לחשב את $latex f_{L}\left(x\right)$. אציג שיטה כללית לעשות זאת, אם נתון אוטומט $latex A$ שמקבל את $latex L$; זה מכתיב דרך פעולה כללית בהתמודדות עם בעיה קומבינטורית שאנחנו רוצים למצוא עבורה פונקציה יוצרת - קודם כל לבדוק האם הבעיה הזו ניתנת לניסוח בתור שפה רגולרית. אם כן, קיבלנו את הפונקציה היוצרת “בחינם”.

מכיוון שאנחנו מתמקדים בשאלה כמותית ולא במבנה של כל מילה, אפשר להתעלם מההבדלים שבין אותיות שונות, ולהתמקד בשאלה יותר פשוטה הנוגעת לאוטומט - בכמה מסלולים שונים מאורך $latex n$ אפשר להגיע מהמצב ההתחלתי למצב המקבל? מספר המסלולים הזה הוא בדיוק $latex a_{n}$. עם זאת, כפי שקורה בדרך כלל בהוכחות שעוסקות באוטומטים, צריך לשאול שאלה “חזקה” יותר - נניח שאנחנו מתחילים ממצב כלשהו של האוטומט, לאו דווקא המצב ההתחלתי. כמה מסלולים מאורך $latex n$ שמגיעים למצב מקבל יהיו כעת? אם $latex q_{i}$ הוא המצב הזה, אפשר לסמן את המספר בתור $latex a_{n}^{i}$, ואת הפונקציה היוצרת המתאימה בתור $latex f_{i}\left(x\right)$. כדי לפשט עוד יותר את הסימונים אפשר לדבר על וקטור של פונקציות יוצרות: $latex \overline{f}=\left(f_{0},f_{2},\dots,f_{k}\right)$ (אני מסמן את מספר המצבים הכולל של האוטומט ב-$latex k+1$ כדי שהוקטור יראה “נחמד”).

מכיוון שויתרנו על זהות האותיות השונות ואנחנו מתמקדים רק במספר הדרכים להגיע ממצב אחד באוטומט לאחר, אפשר להפסיק לדבר על פונקצית המעברים של האוטומט ולהסתפק במעין טבלת מעברים מופשטת - מטריצה מגודל $latex \left(k+1\right)\times\left(k+1\right)$ שהן שורותיה והן עמודותיה מייצגות מצבים, ובתא ה-$latex \left(i,j\right)$ שלה כתוב מספר הדרכים לעבור מהמצב $latex q_{i}$ למצב $latex q_{j}$ (בצורה אולטרה פורמלית, זהו $latex \left|\left\{ \sigma\in\Sigma:\delta\left(q_{i},\sigma\right)=q_{j}\right\} \right|$). דרך הייצוג הזו, של גרף באמצעות מטריצה, היא מאוד, מאוד נפוצה. אקרא למטריצה הזו $latex T$. אלו שבקיאים באלגברה לינארית ומכירים כפל מטריצות יכולים לוודא לעצמם ש-$latex T^{r}$ היא המטריצה שבכניסה $latex \left(i,j\right)$ שלה רשום מספר הדרכים להגיע מ-$latex i$ אל $latex j$ בדיוק ב-$latex r$ צעדים.

האבחנה הבסיסית בכל הסיפור הזה היא פשוטה ביותר. מספר המסלולים מאורך $latex n$ שמובילים מ-$latex q_{i}$ אל מצב מקבל כלשהו ניתן לחישוב באופן רקורסיבי. אם $latex n=0$ אז הוא 1 אם $latex q_{i}$ הוא בעצמו מצב מקבל ואחרת הוא 0. אפשר לסמן זאת בקומפקטיות באמצעות וקטור: $latex \overline{u}$יהיה וקטור שבכניסה ה-$latex i$ שלו יש 1 אם המצב $latex q_{i}$ הוא מקבל, ואחרת 0. אם $latex n>0$ אז אפשר להפעיל רקורסיה: לכל מצב $latex q_{j}$ אפשר לדבר על “מספר המסלולים מאורך $latex n$ מ-$latex q_{i}$ למצב מקבל, שבצעד הראשון נכנסים ל-$latex q_{j}$”. מספר המסלולים הללו הוא בדיוק המכפלה של מספר האפשרויות לעבור מ-$latex q_{i}$ אל $latex q_{j}$ (כלומר, $latex T_{ij}$) במספר המסלולים מאורך $latex n-1$ מ-$latex q_{j}$ שמגיעים למצב מקבל. מכיוון שכל מסלול מ-$latex q_{i}$ שמגיע למצב מקבל חייב לעבור דרך $latex q_{j}$ כלשהו בצעד הראשון, מספר המסלולים הכולל הוא סכום של המכפלות הללו, עבור כל ה-$latex j$-ים האפשריים. מי שבקיא באלגברה לינארית אולי רואה כבר כפל מטריצות מול העיניים, אז אכתוב במפורש את הנוסחה: $latex f_{i}\left(x\right) = u_{i}+\sum_{j}T_{ij}\cdot xf_{j}\left(x\right)=u_{i}+\left[T\right]_{i}\cdot x\overline{f}\left(x\right)$

ההכפלה ב-$latex x$ של $latex f_{j}\left(x\right)$ היא הדרך שלנו לבטא את העובדה שמסלול מאורך $latex n$ של $latex f_{i}$ נבנה באמצעות מסלולים מאורך $latex n-1$ של אגף ימין. ה-$latex u_{i}$ שמתווסף לסכום בא לתאר בדיוק את תנאי העצירה של הרקורסיה (הוא יהיה המקדם החופשי בטור של $latex f_{i}\left(x\right)$).

המשוואה שלמעלה היא משוואה כללית לכל $latex i$; היא בעצם מייצגת מערכת של $latex k+1$ משוואות. את כל המערכת הזו אפשר לתאר באופן עוד יותר קומפקטי:

$latex \overline{f} = u+T\cdot x\overline{f}$

ועל ידי העברת אגף מקבלים:

$latex \overline{f}\left(I-xT\right) = u$

ומכאן:

$latex \overline{f} = \left(I-xT\right)^{-1}u$

וזה נותן לנו את וקטור הפונקציות היוצרות עבור כל המצבים. אם רוצים “לבודד” את הפונקציה היוצרת רק עבור המצב $latex q_{0}$, צריך לכפול את שני האגפים בוקטור $latex \left(1,0,0,\dots,0\right)$ (הוקטור שכולו אפסים פרט לכניסה במקום ה-0). נסמן וקטור זה כ-$latex v$, ונקבל ש-$latex f_{0}\left(x\right)=v\left(I-xT\right)^{-1}u$. זו הנוסחה.

חישוב של כל העסק הזה הוא לא מסובך, בהינתן שאנחנו כבר יודעים לעשות חשבון עם פולינומים. יש מערכות אלגברה ממוחשבות שעושות את זה בדיוק - אני משתמש ב-Sage לצורך כך, ובה החישוב שלעיל הוא מיידי. התוצאה המתקבלת היא תמיד פונקציה רציונלית (מנה של שני פולינומים), כך שמציאת נקודות הסינגולריות שלה (הנקודות שבהן “משהו מתקלקל” ולכן אפשר ללמוד מהן על קצב הגידול של $latex a_{n}$) היא פשוטה למדי (אלו בדיוק הנקודות שמאפסות את המכנה).

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


נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ:

Buy Me a Coffee at ko-fi.com