03-11-2010, 13:56
|
|
|
|
חבר מתאריך: 30.08.09
הודעות: 2,880
|
|
זה נורא פשוט, אתה כביכול נותן למחשב "מנגנון" שלפי הכללים שלו ייקבע אם שפה התקבלה או לא.
אם לאחר הכנסת הקלט אתה נמצא במצב לא מקבל, אז הקלט הוא לא חלק מהשפה וההיפך.
למשל האוטומט הבא (מויקיפדיה):
הא"ב של השפה הוא: 1,0
השפה עצמה היא: כל מילה שבה מספר המופעים של 0 הוא זוגי.
העיגול הכפול במצב q0 מסמל מצב מקבל, כמו כן זה גם המצב ההתחלתי.
אז ניקח לדוגמה את הקלט 0101: אתה נכנס למצב q0 ורואה שאתה צריך לנוע ל-q1, כי החץ
עם הספרה 0 מוביל לq1, אח"כ אתה מתקדם ל0101, ורואה שהחץ עם 1 מורה עליך להישאר במצב q1, וכך הלאה...
אם סיימת לעבור על כל האותיות ואתה במצב מקבל -> השפה התקבלה (והפוך).
תנסה עכשיו לפתור את התרגיל שנתנו לך, אם לא תצליח אני כאן לעזור P:
|