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

[FigureSkater]

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

אשמח אם תוכלו לעזור לי עם השאלה הבאה: למילה w מעל {0,1} נגדיר N(w) את המלה המתקבלת מ w ע"י הפיכת כל 0 ל 1 וכל 1 ל 0. לשפה L מעל {0,1} נגדיר N(L) היא השפה שלוקחת כל מילה ב L והופכת אפס לאחד ואחד לאפס. בהינתן אוטומט סופי דטרמיניסטי A בנה באמצעותו אוטומט סופי דטרמיניסטי B המקבל את השפה L(A) – N(L(A)) thank you

 

[גיל14]

הרעיון הסטנדרטי

הרעיון הוא כזה: בנה אוטומט חדש B1 שבו הפכת בין כל 1 ו 0 בA. קח את B1 וצור ממנו B2 בו כל מצב שלא היה מקבל יהיה מקבל, וכל מצב שכן היה מקבל יהפןך ללא מקבל. קח את B2 ו A וצור אוטומט חיתוך.