הוכחת רגולריות

[FigureSkater]

הוכחת רגולריות

נתונים השפות L רגולרית ו R לא-רגולרית כך ש R חלקית ל L האם L פחות R רגולרית? תודה לעונים

 

[Okuryo]

../images/Emo119.gifייתכן שכן וייתכן שלא...

אם L היא השפה הריקה, אז L\R רגולרית לכל R. אם *L=Σ, אז L\R אינה רגולרית לכל R שאינה רגולרית.

 

[FigureSkater]

הוכחה

מה ההוכחה? ומה שכתבת לגבי השפה הריקה- אם תשים לב השפה הריקה לא מקיימת את תנאי השאלה

 

[FigureSkater]

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

ניסוח חדש: נתונים השפות R ו L כך ש R חלקית ל L, ו R לא רגולרית ו L רגולרית. הוכח או הפרך : L-R רגולרית

 

[Okuryo]

../images/Emo119.gifאוקיי, זה משהו אחר ../images/Emo11.gif

L-R לא רגולרית, כי

R = ( ( L - R ) - L ) ∪ ( L - ( L - R ) ) = ( L - R ) Δ L​

ומהסגירות להפרש סימטרי, אם L-R רגולרית וגם L רגולרית אז R רגולרית.

 

[גיל14]

../images/Emo45.gif