PDA

צפה בגרסה המלאה : [דיון] מודל דטרמיניסטי סופי - שיעורי בית



barbenlulu
29-11-2014, 15:40
בנה אוטומט המקבל את שפת כל המילים מעל הא"ב {a,b} המכילות לפחות a אחד , לכל היותר
3 b-ים ומספר ה b-ים גדול ממספר ה a-ים .זה ממש דחוף תודה לעוזריםם :)

chenkop
18-07-2015, 16:11
דרך פשוטה לבנות את המודל היא לראות מה הגזרה המותרת שלנו:36596 36599
עכשיו נבנה אוטומט, ובכל מצב נציין כמה a היו לנו עד שם וכמה b היו עד שם. עפ"י הגזרה, המצבים המקבלים יהיו כאשר a=1,b=2 או a=1,b=3 או a=2,b=3.
כשנבנה את האוטומט, לא נצא מראש מגבולות הגזרה, זאת אומרת שאם מספר מופעי ה-a גדול מ-2 או מספר מופעי ה-b גדול מ-3 לא ניצור מצב חדש. (האוטומט לא מלא כמובן..אם יש צורך באוטומט מלא, ניתן להוסיף מצב מלכודת בסוף בניית האוטומט ולשלוח לשם את כל האותיות שלא יצאו מהמצבים הלוקים בחסר..) כלומר, האוטומט שנקבל: 36600