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