אם יש לנו שני אוטומטים סופיים דטרמיניסטים האחד עם x מצבים
והשני עם x,y מצבים. אז נוכל לבנות אוטומט חדש עם x*y מצבים
בו כל מצב מייצג זוג מצבים אחד מכל אחד האוטמטים הקודמים.
ונשים מעברים שייצגו את המעבר של האוטומט בשני האוטומטים
הראשונים.
המצבים המקבלים יהיו המצבים המייצגים זוג של מצבים מקבלים.
המצב ההתחלתי יהיה המצב המייצג את זוג המצבים ההתחלתיים.ונפעיל כדוגמא עבור המקרה שלנו: ראשית נבנה אוטומט המקבל
L1=a^nB^mC^q הוא יכיל 4 מצבים (למעשה 3 ומצב מלכודת)
נמספר המצבים 1-4 ונבנה טבלת מעברים אשר נכתוב כך
שהשורה:
משמעותה ממצב אחד בהנתן האות a עוברים למצב 2.
אפשר לכתוב במקום a גם a,b למשל שזה יגיד b או c או
נכתוב ? כלומר כל סימן.
המצב ההתחלתי הוא תמיד 1, המצבים המקבלים יכתוב
E=4,5,6 כלומר המצבים המקבלים הם המצוינים
האוטומט הראשון יראה כך:
1:a:1
1:b:2
2:b:2
2:c:3
3:c:3
1:c:4
2:a:4
3:a,c:4
4:?:4
E=3
|
האוטומט השני מקבל שפה של כל המילים האי זוגיות
הוא מכיל שני מצבים:
נוכל לבנות אוטומט מכפלה בה מספרי הצמתים יהיו זוג ספרות
כאשר מתכילים מ11 הספרה הימנית מהאוטומט הראשון והשמאלית מהשני.
11:a:21
21:a:11
11:b:22
22:b:12
12:b:22
22:b:12
12:c:23
22:c:13
23:c:13
13:c:23
E=23
|
הזנחתי את מצב המלכודת והמעברים אליו, כל מעבר אחר צריך להוביל
אל מצב מלכודת, כך בנינו אס"ד המקבל את השפה המבוקשת.
DRYICE
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
