2 דברים בסיסיים
2 שאלות:
1) בהינתן אלג' לא דטרמיניסטי להכרעת שפה L, אם קלט x לא שייך ל-L, אז כל מסלולי החישוב של האלגוריתם על x, עוצרים במצב דחייה?
או שאפשר לומר שכל המסלולים לא מאשרים (ואז אני מרשה שיהיו מסלולים שלא יעצרו)?
2) איך אני מסביר את זה:
בניגוד לאלגוריתמים דטרמיניסטיים, החלפת מצבי הדחייה והקבלה באלגוריתם הכרעה לא דטרמיניסטי, אינה יוצרת אלגוריתם ל"ד להערכת השפה המשלימה.
למה זה נכון?
2 שאלות:
1) בהינתן אלג' לא דטרמיניסטי להכרעת שפה L, אם קלט x לא שייך ל-L, אז כל מסלולי החישוב של האלגוריתם על x, עוצרים במצב דחייה?
או שאפשר לומר שכל המסלולים לא מאשרים (ואז אני מרשה שיהיו מסלולים שלא יעצרו)?
2) איך אני מסביר את זה:
בניגוד לאלגוריתמים דטרמיניסטיים, החלפת מצבי הדחייה והקבלה באלגוריתם הכרעה לא דטרמיניסטי, אינה יוצרת אלגוריתם ל"ד להערכת השפה המשלימה.
למה זה נכון?