אוטומטים אי דטרמיניסטיים ושאר מריעין בישין

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

אוטומטים ושפות רגולריות – מבוא

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