משפט קלייני – הוכחה נוספת

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

למת הניפוח לשפות רגולריות – גרסה מלאה

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

משפט מייהיל-נרוד – נקודת מבט נוספת, ואלגוריתמי מינימיזציה

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

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

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

שפות חסרות הקשר – למת הניפוח, הלמה של אוגדן ושפות רב משמעיות

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

שקילות אוטומט מחסנית ודקדוק חסר הקשר

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

אוטומט מחסנית

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