20-01-2008, 15:15
|
|
|
|
חבר מתאריך: 03.04.07
הודעות: 242
|
|
עברו כמעט שנתיים אבל אני אנסה להזכר ולעזור לך 
אני אעבור איתך על הפתרון מבחינה לוגית, ואח"כ תנסה ליישם את זה.
קודם כל ברור לך מהנתונים שחייבת להיות לפחות A אחת, לפחות B אחת (למעשה 3), C אחת ו D אחת. אז אתה מתחיל בזה שאתה עושה 5 מצבים, q0-q4 כאשר q4 הוא מצב מקבל. מעבר מ q0 ל q1 מתבצע בקלט A, מעבר מ q1 ל q2 מתבצע בקלט B וכו'. זה מכריח את התוכנה לקבל את כל האותיות פעם אחת לפחות בסדר המבוקש (ABCD). עכשיו אנחנו בוחנים שוב את הנתונים ורואים שA יכולה להופיעה מספר אינסופי של פעמים (לא תלויה בשום אות אחרת) לכן אפשר לעשות מעבר שיוצא מq1 אל עצמו עם A. בגלל שאנחנו רוצים לספור את ה A אז בכל מעבר עד עכשיו שקיבלנו A תדחוף למחסנית אות מסוימת (נגיד a קטנה או מה שתרצה אנערף). עכשיו שסיימנו עם A נעבור ל B, אפשר לראות ש B תלויה במספר ההופעות של A (בגלל M) אז במעבר מ q1 ל q2 (שקורה כשמקבלים B) נוציא a אחת מהמחסנית. נוסיף מצב q5 ונצייר מעבר מ q2 אליו (בגלל ש M+J+K חייב להיות זוגי, וזה במקרה מספר ההופעות של B) ככה אתה מבטיח שקיבלת מספר זוגי של B (המעבר מ q1 ל q2 ועוד המעבר מ q2 ל q5 מוציא מינימום 2 B) ומעבר חזרה מ q5 ל q2. מעבר לכאן אני מקווה שתסתדר, אם לא אני אהיה כאן לעזור ואם ממש ממש תצטרך אני גם אשרטט לך את האוטומט כולו (לא אחד מלא, בלי כל המצבי מלכודת וכו'). נסה להמשיך בדרך מחשבה שהראיתי כאן ושים לב כל הזמן לתנאים.
_____________________________________
חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.
|
ראשי
צ'אט
)
מצב כלאיים
