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

תכירו - מסלולי מוצקין. מסלול מוצקין מאורך \( n \) הוא מסלול ב-\( \mathbb{Z}^{2} \) שמתחיל ב-\( \left(0,0\right) \) ומסתיים ב-\( \left(n,0\right) \) ומורכב משלושה סוגים אפשריים של צעדים: ימינה, למעלה-ימינה ולמטה-ימינה. כלומר, אנחנו כרגע ב-\( \left(x,y\right) \) אז אנחנו יכולים לעבור אל \( \left(x+1,y+\delta\right) \) כאשר \( \delta\in\left\{ -1,0,1\right\} \). והנה העלילה מסתבכת: אסור למסלול לרדת מתחת לציר \( x \), דהיינו אם אנחנו ב-\( \left(x,0\right) \) אסור לנו לבצע צעד ימינה-למטה. אין עוד מגבלות, פרט למגבלה שאנחנו חייבים לסיים ב-\( \left(n,0\right) \).

בואו ניתן שמות לצעדים האפשריים: לימינה-למעלה אקרא U, לימינה למטה אקרא D ולסתם ימינה אקרא S (מלשון Up, Down, Stay שמתארים מה קורה מבחינת הגובה של המסלול). אם כן, מסלול מוצקין הוא סדרה מאורך \( n \) של התווים U,D,S שגם מקיימים עוד כמה כללים - כלומר, זו שפה פורמלית מעל הא”ב \( \Sigma=\left\{ \mbox{U, D, S}\right\} \). כך שאם לשניה פחדתם שאתם בפוסט הלא נכון - לא לדאוג, אנחנו עדיין מדברים על שפות פורמליות פה. ספציפית, על שפות חסרות הקשר, כי אני רוצה לטעון ששפת כל מסלולי מוצקין החוקיים היא שפה חסרת הקשר.

בואו נראה דוגמה למסלולים מאורך 3, חוקיים ולא חוקיים: מסלול חוקי פשוט הוא SSS שלא עולה למעלה ולא יורד למטה. עוד מסלול חוקי הוא USD שעולה, נשאר רגע למעלה ואז יורד. גם UDS (עולה, יורד, נשאר) הוא חוקי. לעומת זאת, USS לא חוקי כי הוא מסיים ב-\( \left(3,1\right) \); ו-DUS לא חוקי כי אחרי הצעד הראשון הוא יורד אל \( \left(1,-1\right) \); ו-UUD גם כן לא חוקי כי הוא מסיים שוב ב-\( \left(3,1\right) \). כבר מתעוררת מאליה השאלה - האם שפת מסלולי המוצקין היא שפה רגולרית? קל לראות שלא, כי היא בעצם כוללת בתוכה את \( \left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) בתור מין מקרה פרטי. פורמלית, קחו את כל המילים מהצורה \( \mbox{U}^{n} \); עבור כל זוג מילים כאלו, \( \mbox{U}^{k},\mbox{U}^{t} \) כך ש-\( k\ne t \) קל לראות ש-\( \mbox{U}^{k}\mbox{D}^{k} \) מגדירה מסלול מוצקין חוקי אבל \( \mbox{U}^{t}\mbox{D}^{k} \) לא, כך ש-\( \mbox{D}^{k} \) היא מה שקראתי לו מילה מפרידה בפוסט על משפט נרוד, שמוכיח שהשפה של מסלולי מוצקין אינה רגולרית.

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

בואו ניקח מסלול מוצקין כלשהו מאורך \( n \). האות הראשונה לא יכולה להיות \( \mbox{D} \) כי זה יוריד את המסלול אל \( \left(1,-1\right) \). לכן יש שתי אפשרויות. באפשרות הראשונה, המסלול מתחיל ב-\( \mbox{S} \). אם מנתקים את ה-\( \mbox{S} \) הזו מהמשך המסלול, המילה מאורך \( n-1 \) שנקבל תתאר מסלול מ-\( \left(1,0\right) \) אל \( \left(n,0\right) \) שמקיים את החוקיות של מסלולי מוצקין - דהיינו, היא תהווה מסלול מוצקין חוקי בעצמה. אז הנה כלל גזירה שמתאים לסיטואציה הזו: \( A\to\mbox{S}A \).

הסיטואציה האפשרית השניה היא זו שבה המסלול מתחיל ב-\( \mbox{U} \). כאן העסק קצת יותר טריקי. מכיוון שהמסלול הגיע אל \( \left(1,1\right) \) אחרי הצעד הראשון שלו, והוא מסיים ב-\( \left(n,0\right) \), חייב להיות צעד כלשהו במסלול (אולי האחרון) שבו יורדים לראשונה לגובה 0. הצעד הזה הוא כמובן D כי שאר הצעדים לא מורידים אותנו. בואו נסמן את המקום שבו הגענו לגובה 0 בתור \( \left(k,0\right) \). עכשיו, ראשית כל שימו לב לכך שהחל מ-\( \left(k,0\right) \) ועד ל-\( \left(n,0\right) \) יש לנו עוד מסלול מוצקין, מאורך \( n-k \) (אולי מאורך 0). וכמו כן, מה קורה בין צעד ה-U בהתחלה וצעד ה-D שמוריד אותנו ל-\( \left(k,0\right) \)? יש לנו מסלול שמתחיל מ-\( \left(1,1\right) \) ומסתיים ב-\( \left(k-1,1\right) \) (המקום שאליו הגענו צעד לפני ה-D). יתר על כן - המסלול הזה לא יורד מתחת לגובה 1, מכיוון ש-\( \left(k,0\right) \) הוא המקום הראשון שבו חזרנו לגובה 0 אחרי ההתחלה. מסקנה: המסלול מ-\( \left(1,1\right) \) עד ל-\( \left(k-1,1\right) \) הוא גם כן מסלול מוצקין חוקי, מאורך \( k-2 \). זה מוביל אותנו אל כלל הגזירה הבא: \( A\to\mbox{U}A\mbox{D}A \). האם ברור לכם למה הוא נכון?

כלומר, הדקדוק המלא שמייצר את כל מסלולי מוצקין האפשריים הוא \( A\to\mbox{U}A\mbox{D}A|\mbox{S}A|\varepsilon \). הנה למשל גזירה פשוטה עבור USD: \( A\Rightarrow\mbox{U}A\mbox{D}A\Rightarrow\mbox{U}\mbox{S}A\mbox{D}A\Rightarrow\mbox{USD}A\Rightarrow\mbox{USD} \).

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

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

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

הנה כמה עובדות שכן יהיו רלוונטיות לנו. אם \( f\left(x\right),g\left(x\right) \) הן פונקציות יוצרות שמתאימות לסדרות \( a_{n},b_{n} \) אז הפונקציה \( f\left(x\right)+g\left(x\right) \) מתאימה לסדרה \( a_{n}+b_{n} \). כמו כן, \( xf\left(x\right) \) מתאימה לסדרה שמתקבלת מ-\( a_{n} \) אחרי “הזזה” ימינה של כל האיברים ודחיפת 0 בהתחלה - פורמלית, \( c_{n}=a_{n-1} \) כאשר \( c_{0}=0 \). כמו כן, \( f\left(x\right)g\left(x\right) \) מתאימה לסדרה \( c_{n}=\sum_{k=0}^{n}a_{k}b_{n-k} \), שמתארת את מספר האפשרויות לבנות אובייקט מגודל \( n \) מתוך זוג של אובייקט מגודל \( k \) מתוך הסדרה הראשונה ואובייקט מגודל \( n-k \) מתוך הסדרה השניה, עבור כל \( 0\le k\le n \).

עכשיו, בואו ניקח את הדקדוק \( A\to\mbox{U}A\mbox{D}A|\mbox{S}A|\varepsilon \). מה שצריך להבין הוא שהדקדוק הזה בעצם מתאר לנו משוואה: אם נסמן ב-\( L_{A} \) את השפה שנוצרת על ידי המשתנה \( A \), אז הדקדוק אומר שמתקיים השוויון

\( L_{A}=\left\{ \mbox{U}\right\} \cdot L_{A}\cdot\left\{ \mbox{D}\right\} \cdot L_{A}\cup\left\{ \mbox{S}\right\} \cdot L_{A}\cup\left\{ \varepsilon\right\} \)

אני רוצה להפוך את המשוואה הזו למשוואה עבור פונקציות יוצרות. נסמן ב-\( f_{A}\left(x\right) \) את הפונקציה היוצרת של הסדרה \( a_{n}=\left|\left\{ w\in L_{A}\ |\ \left|w\right|=n\right\} \right| \). באופן דומה אפשר להגדיר פונקציה יוצרת לכל שפה שהיא. שימו לב גם לכך שהפונקציה היוצרת שמתאימה לשפה \( \left\{ \varepsilon\right\} \) היא 1 (כי יש לנו אובייקט אחד מגודל 0 בשפה, ו-0 אובייקטים מכל גודל אחר) והפונקציה היוצרת שמתאימה ל-\( \left\{ \mbox{U}\right\} \) היא \( x \) (אובייקט אחד מגודל 1 ו-0 מכל גודל אחר) וכך גם עבור \( \left\{ \mbox{S}\right\} \) ו-\( \left\{ \mbox{D}\right\} \).

עכשיו, נניח שיש לי שלוש שפות, \( L_{A}=L_{B}\cup L_{C} \), כך ש-\( L_{B}\cap L_{C}=\emptyset \) עם פונקציות יוצרות מתאימות \( f_{A},f_{B},f_{C} \). אני טוען ש-\( f_{A}=f_{B}+f_{C} \) מהסיבה שציינתי קודם (כי מספר האובייקטים מגודל \( n \) ב-\( L_{A} \) הוא בדיוק סכום מספרי האובייקטים מגודל זה ב-\( L_{B},L_{C} \)). קצת יותר טריקי לראות שאם \( L_{A}=L_{B}\cdot L_{C} \) אז \( f_{A}=f_{B}\cdot f_{C} \), אבל גם זה נובע ממה שאמרתי קודם (חשבו על זה קצת אם אתם לא משוכנעים). השתכנעתם בשני אלו? יופי, אז בואו נחזור למשוואה שלנו:

\( L_{A}=\left\{ \mbox{U}\right\} \cdot L_{A}\cdot\left\{ \mbox{D}\right\} \cdot L_{A}\cup\left\{ \mbox{S}\right\} \cdot L_{A}\cup\left\{ \varepsilon\right\} \)

אם נתרגם אותה לפונקציות יוצרות ונשתמש בכללים שקיבלנו, הרי שנקבל

\( f_{A}=x\cdot f_{A}\cdot x\cdot f_{A}+x\cdot f_{A}+1=x^{2}f_{A}^{2}+xf_{A}+1 \)

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

\( f_{A}=\frac{1-x-\sqrt{\left(x-1\right)^{2}-4x^{2}}}{2x^{2}}=\frac{1-x-\sqrt{1-2x-3x^{2}}}{2x^{2}} \)

נוסחת השורשים מניבה שני פתרונות, וכאן לקחתי רק אחד - זה לא פוסט על קומבינטוריקה אז לא אסביר את השיקולים שבגללם יודעים שהפתרון שלקחתי הוא הנכון; זה מופיע בפוסט על פונקציות יוצרות ומסלולי מוצקין שקישרתי אליו. כאן מסלולי מוצקין מופיעים רק בתור דוגמה. הפואנטה היא שונה לחלוטין: התהליך שבו קיבלתי את הפונקציה היוצרת של \( L_{A} \) היה כמעט מכני: בהינתן הדקדוק שמייצר את \( L_{A} \), קיבלתי ממנו באופן אוטומטי לגמרי משוואה עבור \( f_{A} \). כדי לחלץ ממנה את \( f_{A} \) השתמשתי בידע כללי שיש לי על פתרון משוואות פונקציונליות שכאלו; לא תמיד אפשר לפתור את המשוואה בצורה נחמדה שכזו, אבל לפעמים כבר מערכת המשוואות עצמה היא מועילה.

בואו נראה עוד דוגמאות כדי להבין עד כמה חזק הכלי שכרגע קיבלנו. נתחיל מ-\( L=\left\{ a^{n}b^{n}\ |\ n\ge0\right\} \) ידידתנו משכבר הימים. זו שפה שלכל \( n \) זוגי יש בה בדיוק מילה אחת מאורך זה, ולכל \( n \) אי זוגי יש בה 0 איברים מאורך זה. הפונקציה היוצרת באה מאליה: הדקדוק הוא \( S\to aSb|\varepsilon \) ולכן המשוואה היא \( f=x^{2}f+1 \), ואחרי חילוץ נקבל \( f=\frac{1}{1-x^{2}}=\sum x^{2n} \) - בדיוק מה שהיינו אמורים לקבל. כמובן, זו בכל מקרה שפה פשוטה כי “קל לראות” מההגדרה שלה את העניין הזה של הזוגיים והאי זוגיים, אבל צריך להבין שאם השפה הזו נתונה למחשב, אז הייצוג שהמחשב הולך לקבל ככל הנראה יהיה הדקדוק, כי זה הייצוג הכי פשוט של השפה, ומהייצוג הזה הוא יכול להסיק את הפונקציה היוצרת (ובמקרה הזה, את מספר האיברים המפורש לכל \( n \)) בקלות.

עוד דוגמה - מספרי קטלן. סדרת המספרים הזו היא פתרון לשלל בעיות ספירה מעניינות שלא נראות קשורות במבט ראשון. אציג כאן שתיים מהן - ראשית, מספר קטלן \( C_{n} \) הוא מספר הסדרות מאורך \( 2n \) שמורכבות מסוגריים ימניים ושמאליים, כך שסדרת הסוגריים היא “חוקית” - מה שאומר שאם קוראים את המילה משמאל לימין אין רגע שבו מספר הסוגריים השמאליים גדול ממספר הסוגריים הימניים, ושבסוף המילה מספר הסוגריים משני הסוגים מתאזן. תחשבו על זה שניה ותבינו למה זה בדיוק אותו דבר כמו מספר המסלולים מ-\( \left(0,0\right) \) אל \( \left(2n,0\right) \) עם צעדי U ו-D אבל בלי צעדי S הפעם, כך שלא יורדים מתחת לציר \( x \) (כלומר - זה דומה למסלולי מוצקין אבל זה לא באמת אותו דבר). דקדוק עבור השפה הזו נובע כמעט מאליו: \( A\to\mbox{U}A\mbox{D}A|\varepsilon \). ומכאן המשוואה \( f=x^{2}f^{2}+1 \) והפונקציה היוצרת \( f\left(x\right)=\frac{1-\sqrt{1-4x^{2}}}{2x^{2}} \). אבל רגע, זהירות, זו לא הפונקציה היוצרת של מספרי קטלן, כי \( C_{n} \) מיוצג על ידי סדרה מאורך \( 2n \). כדי לפתור את הבעיה הזו, אנחנו “מוציאים שורש”. פורמלית, אם \( f\left(x\right)=\sum_{n=0}^{\infty}a_{2n}x^{2n} \) (כלומר, מספר האיברים מגודל אי זוגי הוא תמיד אפס), אז אפשר להגדיר סדרה חדשה \( c_{n}=a_{2n} \) עם פונקציה יוצרת \( g\left(x\right)=\sum c_{n}x^{n} \) ונקבל ש-\( g\left(x^{2}\right)=f\left(x\right) \). לכן אם \( g\left(x^{2}\right)=\frac{1-\sqrt{1-4x^{2}}}{2x^{2}} \) קיבלנו שהפונקציה היוצרת של מספרי קטלן היא \( g\left(x\right)=\frac{1-\sqrt{1-4x}}{2x} \) (לא הבנתם את התעלולים הללו? לא נורא, זו לא מטרת הפוסט).

עכשיו, אחרי שנהנינו קצת, הגיע הזמן לחשוף את האמת המכוערת - אני קצת משקר לכם. בואו ניקח דקדוק אחר עבור \( \left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) כדי לראות את זה: \( S\to aSb|aaSbb|\varepsilon \). מה עשינו כאן? כמעט שום דבר - פשוט אפשרנו ל-\( S \) לקצר עניינים וליצור יותר תווים בגזירה אחת. זה הופך את הדקדוק שלנו לרב משמעי, כי הנה למשל שתי גזירות שונות מהותית של \( aabb \): \( S\Rightarrow aaSbb\Rightarrow aabb \) ו-\( S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb \).

אם ננסה להפעיל את השיטה שראינו על הדקדוק הזה, נקבל כמובן \( f=1+x^{2}f+x^{4}f \) שמוביל אותנו אל \( f=\frac{1}{1-x^{2}-x^{4}} \) - וזו פונקציה שונה מ-\( \frac{1}{1-x^{2}} \). מה קרה? ההנחה הסמויה שלי הייתה שהדקדוק שלי הוא חד משמעי. אחרת, משוואה כמו \( L=aLb\cup aaLbb\cup\left\{ \varepsilon\right\} \) כבר לא ניתנת לתרגום ישיר לפונקציות יוצרות כי האיחוד הראשון בה איננו איחוד זר. אני לא אוכיח כאן שאם הדקדוק חד משמעי אז לא יכולה להיווצר בעיה עם השיטה, אבל זה נכון. כמובן, להוכיח שדקדוק הוא חד משמעי זה לאו דווקא טריוויאלי וזה מקטין את השימושיות של השיטה.

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

בפוסט הקודם אמרתי שאם יש לנו אוטומט סופי דטרמיניסטי \( A \), אז אפשר לבנות דקדוק עבור השפה שלו. הרעיון היה להתאים משתנה דקדוקי לכל מצב של האוטומט, ואת הגזירה \( q\to\sigma p \) אם באוטומט יש את המעבר \( \delta\left(q,\sigma\right)=p \). וכמו כן את הגזירה \( q\to\varepsilon \) אם \( q\in F \). עכשיו, הדקדוק הזה הוא כן חד משמעי, וזה נובע מכך ש-\( A \) דטרמיניסטי; אם אתם לא משוכנעים, נסו לחשוב איך ייראו שתי גזירות שונות לאותה מילה - קל לראות שברגע שבו הן מתחילות “להתנהג שונה” הן גם יהיו חייבות ליצור אותיות שונות, ולכן מילים שונות.

עכשיו, בדקדוק שלנו יש הרבה משתנים, ולכן אנחנו לא מקבלים משוואה אחת; אנחנו מקבלים מערכת משוואות. אבל משוואות פשוטות במיוחד - לינאריות: לכל מצב \( q \) תהיה לנו משוואה מהצורה

\( f_{q}=\sum_{p}a_{p}^{q}xf_{p}+\delta_{q} \)

כאשר \( a_{p}^{q} \) הוא מספר המעברים מ-\( q \) אל \( p \) - פורמלית, \( a_{p}^{q}=\left|\left\{ \sigma\in\Sigma\ |\ \delta\left(q,\sigma\right)=p\right\} \right| \). כמו כן, \( \delta_{q}=\begin{cases}1 & q\in F\\0 & q\notin F\end{cases} \). למה המשוואה הזו נכונה? אין כאן שום דבר חדש, זו הפעלה של הכללים שכבר ראינו.

מה שיפה במשוואה הזו היא שמדובר על משוואה לינארית - אין ל-\( f \)-ים חזקות גבוהות שם. זה מאפשר לנו להשתמש בעולם המושגים של האלגברה הלינארית: נגדיר מטריצה \( A \) כך ש-\( A_{qp}=a_{p}^{q} \) ונגדיר וקטורים \( \overline{f},\overline{\delta} \) שמייצגים את ה-\( f_{q} \) וה-\( \delta_{q} \)-ים, וקיבלנו שאפשר לכתוב את מערכת המשוואות כולה במשוואה קומפקטית אחת:

\( \overline{f}=xA\cdot\overline{f}+\overline{\delta} \)

ואחרי חילוץ של \( \overline{f} \):

\( \overline{f}=\left(I-xA\right)^{-1}\overline{\delta} \)

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

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