ביטוי רגולרי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
מ הוספת קישור לאוטומט סופי דטרמיניסטי |
||
שורה 41:
===לכל שפה רגולרית קיים ביטוי רגולרי===
טענה זו מסובכת יותר להוכחה. בהינתן שפה רגולרית <math>\ L</math> על פי ההגדרה קיים [[אוטומט סופי דטרמיניסטי]] <math>\ A</math> המקבל אותה. הביטוי הרגולרי נבנה בהתבסס על האוטומט. לצורך נוחות מסמנים את קבוצת המצבים שלו במספרים הטבעיים: <math>\ Q=\left\{q_1,\dots,q_n\right\}</math>, כאשר <math>\ q_1</math> הוא המצב ההתחלתי.
לצורך ההוכחה מוגדרות שפות עזר: <math>\ L_{ij}^k</math> מוגדרת כשפת כל המילים שמעבירות את האוטומט מהמצב <math>\ q_i</math> למצב <math>\ q_j</math> מבלי שהמסלול ייכנס וייצא ממצב שמספרו גדול מ-<math>\ k</math>. ברור כי <math>\ L(A)=\bigcup_{j:q_j\isin F} L_{1j}^n</math> - השפה שמקבל האוטומט היא אוסף כל המילים שמעבירות את האוטומט מהמצב הראשון למצב מקבל כלשהו, כאשר אין הגבלה על המצבים שמותר למסלול לעבור בדרך.
| |||