תורת האוטומטים היא ענף תיאורטי של מדעי המחשב ומתמטיקה. זהו חקר מכונות מופשטות ובעיות חישוב שניתן לפתור באמצעות מכונות אלו. המכונה המופשטת נקראת האוטומטים. המניע העיקרי מאחורי פיתוח תיאוריית האוטומטים היה לפתח שיטות לתיאור וניתוח ההתנהגות הדינמית של מערכות בדידות.
אוטומט זה מורכב ממצבים ומעברים. ה מדינה מיוצג על ידי מעגלים , וה מעברים מיוצג על ידי חצים .
אוטומט הוא סוג המכונה שלוקח מחרוזת כלשהי כקלט וקלט זה עובר מספר סופי של מצבים ויכול להיכנס למצב הסופי.
יש את הטרמינולוגיות הבסיסיות החשובות והמשמשות לעתים קרובות באוטומטים:
סמלים:
סמלים הם ישות או אובייקטים בודדים, שיכולים להיות כל אות, אלפבית או כל תמונה.
דוגמא:
1, a, b, #
אלפבית:
אלפבית הם קבוצה סופית של סמלים. הוא מסומן על ידי ∑.
דוגמאות:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} חוּט:
זהו אוסף סופי של סמלים מהאלפבית. המחרוזת מסומנת על ידי w.
דוגמה 1:
אם ∑ = {a, b}, מחרוזות שונות שניתן להפיק מ-∑ הן {ab, aa, aaa, bb, bbb, ba, aba.....}.
- מחרוזת עם אפס מופעים של סמלים ידועה כמחרוזת ריקה. הוא מיוצג על ידי ε.
- מספר הסמלים במחרוזת w נקרא אורך המחרוזת. הוא מסומן על ידי |w|.
דוגמה 2:
w = 010 Number of Sting |w| = 3
שפה:
שפה היא אוסף של מחרוזת מתאימה. שפה שנוצרת על Σ יכולה להיות סוֹפִי אוֹ אֵינְסוֹף .
דוגמה: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> דוגמה: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>