הבדלים בין גרסאות בדף "אוטומט מחסנית"

אין שינוי בגודל ,  לפני שנה
ביטול גרסה 25794588 של יהונתן חרמץ (שיחה)
(←‏הגדרת קבלה: תיקון טעות)
(ביטול גרסה 25794588 של יהונתן חרמץ (שיחה))
 
ואילו השפה שמתקבלת על ידי ריקון המחסנית מוגדרת בתור:
*<math>\ L_e(M)=\left\{w\in\Sigma^*|\exists p\in FQ: \left(q_0,w,\dashv\right)\vdash^*\left( p,\varepsilon,\varepsilon\right)\right\}</math>
 
באופן כללי, יכול להיות ש- <math>\ L_f(M)\ne L_e(M)</math>; כלומר, שהשפה שהאוטומט מזהה על ידי הגעה למצב מקבל שונה מהשפה שהוא מזהה על ידי ריקון המחסנית. עם זאת, קיימת [[שקילות (מתמטיקה)|שקילות]] בין שני אופני הקבלה: אם שפה כלשהי <math>\ L</math> מזוהה על ידי הגעה למצב מקבל בידי אוטומט מחסנית כלשהו, קיים אוטומט מחסנית (לא בהכרח אותו אחד) שמזהה את השפה <math>\ L</math> על ידי ריקון המחסנית, ולהפך. כמובן, שניתן גם להגדיר את השפה שהאוטומט מקבל כ[[איחוד (מתמטיקה)|איחוד]] שתי דרכי הגדרות הקבלה: <math>\ L_f(M)\cup L_e(M)</math>.
350

עריכות