אוטומטים ושפות פורמאליות

פרויקט במסגרת קול קורא 2 לקידום יישומי טכנולוגיות למידה

 

מרק טרכטנברוט, ולדימיר נודלמן, אבי למעי

מכון טכנולוגי חולון

יהודית גל-עזר, רינה צביאל-גירשין, מיכל ארמוני, יהלום הומי

האוניברסיטה הפתוחה

 

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

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

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

מבחינת הסטודנט, הכלי מציע שלושה אופני עבודה עיקריים:

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

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

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

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

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

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