logo

דוגמאות ל-DFA

דוגמה 1:

עצב FA עם ∑ = {0, 1} מקבל את המחרוזת שמתחילה ב-1 ומסתיימת ב-0.

פִּתָרוֹן:

ל-FA יהיה מצב התחלה q0 שממנו רק הקצה עם קלט 1 יעבור למצב הבא.

דוגמאות לאוטומטים סופיים דטרמיניסטיים

במצב q1, אם נקרא 1, נהיה במצב q1, אבל אם נקרא 0 במצב q1, נגיע למצב q2 שהוא המצב הסופי. במצב q2, אם נקרא 0 או 1, נעבור למצב q2 או מצב q1 בהתאמה. שימו לב שאם הקלט מסתיים ב-0, הוא יהיה במצב הסופי.

דוגמה 2:

תכנן FA עם ∑ = {0, 1} מקבל את הקלט היחיד 101.

פִּתָרוֹן:

דוגמאות לאוטומטים סופיים דטרמיניסטיים

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

דוגמה 3:

עיצוב FA עם ∑ = {0, 1} מקבל מספר זוגי של 0 ומספר זוגי של 1.

סורק Java הבא

פִּתָרוֹן:

FA זה ישקול ארבעה שלבים שונים עבור קלט 0 וקלט 1. השלבים יכולים להיות:

דוגמאות לאוטומטים סופיים דטרמיניסטיים

כאן q0 הוא מצב התחלה וגם המצב הסופי. שימו לב היטב שנשמרת סימטריה של 0 ו-1. אנו יכולים לשייך משמעויות לכל מדינה כמו:

q0: מצב של מספר זוגי של 0 ומספר זוגי של 1.
q1: מצב של מספר אי זוגי של 0 ומספר זוגי של 1.
q2: מצב של מספר אי זוגי של 0 ומספר אי זוגי של 1.
q3: מצב של מספר זוגי של 0 ומספר אי זוגי של 1.

דוגמה 4:

עיצוב FA עם ∑ = {0, 1} מקבל את קבוצת כל המחרוזות עם שלוש 0 רצופות.

פִּתָרוֹן:

המחרוזות שייווצרו עבור שפות ספציפיות זו הן 000, 0001, 1000, 10001, .... שבהן 0 מופיע תמיד בגוש של 3. גרף המעבר הוא כדלקמן:

דוגמאות לאוטומטים סופיים דטרמיניסטיים

שימו לב שרצף האפסים המשולשים נשמר כדי להגיע למצב הסופי.

דוגמה 5:

עצב DFA L(M) = {w | w ε {0, 1}*} ו-W היא מחרוזת שאינה מכילה 1ים עוקבים.

פִּתָרוֹן:

כאשר מתרחשים שלושה 1'ים רצופים, ה-DFA יהיה:

איך להשיג משחק יונה באנדרואיד
דוגמאות לאוטומטים סופיים דטרמיניסטיים

כאן שני 1ים רצופים או יחיד 1 מקובלים, ומכאן

דוגמאות לאוטומטים סופיים דטרמיניסטיים

השלבים q0, q1, q2 הם המצבים הסופיים. ה-DFA יפיק את המחרוזות שאינן מכילות 1 רצופות כמו 10, 110, 101 וכו'.

דוגמה 6:

עצב FA עם ∑ = {0, 1} מקבל את המחרוזות עם מספר זוגי של 0 ואחריו יחיד 1.

פִּתָרוֹן:

ניתן להציג את ה-DFA באמצעות דיאגרמת מעבר כ:

דוגמאות לאוטומטים סופיים דטרמיניסטיים