שפות רגולריות – משפט קלייני

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

שפות רגולריות – תכונות סגור (חלק ב')

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

שפות רגולריות – תכונות סגור (חלק א')

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