בעידן הטכנולוגי של ימינו הן בתחום החומרה והן בתחום התוכנה חלה התפתחות אדירה. אחד מתחומי הפיתוח העיקריים נראה בשיטות של עיצוב חומרה. עם ה טכנולוגיה גוברת הרעיון של חומרה - תוכנה משותפת של תוכנה היה אפשרי ליישום. שיטות שונות מפותחות באמצעותן, באמצעות תוכנה אפשר לתכנן ולדמות במלואן את מערכות החומרה. אחת משיטות כאלה היא תורת האוטומטיות. תורת האוטומטיות היא הענף של מדעי המחשב העוסק בתכנון המודל המופשט של מכשירי מחשוב העוקבים באופן אוטומטי אחר רצף הצעדים שנקבע מראש. מאמר זה דן במידע קצר על הדרכות אוטומטיות.
מהי תורת האוטומטיות?
המילה אוטומטה נגזרת מיוונית, שפירושה 'פעולה עצמית'. אוטומט הוא מודל מתמטי של המכונה. האוטומטון מורכב ממצבים ומעברים. כאשר הקלט ניתן לאוטומט, הוא מבצע מעבר למצב הבא, תלוי בפונקציית המעבר. הקלטים לפונקציית המעבר הם המצב הנוכחי והסמלים האחרונים. אם לאוטומטון יש מספר סופי של מצבים, הוא מכונה אוטומטי סופי או מכונת מדינה סופית . האוטומטים הסופיים מיוצגים על ידי 5-כפולה (Q, ∑, δ, qo, F)
איפה,
Q = קבוצת מצבים סופית.
∑ = קבוצה סופית של סמלים הנקראת גם אלפבית של האוטומט.
δ = פונקציית המעבר.
qo = מצב התחלתי של הקלט.
F = קבוצה של מצבים סופיים של Q.
טרמינולוגיות בסיסיות של תורת האוטומטיות
חלק מהטרמינולוגיות הבסיסיות של תורת האוטומטיות הן-
1 . אלף בית : כל קבוצה סופית של סמלים בתורת האוטומטיות מכונה אלפבית. מיוצג על ידי האות∑ הסט {a, b, c, d, e,} נקרא Alfabet set, ואילו האותיות של הסט 'a', 'b', 'c', 'd', 'e' נקראות סמלים.
שתיים . חוּט : באוטומט, מחרוזת היא רצף סופי של סמלים הלקוחים מסט האלפבית ∑, לדוגמא, המחרוזת S = 'adeaddadc' תקפה על קבוצת האלפבית∑ = {a, b, c, d, e,}
3 . אורך המחרוזת : מספר הסמלים הקיימים במחרוזת מכונה אורך המחרוזת. עבור המחרוזת S = 'adaada' אורך המחרוזת הוא | S | = 6. אם אורך המחרוזת הוא 0, אז זה נקרא מחרוזת ריקה.
4 . כוכב קלן : זהו האופרטור האחיד על קבוצת הסמלים Σ, שנותן את האינסוף של כל המיתרים האפשריים, כולל λ, של כל האורכים האפשריים על פני הסט Σ. זה מיוצג על ידי. לדוגמא, עבור הסט Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . סגירת קליין : זה הסט האינסופי של כל המיתרים האפשריים של האלף-בית, למעט λ. זה מסומן על ידי. עבור הסט Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd, ... ..}.
6 . שפה : השפה היא קבוצת המשנה של קבוצת הכוכבים Kleene∑ * עבור קבוצת אלפבית כלשהי Σ. השפה יכולה להיות סופית או אינסופית. לדוגמא אם שפה לוקחת את כל המיתרים האפשריים באורך 2 על פני הסט Σ = {a, d}, אז L = {aa, ad, da, dd}.
שפות רשמיות ואוטומטיות
בתורת האוטומט, שפה פורמלית היא מכלול מיתרים, כאשר כל מחרוזת נמצאת מורכב מסמלים השייכים לסט האלפבית הסופי Σ. הבה נבחן שפת חתול, שיכולה להכיל כל מחרוזות מהסט האינסופי להלן ...
מיילל!
meww!
mewww !! ……
האלף-בית שנקבע לשפת החתול הוא Σ = {m, e, w,!}. בואו להשתמש בערכה זו עבור מודל אוטומטי של המדינה הסופית. ואז השפה הפורמלית המאופיינת במודל m מסומנת על ידי
L (מ ')
L (m) = {'mew!', 'Meww!', 'Mewww', ...…}
אוטומטון שימושי להגדרת שפה מכיוון שהוא יכול לבטא מערך אינסופי בצורה סגורה. שפות פורמליות אינן זהות לשפות הטבעיות בהן אנו מדברים בחיי היום יום שלנו. שפה רשמית יכולה לציין את המצבים השונים של המכונה, בניגוד לשפות הרגילות שלנו. שפה פורמלית משמשת למודל חלק מהשפה הטבעית כגון תחביר וכו '... שפות פורמליות מוגדרות על ידי אוטומטיות של מדינה סופית. ישנן שתי נקודות מבט עיקריות של אוטומטים של מצב סופי - מקבלים שיכולים לדעת אם מחרוזת בשפה והשנייה היא המחולל שמייצר רק את המחרוזות בשפה.
אוטומטיות סופיות דטרמיניסטיות
בסוג אוטומטי דטרמיניסטי, כאשר ניתן קלט, אנו תמיד יכולים לקבוע לאיזה מצב יהיה המעבר. מכיוון שמדובר באוטומט סופי, הוא נקרא אוטומט סופי דטרמיניסטי.
ייצוג גרפי
דיאגרמת מצב היא הדיגראפים המשמשים לייצוג גרפי של אוטומטיות סופיות דטרמיניסטיות. תן לנו להבין עם דוגמא. תן לאוטומטים סופיים דטרמיניסטיים להיות ...
ש = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} ופונקציית המעבר תהיה
טופס טבלה ייצוג גרפי
דיאגרמת מדינה
דיאגרמת מדינות אוטומטיות של מדינה סופית
מתרשים המצב
- המדינות מיוצגות על ידי קודקודים.
- מעברים מיוצגים על ידי הקשת שכותרתה אלפבית קלט.
- הקשת הנכנסת היחידה הריקה מייצגת את המצב ההתחלתי.
- המדינה עם מעגלים כפולים היא המדינה הסופית.
אוטומטיות סופיות לא דטרמיניסטיות
האוטומטיות שבה לא ניתן לקבוע את מצב הפלט עבור הקלט הנתון נקראת אוטומטיות לא דטרמיניסטיות. זה נקרא גם אוטומטית סופית לא דטרמיניסטית, מכיוון שיש לה מספר סופי של מדינות. אוטומטיות סופיות לא דטרמיניסטיות מיוצגות כמערכת של 5 - כפול איפה (Q, ∑, δ, qo, F)
ש = קבוצה סופית של מדינות.
∑ = ערכת אלפבית.
δ = פונקציית המעבר
איפה : 
qo = מצב התחלתי.
ייצוג גרפי
אוטומטים סופיים לא דטרמיניסטיים מיוצגים בעזרת תרשים המצב. תנו לאוטומטיות הסופית הלא-דטרמיניסטית להיות-
ש = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
המעברים הם
טופס טבלה ייצוג גרפי
“מהו מסך lcd ”
דיאגרמת מדינה
דיאגרמת מדינה של אוטומטיות סופיות לא דטרמיניסטיות
יישומי תיאוריה אוטומטית
היישומים של תורת האוטומט כלול את הבאים.
- תורת האוטומטיות שימושית מאוד בתחומי תורת החישוב, הפקות מהדרים, AI וכו '.
- עבור מהדרים לעיבוד טקסטים ועיצובי חומרה, אוטומטים סופיים ממלאים תפקיד מרכזי.
- ליישומים ב- AI וב- שפות תכנות , דקדוק ללא הקשר הוא מאוד שימושי.
- בתחום הביולוגיה אוטומטים סלולריים שימושיים.
- בתיאוריה של שדות סופיים אנו גם יכולים למצוא את היישום של אוטומט.
במאמר זה למדנו הקדמה קצרה לשפות תורת האוטומטיות ולחישוב. האוטומטיות היו קיימות מאז התקופה הפרהיסטורית. עם המצאת הטכנולוגיות החדשות ניתן לראות פיתוחים חדשים רבים בתחום זה. באיזה סוג אוטומטים נתקלתם?
