תורת האוטומטים, אוטומטים סופיים
המבנה, העיצוב, עקרון הפעולה של מכונות שונות נקבעים במידה רבה על ידי המטרה הפונקציונלית שלה. הבחנה בין מכונות טכנולוגיות, תחבורה, מחשוב, צבאיות ואחרות. מתחמים אוטומטיים שלמים המיועדים לביצוע תהליכים טכנולוגיים מורכבים מוצגים באופן נרחב בתעשיות שונות. תוכננו ונבנו אוטומטים המבצעים פונקציות לוגיות שונות (מכונות לוגיות).
תורת האוטומטים — מדור קיברנטיקה, שהתעוררה בהשפעת הדרישות של הטכנולוגיה של מחשבים דיגיטליים ומכונות בקרה. אוטומטים בדידים הנלמדים בתורת האוטומטים הם מודלים מופשטים של מערכות אמיתיות (הן טכניות והן ביולוגיות) המעבדות מידע דיסקרטי (דיגיטלי) בשלבי זמן נפרדים.
תורת האוטומט מבוססת על מושגים מתמטיים מדויקים המעצבים רעיונות אינטואיטיביים לגבי תפקודו (התנהגות) של האוטומט ולגבי המבנה שלו (מבנה פנימי).
במקרה זה, טרנספורמציה של מידע תמיד מובנת כפעולה ההופכת רצפי קלט המורכבים מאותיות מאלפבית הקלט לרצפי פלט המורכבים מאותיות מאלפבית הפלט.
המנגנון של לוגיקה מתמטית, אלגברה, תורת ההסתברות, קומבינטוריקה ותורת הגרפים נמצא בשימוש נרחב.
הבעיה עם תורת האוטומטים בחלק מחלקיה (תורת האוטומטים) הלכה וגברה מהתיאוריה של מעגלי ממסר-מגע, שהחלה להתגבש בסוף שנות ה-30. כָּלוּל שיטות של אלגברה לוגית.
בתיאוריה המבנית של אוטומטים, נלמדים סוגים שונים של סכמות, שנועדו לתאר כיצד אוטומט מורכב נוצר מרכיבים (אלמנטים) פשוטים יותר המחוברים כהלכה במערכת.
כיוון אחר, הנקרא התיאוריה המופשטת של האוטומטים, חוקר את התנהגות האוטומטים (כלומר, אופי הטרנספורמציה של המידע המתבצעת על ידם), תוך הפשטה מפרטי המבנה הפנימי שלהם, והתעורר בשנות החמישים.
במסגרת התיאוריה המופשטת של האוטומטים, תוכן המושגים "אוטומט" ו"מכונה" מוצה בעיקרו על ידי התיאור הסטנדרטי של טרנספורמציה של מידע שמתבצעת על ידי אוטומט. טרנספורמציה כזו יכולה להיות דטרמיניסטית, אבל היא יכולה להיות גם הסתברותית במהותה.
הנחקרות ביותר הן מכונות דטרמיניסטיות (אוטומטות), הכוללות אוטומטים סופיים - מושא המחקר העיקרי בתורת האוטומטים.
מכונת מצבים סופיים מאופיינת בכמות מוגבלת של זיכרון (מספר המצבים הפנימיים) ומוגדרת באמצעות פונקציית מעבר.עם אידיאליזציה סבירה מסוימת, כל המכונות המתמטיות המודרניות ואפילו המוח, מנקודת המבט של תפקודן, יכולים להיחשב כאוטומטים סופיים.
המונחים "מכונה רציפה", "אוטומט מילי", "אוטומט מור" משמשים בספרות (ולא באופן אחיד על ידי כל המחברים) כמילים נרדפות למונח "אוטומט סופי" או כדי להדגיש תכונות מסוימות בפונקציות המעבר של סופי. אוֹטוֹמָט.
אוטומט עם זיכרון בלתי מוגבל היא מכונת טיורינג המסוגלת לבצע (בפוטנציה) כל שינוי מידע יעיל. המושג "מכונת טיורינג" עלה מוקדם יותר מהמושג "מכונת מצב סופי" והוא נחקר בעיקר בתורת האלגוריתמים.
תורת האוטומטים המופשטים קשורה קשר הדוק לתיאוריות אלגבריות ידועות, למשל תורת הקבוצות למחצה. מנקודת מבט יישומית, התוצאות המאפיינות את הטרנספורמציה של מידע באוטומט מבחינת גודל הזיכרון מעוררות עניין.
זה המקרה, למשל, בבעיות בניסויים באוטומטים (עבודות של E.F. מור וכו'), כאשר מידע כזה או אחר על פונקציות המעבר של האוטומט או על קיבולת הזיכרון שלו מתקבל מתוצאות ה- ניסויים.
משימה נוספת היא לחשב את התקופות של רצפי הפלט, בהתבסס על המידע הזמין על גודל הזיכרון של האוטומט ותקופות של רצפי הקלט.
חשיבות רבה היא לפיתוח שיטות למזעור הזיכרון של מכונות מצב סופיות וללימוד התנהגותן בסביבות אקראיות.
בתורת האוטומטים המופשטים, בעיית הסינתזה היא הבאה.במונחים של שפה מסודרת בבירור, התנאים נכתבים להתנהגות האוטומט המעוצב (עבור האירוע המיוצג באוטומט). במקרה זה, יש צורך לפתח שיטות שלפי כל תנאי כתוב:
1) לברר האם קיימת מכונת מצב כזו שהמידע שהומר על ידה עומד בתנאי זה;
2) אם כן, אז פונקציות המעבר של מכונת מצב סופי כזו בנויות או גודל הזיכרון שלה מוערך.
הפתרון של משימת הסינתזה בניסוח כזה מניח יצירה ראשונית של שפה נוחה להקלטת תנאי ההפעלה של אוטומט עם אלגוריתמים נוחים למעבר מהקלטה לפונקציות טרנזיטיביות.
בתיאוריה המבנית של האוטומטים, בעיית הסינתזה מורכבת מבניית שרשרת של אלמנטים מסוג נתון המממשת אוטומט סופי שניתן על ידי פונקציות המעבר שלו. במקרה זה, הם בדרך כלל מציינים קריטריון אופטימלי כלשהו (לדוגמה, המספר המינימלי של אלמנטים) ומבקשים להשיג סכמה אופטימלית.
כפי שהתברר מאוחר יותר, המשמעות היא שחלק מהשיטות והמושגים שפותחו קודם לכן ביחס למעגלי מגע ממסר ישימים למעגלים מסוג אחר.
בקשר לפיתוח טכנולוגיות אלקטרוניות, הנפוצות ביותר הן התוכניות של אלמנטים פונקציונליים (רשתות לוגיות). מקרה מיוחד של רשתות לוגיות הן רשתות עצביות מופשטות, שהיסודות שלהן נקראים נוירונים.
פותחו שיטות סינתזה רבות, בהתאם לסוג המעגלים ולטרנספורמציה של המידע עבורם הם מיועדים (סינתזה של התקני ממסר).
תראה -מזעור מעגלים שילוביים, מפות קרנו, סינתזת מעגלים
מכונת מצב סופי - מודל מתמטי של מערכת בקרה עם גודל זיכרון קבוע (לא מסוגל להגדיל במהלך הפעולה).
הרעיון של מכונת מצב סופי הוא הפשטה מתמטית המאפיינת את המאפיינים הכלליים של קבוצת מערכות בקרה (לדוגמה, מכשיר ממסר רב-לולאות). לכל המערכות הללו יש תכונות משותפות שטבעי לקבל אותן כהגדרה של אוטומט סופי.
לכל אוטומט שהושלם יש כניסה חשופה להשפעות חיצוניות ולאלמנטים פנימיים. הן עבור אלמנטים קלט והן עבור אלמנטים פנימיים, יש מספר קבוע של מצבים בדידים שהם יכולים לקחת.
השינוי במצבי הקלט והאלמנטים הפנימיים מתרחש ברגעים בדידים בזמן, שהמרווחים ביניהם נקראים טיקים. המצב הפנימי (מצב הפנימיות) בסוף הקלטת נקבע לחלוטין על ידי המצב הפנימי ומצב הקלט בתחילת הקלטת.
ניתן לצמצם את כל שאר ההגדרות של אוטומט סופי למאפיין זה, בפרט הגדרות המניחות שלאוטומט סופי יש פלט התלוי במצב הפנימי של האוטומט בזמן נתון.
מבחינת מאפיין כזה, אופי התשומות והמצבים הפנימיים שלו אינו רלוונטי לתיאור של אוטומט שלם. במקום קלט ומצבים, אתה יכול פשוט להסתכל על המספרים שלהם במספור אקראי.
מכונת המצב תוגדר אם צוינה התלות של מספר המצב הפנימי שלו במספר המצב הפנימי הקודם ומספר מצב הקלט הקודם. משימה כזו יכולה להיות בצורת שולחן אחרון.
דרך נפוצה נוספת להגדיר אוטומט שלם היא בניית מה שנקרא דיאגרמות מעבר. מצבי קלט נקראים לעתים קרובות פשוט קלט, ומצבים פנימיים הם פשוט מצבים.
מכונת מצב סופי יכולה להיות דגם של מכשירים טכניים ומערכות ביולוגיות מסוימות. אוטומטים מהסוג הראשון הם, למשל, מכשירי ממסר ומחשבים אלקטרוניים שונים, כולל. בקרי לוגיקה ניתנים לתכנות.
במקרה של התקן ממסר, תפקידם של מצבי הקלט מתבצע על ידי שילובים של מצבים של האלמנטים הרגישים של התקן הממסר (כל שילוב של מצבים כאלה הוא "מצב מורכב", המאופיין באינדיקציה של כל האלמנטים הרגישים של המצבים הבדידים הללו שיש להם ברגע נתון). באופן דומה, שילובים של מצבים של רכיבי ביניים של התקן ממסר פועלים כמצבים פנימיים.
בקר לוגי ניתן לתכנות (PLC) הוא דוגמה להתקן פעולת ממסר שניתן לכנותו מכונת מצב עצמאית.
למעשה, ברגע שהתוכנית הוכנסה ל-PLC והבקר התחיל לחשב, היא אינה חשופה להשפעות חיצוניות וכל מצב עוקב נקבע לחלוטין על פי המצב הקודם שלו. אנו יכולים להניח שלקלט יש אותו מצב בכל מחזור שעון.
לעומת זאת, כל מכונת מצב סופי שיש לה את מצב הקלט היחיד האפשרי נקראת באופן טבעי אוטונומית, מכיוון שבמקרה זה הסביבה החיצונית אינה נושאת מידע השולט בהתנהגותה.
ראה גם:
השימוש במערכות מיקרו-מעבד בהנדסת חשמל על דוגמה של שימוש ב-PLC