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

[FigureSkater]

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

נתונים לי שני ביטויים רגולריים א. *(0+1) ב. (01*)*(10*)*)*) איך אני מוכיח שהם שקולים?

 

[FigureSkater]

תיקון

הנה שני הביטויים א. *(1+0) ב. *(*(*10)*(*01)) איך מוכיחים שהם מייצגים את אותה השפה? באינדוקציה? איך?

 

[yuvalmadar]

אינדוקציה זה רעיון טוב

אתה רוצה להוכיח בעצם שכל מילה בינארית ניתנת להצגה על ידי הביטוי השמאלי. תשתמש באינדוקציה על אורך המילה. (ניתן לתאר כל מילה כ-0x או כ-1x כאשר x מילה באורך הקצר באחד)

 

[FigureSkater]

אפשר להראות לי..

איך עושים את זה באופן פורמלי? תודה רבה מראש