בעיות הכרעה עבור שפות פורמליות

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

נניח ש-\( L \) היא שפה פורמלית כלשהי (רגולרית או חסרת הקשר), אז הנה דברים שמעניין אותנו לדעת. האם \( L \) ריקה? האם \( L \) אינסופית? האם מילה \( w \) ספציפית שייכת ל-\( L \)? ונניח שנתונה שפה גם \( L^{\prime} \), האם \( L=L^{\prime} \)?

לפני שניגשים לפתור את הבעיות הללו צריך להבין איך \( L \) נתונה לנו בכלל. קלטים, במחשב, הם בסך הכל סדרה סופית של ביטים, שאנחנו מפענחים בצורה מסויימת. אנחנו צריכים ייצוג שהמחשב יודע לעבוד איתו, ולכן ייצוג של שפה באמצעות תיאור מילולי לא פורמלי (“\( L \) היא שפת כל המילים מאורך זוגי מעל \( \left\{ a,b\right\} \)”) יהיה משהו שלמחשב יהיה קשה מאוד לעבוד איתו. אז בדרך כלל אנחנו מניחים שאם \( L \) רגולרית היא נתונה לנו בעזרת אוטומט סופי \( A \) (שמיוצג באופן דומה לזה שמייצגים בו גרף במחשב), ואם היא חסרת הקשר היא נתונה בעזרת דקדוק חסר הקשר \( G \). אפשר כמובן גם להציע דרכי תיאור אחרות, למשל ביטוי רגולרי; אבל אנחנו יודעים שאפשר להמיר כל ביטוי רגולרי לאוטומט מתאים, אז על פניו אנחנו לא מגבילים את הכלליות (כמובן שיש שאלה של סיבוכיות ההמרה של הביטוי הרגולרי לאוטומט וכדומה אבל לא אכנס לזה הפעם).

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

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

אוקיי, בואו נעבור עכשיו לפתרון בעיות.

אם \( A \) הוא אוטומט סופי דטרמיניסטי ונתונה לנו מילה כלשהי \( w \), אז אין דבר קל יותר מלבדוק אם \( w\in L\left(A\right) \): פשוט מבצעים סימולציה של ריצת \( A \) על \( w \) ובודקים אם הגענו למצב מקבל. אם \( A \) אינו דטרמיניסטי אפשר לבצע לו דטרמיניזציה (להמיר אותו לאוטומט דטרמיניסטי; אדבר בפוסט אחר על איך עושים את זה יעיל יחסית), אבל גם אפשר להריץ אותו כמו שהוא על המילה, כשבמקום לזכור את המצב שבו אנחנו נמצאים כרגע, אנחנו זוכרים את קבוצת המצבים שבהם אנחנו נמצאים כרגע בכל הריצות האפשריות של האוטומט. כבר דיברתי על זה בשעתו.

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

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

ומה קורה בדקדוקים? המצב לא שונה בהרבה. האתגר פה הוא למצוא משתנים טרמינליים - משתנים שגוזרים מילה טרמינלית. למשתנים כאלו יש הגדרה רקורסיבית פשוטה: \( A \) הוא טרמינלי אם קיים כלל גזירה \( A\to\alpha \) כך ש-\( \alpha \) מורכבת כולה מטרמינלים וממשתנים טרמינליים. הגדרה כזו נותנת לנו מייד אלגוריתם איטרטיבי למציאת כל המשתנים הטרמינליים: מתחזקים קבוצה \( X \) של משתנים טרמינליים, שבהתחלה היא ריקה; בכל איטרציה עוברים על כל הגזירות \( A\to\alpha \) בדקדוק ובודקים אם \( \alpha\in\left(X\cup T\right)^{*} \). אם כן, מוסיפים את \( A \) ל-\( X \). ממשיכים כך עד שמגיעים לאיטרציה שבה לא התווסף כלום ל-\( X \), ואז מסיימים. עכשיו, כדי לבדוק אם שפת הדקדוק ריקה, פשוט בודקים אם \( S \) טרמינלי או לא.

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

עבור דקדוקים חסרי הקשר הסיטואציה דומה, אבל צריך להיות קצת יותר זהירים. אנחנו עדיין רוצים, באופן בסיסי, לחפש מעגל בגרף. נבנה גרף שצמתיו הם המשתנים של הדקדוק ויש קשת מ-\( A \) אל \( B \) אם קיימת בדקדוק גזירה \( A\to\alpha B\beta \). מעגל בגרף הזה פירושו שיש לנו משתנה שגוזר את עצמו: \( A\Rightarrow^{*}\gamma A\delta \). אבל גם אם מצאנו סיטואציה כזו, זה עדיין לא מבטיח לנו אינסוף מילים בשפה - אנחנו צריכים לדעת ש-\( A \) מסוגל לגזור מילה טרמינלית (אחרת חישוב ש-\( A \) משתתף בו לא הולך לייצר מילים בכלל), וש-\( \left|\gamma\delta\right|\ge1 \) (אחרת \( A \) עשוי לגזור את עצמו שוב ושוב, אבל זה החישוב איתו ייצר רק מילה אחת). כדי להבטיח את אלו, אנחנו מראש מבטיחים שהדקדוק שלנו הוא “נקי” - מעיפים ממנו משתנים טרמינליים, וגם מסלקים ממנו כללי יחידה כמו \( A\to B \) וכללים מהצורה \( A\to\varepsilon \), כך שאנו מבטיחים שכל גזירה \( A\to\alpha B\beta \) היא כזו שגם מייצרת מסביב ל-\( B \) משהו שהולך להפוך לטרמינלים בסופו של דבר. זו המחשה טובה לכך שנוח הרבה יותר להפעיל אלגוריתמים אם אפשר להניח שהדקדוק שפועלים עליו עבר פישוט מתאים.

בואו נעבור עכשיו למי שהיא אולי הבעיה המרתקת ביותר מבין כל בעיות ההכרעה שאדבר עליהן בפוסט הזה - בעיית השקילות. נתונים שני אוטומטים \( A_{1},A_{2} \) ואנחנו רוצים לדעת האם \( L\left(A_{1}\right)=L\left(A_{2}\right) \). זה לחלוטין לא טריוויאלי. חשבו על סיטואציה שבה אנחנו רוצים לבנות רכיב חומרה; מצד אחד, יש לנו מודל \( A_{1} \) מאוד פשוט של הרכיב שמתאר את הפונקציה שהוא צריך לחשב, אבל ייתכן מאוד שמכל בחינה מעשית, המימוש של הרכיב הוא מאוד לא יעיל (מבחינת מספר שערים; מיקום שערים; צריכת חשמל; זמן ביצוע החישוב ועוד אינסוף שיקולים מורכבים שמהנדסי חומרה חייבים להתחשב בהם). מצד שני, יש לנו מימוש בפועל \( A_{2} \) שמהנדס חומרה עבד עליו מאוד קשה, אבל לכו תדעו עד אם הוא לא פספס משהו ואם אין באגים וכדומה. ועכשיו תחשבו שבלחיצת כפתור היה אפשר לבדוק אם \( A_{1} \) שקול ל-\( A_{2} \). זה סוג הקושי שמדובר עליו כאן. עבור תוכניות מחשב כלליות זה פשוט לא עובד - אין אלגוריתם שמסוגל לבדוק אם שתי תוכניות מחשב הן שקולות. אבל עבור אוטומטים זה כן עובד, ואפילו עובד בצורה פשוטה להחריד, מבחינה רעיונית (מבחינת החישוב - שוב, זה ייקח יותר מדי זמן בפועל בסיטואציות אמיתיות של בדיקת רכיבי חומרה, אבל זה לא אומר שזה לא מועיל בהקשרים אחרים).

איך אנחנו עושים את הקסם הזה? פשוט מאוד - רדוקציה לבעיה של בדיקת ריקנות. אם \( L_{1}=L\left(A_{1}\right) \) ו-\( L_{2}=L\left(A_{2}\right) \), נבנה אוטומט עבור ההפרש הסימטרי של \( L_{1} \) ו-\( L_{2} \) - אוסף המילים ששייכות לשפה אחת אבל לא לשניה. מן הסתם ההפרש הסימטרי ריק אם ורק אם השפות שוות. פורמלית, ההפרש הסימטרי הוא \( \left(L_{1}\backslash L_{2}\right)\cup\left(L_{2}\backslash L_{1}\right)=\left(L_{1}\cap\overline{L_{2}}\right)\cup\left(L_{2}\cap\overline{L_{1}}\right) \), ואלו תכונות סגור; בפועל פשוט בונים אוטומט מכפלה עם מצבים מקבלים \( \left(F_{1}\times\left(Q_{2}\backslash F_{2}\right)\right)\cup\left(\left(Q_{1}\backslash F_{1}\right)\times F_{2}\right) \).

האם אפשר לעשות משהו דומה עבור שפות חסרות הקשר? ובכן, התשובה היא חד משמעית לא. לא קיים אלגוריתם שבודק שקילות של שני דקדוקים חסרי הקשר. אבל למה? איך מוכיחים את זה? כאן אני חייב לגלוש קצת לתורה של בעיות לא כריעות. ספציפית, אני אציג בעיה לא כריעה אחת שבעזרתה אוכיח שהבעיות הקשורות לדקדוקים אינן כריעות. הבעיה הזו נקראת “בעיית ההתאמה של פוסט” ובקיצור PCP ויש לי עליה פוסט ייעודי שגם מוכיח שהיא לא כריעה. בפוסט הזה לא רק שלא אוכיח שהבעיה הזו לא כריעה, אלא גם לא אכנס לתיאור עמוק שלה, אלא ההפך - אציג ניסוח שקול שלה שהוא מאוד פשוט אבל עושה שימוש בטרמינולוגיה שאנחנו כבר מכירים ולא הנחתי אותה בפוסט ההוא. בניסוח שלי, בעיית ההתאמה של פוסט היא הדבר הבא: נתון לנו אלפבתים סופיים \( \Sigma \) ו-\( \Delta \) ונתונים שני הומומורפיזמים \( h:\Sigma\to\Delta^{*} \) ו-\( g:\Sigma\to\Delta^{*} \). השאלה: האם קיימת מילה \( w\in\Sigma^{*} \) כך ש-\( h\left(w\right)=g\left(w\right) \)? וזו, כאמור, בעיה לא כריעה.

כעת, בואו נתעסק בבעיה הבאה: נתונות שתי שפות חסרות הקשר \( L_{1},L_{2} \) (נתונות באמצעות דקדוקים, כרגיל). האם \( L_{1}\cap L_{2}=\emptyset \)? כלומר, האם יש מילה משותפת כלשהי לשתי השפות? אני אראה שאם אנחנו יודעים לפתור את הבעיה הזו באופן כללי, אז אנו גם יודעים לפתור את PCP. הרדוקציה היא פשוטה מאוד, למעשה - קחו רגע וראו אם תצליחו לחשוב עליה.

האלפבית שמעליו השפות שלו יוגדר יסומן בתור \( \Gamma=\Sigma\cup\Delta \), כלומר הוא כולל גם את האותיות של \( \Sigma \) וגם של \( \Delta \), ואני אניח בלי הגבלת הכלליות ש-\( \Sigma\cap\Delta=\emptyset \). עכשיו, אגדיר \( L_{1}=\left\{ w\#w^{R}\ |\ w\in\Gamma^{*}\right\} \) (אני מניח ש-\( \#\notin\Gamma \)) - מה שנקרא “שפת ראי מסומנת”. קל לראות שזו שפה חסרת הקשר - כללי הדקדוק הם פשוט \( \left\{ S\to\sigma S\sigma\ |\ \sigma\in\Gamma\right\} \cup\left\{ S\to\#\right\} \). עכשיו, נגדיר את \( L_{2} \) כך: \( L_{2}=\left\{ u^{R}h\left(u\right)\#\left(v^{R}g\left(v\right)\right)^{R}\ |\ u,v\in\Sigma^{*}\right\} \). גם זו שפה חסרת הקשר, וקל לראות את זה עם תכונות סגור. ראשית, \( L=\left\{ w^{R}w^{\prime}\ |\ w\in\Sigma^{*}\right\} \) היא שפה חסרת הקשר עם דקדוק \( S\to\sigma S\sigma^{\prime}|\varepsilon \). שנית, נפעיל על \( L \) הומומורפיזם שעל אותיות ללא תג מחזיר את עצמן, ועל אותיות עם תג מחזיר את מה ש-\( h \) מחזירה על האות ללא תג, ונקבל את השפה \( \left\{ w^{R}h\left(w\right)\ |\ w\in\Sigma^{*}\right\} \). לבסוף נשרשר עם השפה הזו עם השפה שמכילה רק את \( \# \) ואת זה עם השפה שעליה עשינו את אותו תעלול רק עם \( g \).

קחו רגע לשכנע את עצמכם שאכן \( L_{1}\cap L_{2}\ne\emptyset \) אם ורק אם קיים \( w \) כך ש-\( h\left(w\right)=g\left(w\right) \); זה מסיים את ההוכחה.

עכשיו, בעזרת כללי דה-מורגן נקבל ש-\( L_{1}\cap L_{2}\ne\emptyset \) אם ורק אם \( \overline{L_{1}}\cup\overline{L_{2}}\ne\Sigma^{*} \). באופן כללי דבר כזה לא יעזור לנו במיוחד, כי זה ש-\( L_{1},L_{2} \) הן חסרות הקשר לא אומר שגם המשלימות שלהן כאלו, אבל במקרה שלנו זה דווקא נכון. אולי הדרך הקלה ביותר לראות זאת היא באמצעות האבחנה שאת \( L_{1},L_{2} \) אפשר לקבל עם אוטומט מחסנית דטרמיניסטי (מושג שטרם הגדרתי), אבל אפשר גם סתם לחשוב כמה דקות על איך לבנות אוטומטי מחסנית שמקבלים את \( \overline{L_{1}},\overline{L_{2}} \).

המסקנה? אם \( \overline{L_{1}},\overline{L_{2}} \) הן חסרות הקשר כך גם \( \overline{L_{1}}\cup\overline{L_{2}} \), ולכן קיבלנו שהבעיה הבאה אינה כריעה: בהינתן שפה חסרת הקשר \( L \), יש לבדוק האם \( L=\Sigma^{*} \). הבעיה הזו מכונה “בעיית האוניברסליות”. העובדה שהיא לא כריעה מראה מייד שגם בדיקת שקילות של דקדוקים היא בעיה לא כריעה - כי אם בהינתן \( G_{1},G_{2} \) היינו יכולים לבדוק האם \( L\left(G_{1}\right)=L\left(G_{2}\right) \) היינו פותרים את בעיית האוניברסליות על ידי בדיקת שקילות לדקדוק שאנחנו יודעים שמייצר את \( \Sigma^{*} \). בעיה נוספת שמייד רואים שהיא לא כריעה היא בעיית ההכלה: בהינתן \( L_{1},L_{2} \), אם הייתה לנו דרך לבדוק האם \( L_{1}\subseteq L_{2} \) היינו יכולים לפתור את בעיית האוניברסליות על ידי בדיקה האם \( \Sigma^{*}\subseteq L \) (או לחילופין, היינו יכולים לבדוק האם \( L_{1}=L_{2} \) על ידי בדיקה האם \( L_{1}\subseteq L_{2} \) וגם \( L_{2}\subseteq L_{1} \)).

חוב אחד שלי שעדיין נשאר מפוסט קודם הוא השאלה האם בהינתן דקדוק \( G \) ניתן לקבוע אם הוא חד משמעי, או שקיימת מילה שקיימים לה שני עצי גזירה. בעיית ההתאמה של פוסט יכולה להיפתר גם על ידי אלגוריתם כזה: בהינתן \( h,g \) נבנה את הדקדוק \( G \) הבא: \( S\to A|B \) ו-\( A\to\sigma Ah\left(\sigma\right)|\varepsilon \) ו-\( B\to\sigma Bg\left(\sigma\right)|\varepsilon \). הדקדוק הזה מייצר מילים מהצורה \( w^{R}h\left(w\right) \) ו-\( w^{R}g\left(w\right) \). כל מילה מהצורה \( w^{R}h\left(w\right) \) נוצרת בצורה יחידה (ה-\( w^{R} \) שבהתחלה מבטיח את זה) וכך גם עבור \( w^{R}g\left(w\right) \); לכן הסיכוי היחיד של הדקדוק להיות רב-משמעי הוא שיתקיים \( w^{R}h\left(w\right)=w^{R}g\left(w\right) \) עבור \( w \) כלשהו, מה שגורר \( h\left(w\right)=g\left(w\right) \).

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

נתחיל מזה שלא סתם לוקחים דקדוק כלשהו עבור \( L \) - לוקחים דקדוק \( G \) בצורה הנורמלית של חומסקי, שכבר הזכרתי בעבר ואזכיר שוב - בצורה הנורמלית הזו כל כללי הגזירה בדקדוק הם מהצורה \( A\to a \) או \( A\to BC \). לכל שפה חסרת הקשר \( L \) קיים דקדוק בצורה הנורמלית של חומסקי שמקיים \( L\left(G\right)=L\backslash\left\{ \varepsilon\right\} \) (כלומר, אם המילה הריקה הייתה שייכת ל-\( L \), אז הדקדוק לא ידע לייצר אותה כי הצורה הנורמלית של חומסקי לא מאפשרת את זה). זה אומר שאם אנחנו רוצים לבדוק אם \( \varepsilon\in L \) צריך לבדוק באמצעות אלגוריתם אחר, אבל זה יחסית קל (זה שקול לבדיקה האם המשתנה \( S \) אפיס, כלומר יש לו סדרת גזירה שמסתיימת ב-\( \varepsilon \), וזו בדיקה דומה לבדיקה האם משתנה הוא טרמינלי).

אם כן, אנו מניחים ש-\( w \) הוא מאורך 1 לפחות. והנה הרעיון של האלגוריתם: אם \( A\Rightarrow^{*}w \) אז מתקיים בדיוק אחד משני דברים - או ש-\( \left|w\right| \) מאורך 1 וקיימת גזירה \( A\to w \) בדקדוק; או שקיים פירוק \( w=uv \) וגזירה \( A\to BC \) כך ש-\( B\Rightarrow^{*}u \) וגם \( C\Rightarrow^{*}v \). על בסיס האבחנה הזו אפשר לתת אלגוריתם רקורסיבי שבודק את התנאי הזה, על ידי בדיקת כל הפירוקים האפשריים של \( w \) מהצורה \( w=uv \), ועם תנאי עצירה עבור הסיטואציה שבה \( \left|w\right|=1 \).

רק מה, האלגוריתם הרקורסיבי הזה עשוי לעשות עבודה כפולה, ולא מעט ממנה. לכן אנחנו נוקטים בגישה שמכונה תכנון דינמי, והיא בעצם שם מפוצץ ל”תזכור את תוצאות חישובי הביניים שלך ותשתמש בהן שוב אם צריך”. לצורך כך, בואו נניח ש-\( w=\sigma_{1}\sigma_{2}\dots\sigma_{n} \). כעת אפשר לתאר תת-מילים של \( w \) באמצעות שני מספרים טבעיים - האורך שלה \( l \), והאינדקס שבו היא מתחילה \( i \). כעת אגדיר משתנים בוליאניים \( P_{l,i}^{\left(A\right)} \) שהרעיון הוא שהם יקבלו “אמת” אם ורק אם \( A\Rightarrow^{*}\sigma_{i}\sigma_{i+1}\dots\sigma_{i+\left(l-1\right)} \). אם \( S \) הוא המשתנה ההתחלתי של הדקדוק, הרי שהשאלה האם \( w\in L \) זהה לשאלה אם \( P_{n,1}^{\left(S\right)} \) הוא “אמת”, אז מה שאנחנו רוצים הוא אלגוריתם לחישוב ה-\( P \)-ים הללו.

לא אתן כאן פסאודו-קוד מלא של האלגוריתם (אבל למי שזה מעניין אותו אני ממליץ לתכנת אותו), אבל הרעיון הכללי פשוט: ראשית נותנים את הערך “שקר” לכל ה-\( P \)-ים. כעת עוברים על כל הגזירות מהצורה \( A\to a \) בדקדוק ומשנים את \( P_{1,i}^{\left(A\right)} \) ל”אמת” לכל אינדקס \( i \) כך ש-\( \sigma_{i}=a \). זה תנאי ההתחלה שלנו.

עכשיו, לכל \( 1<r\le n \) באופן סדרתי, ולכל משתנה \( A \), ולכל \( 1\le i\le n-r \) אנחנו רוצים לחשב מהו \( P_{r,i}^{\left(A\right)} \) - כלומר, האם \( A \) יודע לגזור את תת-המילה \( \sigma_{i}\sigma_{i+1}\dots\sigma_{i+\left(r-1\right)} \). לצורך כך אנחנו עוברים על כל הגזירות מהצורה \( A\to BC \) של המשתנה \( A \); כעת, לכל אינדקס \( i\le j<n-r \) אנחנו בודקים האם שני המשתנים \( P_{j-i+1,i}^{\left(B\right)} \) ו-\( P_{n-r-j,j+1}^{\left(C\right)} \) הם “אמת” בו זמנית - אם כן, אז הופכים את \( P_{r,i}^{\left(A\right)} \) לאמת בעצמו. זה הסוף.

מה הסיבוכיות של האלגוריתם? מכיוון שכל \( P \) מחושב בדיוק פעם אחת, הקריאה ה”רקורסיבית” שדיברתי עליה לא באה לידי ביטוי באלגוריתם כלל (האלגוריתם הוא למעשה איטרטיבי, לא רקורסיבי). זה אומר שצריך בעיקר לבדוק כמה לולאות יש בו. שאלה אחרת היא ביחס למה מודדים את הסיבוכיות - כאן יש שני גורמים שונים. אחד הוא אורך המילה \( w \), שסימנו \( n \), והשני הוא גודל הדקדוק \( \left|G\right| \) (למשל, מספר כללי הגזירה שלו).

ובכן, אנחנו עוברים על כל ה”רמות” של ה-\( P \)-ים, החל מ-\( r=1 \) ועד \( r=n \), כך שזו לולאה אחת מאורך \( n \); בכל מעבר כזה, אנחנו עוברים על כל ה-\( i \)-ים בתחום מ-1 ועד \( n-r \) - זו לולאה שניה שמספר האיטרציות בה חסום על ידי \( n \). כעת אנחנו עוברים על כל הגזירות הקיימות בדקדוק לכל המשתנים - חסום על ידי \( \left|G\right| \), ולכל גזירה כזו אנו מבצעים בדיקה שתלויה בבחירה של האינדקס \( i\le j<n-r \) - גם כן חסום על ידי \( n \). קיבלנו זמן ריצה של \( O\left(n^{3}\left|G\right|\right) \). שזה לא רע, גם אם לא נפלא כמו זמן הריצה \( O\left(n\right) \) של אוטומט סופי דטרמיניסטי על מילה. כמובן, במרבית היישומים הפרקטיים זה לא מספיק טוב, ומשתמשים באלגוריתמים פחות כלליים שמותאמים לדקדוקים יותר ספציפיים ויעילים - אבל זה נושא לדיון כשמדברים על פרסור שפות חסרות הקשר (למשל, בקומפילציה).

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