שאלה בדקדוקים ואוטומטים..

[gilatb1]

שאלה בדקדוקים ואוטומטים..

אני צריכה את זה לבגרות מחר. אמרו לי שיש שיטה להפוך אוטומט לדקדוק, משהו עם לסמן את התחנות שבאוטומט באותיות [S,A].. מישהו יודע איך?

 

[Tomer878]

כן זה טריק טוב -

המצב הראשון (qo) יסומן בS, ואחריו כל מצב יסומן ב A B וכך הלאה.. כל אות על החץ שמעביר אותך מצב באוטומט תהיה אות שתכתב ליד האותיות ה A B של הדקדוק... תביאי תרגיל אני אראה לך איך.

 

[ron369]

זה לא טריק!

זו הוכחת השקילות של שני מודלים חישוביים מקובלים (ושימושיים!) ביותר

מה מלמדים אתכם בבי"ס?!

 

[lim1989]

לא רק

יש אוטומטים לא רק במודלים חישוביים, אלא גם בתורת המחשב.. ואז לא כולם מבינים את זה: זו הוכחת השקילות של שני מודלים חישוביים מקובלים

 

[ron369]

יש אוטומטים ודקדוקים בקומפילציה,

אז מה? ואגב, בעצם, זה הוכחה של אחד מהכיוונים בשקילות, אם כבר. הכיוון השני בכלל לא נחמד, אם אני זוכר נכון, ומשתמש בצורה הנורמלית של חומסקי, או משהו כזה (איכסה פיכסה).

 

[gilatb1]

הנה תרגיל..

 

[mEaS]

הרבה יותר קל להבין מה האוטומט מקבל

ואז לבנות דקדוק שיוצר את השפה הזאת. במקרה הזה האוטומט מקבל את שפת המילים מהצורה a^ib^j כאשר שאריות החלוקה של i וj ב3 שוות.

 

[gilatb1]

זה גם יכול להיות...?

a^j a^n b^n b^k כל האותיות >= 0 j,k mod 3=0 ?

 

[gilatb1]

זה אומר בעצם אותו דבר?

 

[mEaS]

כן זה אותו דבר.

 

[gilatb1]

אה אוקי..../images/Emo51.gif אבל

ידעתי מה השפהף פשוט נתתי דוגמא לאוטומט כדי שיראו לי מה השיטה להפוך אוטומט לדקדוק

 

[gilatb1]

../images/Emo35.gif

טוב, אני רואה שהרבה פה מכירים את השיטה, אז איך עושים אותה ככה..? [אני מראה על התרגיל שנתתי] קוראת לתחנות באותיות.. qo-->S q1-->A q2-->B q3-->C q4-->D q5-->E q6-->F ואז...לפי הציור מציירת את הדקדוק.. ז"א: S-->aA|bC A-->bD|aB B-->aS|bE C-->aF|bE D-->aF|bC E-->aF|bD ובתחנות שמקבלות אני שמה גם אפסילון.. אבל מה עם F? ממ.. זה יכול להיות סתם שטויות, אבל זאת השיטה במקרה? תודה

 

[gilatb1]

מישהו יודע?

 

[CaSsIe]

נראה לי..

תראי אני לא מכירה את השיטה אבל בקשר ל F: בגלל שQ6 הוא מצב מלכודת (אם הבנתי נכון) לא אמור להיות לו ייצוג בדקדוק משום שדקדוק אמור לקבל רק מילים שבשפה.

 

[gilatb1]

אה אז אני פשוט לא שולחת בכלל אותיות

לf? ז`א..אם האות הולכת להיתקע אני לא שולחת אותה,כן? ותודה