אוטומטים ושפות פורמליות/אוטומט סופי דטרמיניסטי: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
פורמלית |
←הגדרה פורמלית: דוגמא ותרגיל |
||
שורה 38:
* <math>F\subseteq Q</math> - קבוצת המצבים המקבלים (מצבים סופיים)
* <math>\delta: Q\times \Sigma \to Q</math> - פונקציית המעברים
== דוגמא ==
נניח כי האלפבית הינו אונרי, כלומר <math>\Sigma=\{1\}</math> ונרצה לתכנן אוטומט המקבל את כל המילים שאורכן הוא כפולה של 3, כלומר אוטומט עבור השפה <math>L=\{\varepsilon, 111, 111111, \ldots\}</math> או באופן פורמלי
<center><math>L=\{ x \in \{1\}^* : |x|\mod 3=0\}</math></center>
קל לראות שעבור אוטומט זה מספיקים שלושה מצבים: המצב הראשון יסמל אורך שהוא כפולה של 3 (ללא שארית), מצב שני יסמל שארית 1, והמצב השלישי - שארית 2. עם כל אות של הקלט האורך גדל באחד, והמכונה עוברת למצב המתאים.
[[קובץ:DFA length mod3.png|שמאל|ממוזער|250px|אוטומט סופי עבור השפה האונרית שאורך מילותיה כפולה שלמה של 3.]]
נשים לב שלמילה הריקה אורך 0, ואורך זה הוא כפולה של שלוש, לכן המצב הראשון (המסמל שארית 0), יהיה מצב מקבל.
{{תרגיל
|מספר=
|שאלה=תכננו אוטמט סופי מעל האלפבית הבינארי המקבל את המחרוזות המייצגות מספר שמתחלק ב-3. ניתן להניח שהמילה הריקה שקולה למספר 0.
|פתרון=(רמז) הוספת 0 למספר בינארי מימינו מכפילה את המספר, והוספת 1 מכפילה ומסיפה 1.
|יישור=ימין}}
| |||