PDA

צפה בגרסה המלאה : אוטומט מחסנית



sivan1256
09-01-2015, 18:21
איך אני עושה אוטומט לשפה הזאת:

$$ \begin{gathered}{0^i1^j2^k |i!=k , i,j,k>=o}\end{gathered} $$

antigravity
10-01-2015, 14:12
את לא. מאיפה השאלה?

אם קיים אוטומט מחסנית שזו שפתו, אז גם קיים אוטומט מחסנית לשפה $$ \begin{gathered}\{0^{i!}|i\geq0\}\end{gathered} $$ (וידוע שזה לא נכון).

sivan1256
10-01-2015, 17:29
לא ממש הבנתי..
הסימן =! אומר שזה שונה.. אז איך עושים אוטומט מחסנית כזה?

antigravity
10-01-2015, 18:11
הסימן =! אומר שונה במקומות שבהם אי-אפשר לכתוב $$ \begin{gathered}\neq\end{gathered} $$ (שזה לא הפורום הזה).

בכל מקרה, פתרון אפשרי הוא: (אני רושם את זה כאילו הקלט מהצורה $$ \begin{gathered}0^i1^j2^k\end{gathered} $$ , שכן קל לפסול קלטים מצורה אחת.)
נתחיל לקרוא אפסים, ועל כל אפס שנקרא נכניס סימן $ למחסנית.
אח"כ נעבור למצב שקורא אחדים.
כשיגיע 2, נעבור למצב שעל כל 2 שנקרא, מוציא סימן מהמחסנית.
אם הקלט נגמר ועדיין יש דולרים במחסנית, נקבל.
אם הקלט לא נגמר וגם לא נשארו דולרים במחסנית, נעבור למצב שמסיים לקרוא את הקלט ואז מקבל.
(ה"אם" הראשון מטפל במקרה $$ \begin{gathered}i>k\end{gathered} $$ , והשני במקרה $$ \begin{gathered}i<k\end{gathered} $$ . במצב השלישי, בו הקלט נגמר ואיתו התרוקנו הדולרים מהמחסנית, נדחה כמובן.)