|
אוטומטים סופיים
בתורת החישוביות במדעי המחשב, אוטומט סופי הוא מכונה מופשטת בעלת זיכרון מוגבל המגדירה שפה פורמלית.קיימים שני סוגים של אוטומטים סופיים – אוטומט סופי דטרמיניסטי (DFA – Deterministic Finite Automaton) ואוטומט סופי לא דטרמיניסטי (NFA – Nondeterministic Finite Automaton).ניתן לתאר אוטומט סופי דטרמיניסטי באמצעות קבוצה סופית של מצבים, המשמשים את האוטומט והוא עובר בהם לפי כללים קבועים מראש במהלך קריאת מילת קלט. חלק ממצבי האוטומט הם מצבים מקבלים. אם בסוף קריאת המילה מגיע האוטומט למצב מקבל, המילה שייכת לשפה המוגדרת על ידיו, אחרת לא.
אוטומט סופי לא־דטרמיניסטי דומה לאוטומט הדטרמיניסטי, רק שמכל מצב יכולים להיות מספר מסלולים למצב אחר עבור אות קלט, או שאין אף מסלול אפשרי ממצב מסוים עבור אות קלט מסוימת. מבחינה פורמלית, מילה תתקבל אם ורק אם קיים מסלול עבורה מהמצב ההתחלתי עד למצב מקבל כלשהו.
    תגובות
|
lunch box
צופים עכשיו
|
| אי-מייל: | |
| שם: | |
עוד נושאים
תמונות
מדיה 
חדשות
