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

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

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

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

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

האבחנה הבסיסית בכל הסיפור הזה היא פשוטה ביותר. מספר המסלולים מאורך \( n \) שמובילים מ-\( q_{i} \) אל מצב מקבל כלשהו ניתן לחישוב באופן רקורסיבי. אם \( n=0 \) אז הוא 1 אם \( q_{i} \) הוא בעצמו מצב מקבל ואחרת הוא 0. אפשר לסמן זאת בקומפקטיות באמצעות וקטור: \( \overline{u} \)יהיה וקטור שבכניסה ה-\( i \) שלו יש 1 אם המצב \( q_{i} \) הוא מקבל, ואחרת 0. אם \( n>0 \) אז אפשר להפעיל רקורסיה: לכל מצב \( q_{j} \) אפשר לדבר על “מספר המסלולים מאורך \( n \) מ-\( q_{i} \) למצב מקבל, שבצעד הראשון נכנסים ל-\( q_{j} \)”. מספר המסלולים הללו הוא בדיוק המכפלה של מספר האפשרויות לעבור מ-\( q_{i} \) אל \( q_{j} \) (כלומר, \( T_{ij} \)) במספר המסלולים מאורך \( n-1 \) מ-\( q_{j} \) שמגיעים למצב מקבל. מכיוון שכל מסלול מ-\( q_{i} \) שמגיע למצב מקבל חייב לעבור דרך \( q_{j} \) כלשהו בצעד הראשון, מספר המסלולים הכולל הוא סכום של המכפלות הללו, עבור כל ה-\( j \)-ים האפשריים. מי שבקיא באלגברה לינארית אולי רואה כבר כפל מטריצות מול העיניים, אז אכתוב במפורש את הנוסחה: \( 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) \)

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

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

\( \overline{f} = u+T\cdot x\overline{f} \)

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

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

ומכאן:

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

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

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

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