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

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

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

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

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

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