سلام
دوستان کسی میتونه این دو تا موضوع رو برام توضیح بده؟
بیشتر خارج قسمت راست رو متوجه نشدم.
توی کتاب لینز دو تا مثال زد متوجه نشدم.
خارج قسمت راست
اگه L1 و L2 دو زبان روی الفبای سیگما باشند، خارج قسمت راست L1 نسبت به L2 به صورت زیر نمایش داده می شود:
[tex]L1/L2=\{x|\: xy\: ∈\: L1\: and\: y\: ∈\: L2\}[/tex]
به طور مثال، اگه L1 برابر {ab,ba} باشه و L2 برابر {aab,baa,baba} باشه، حاصل L2/L1 برابر است با:
[tex]L2/L1=\{a,ba\}[/tex]
اگر متوجه نشدید بگید بیشتر توضیح بدم
هومومورفیسم:
هومومورفیستم در واقع یه تابع هست که الفبای یک زبان رو نگاشت میکنه به یه الفبا یا رشته ی دیگه. یعنی به جای هر کدوم از الفبای یک رشته از یک زبان، یک الفبای دیگه، یا حتی یک رشته قرار داده میشه. در نتیجه رشته های جدید حاصل میشه.
H: گاما* <- سیگما
دامنه ی تابع هومومورفیسم سیگما یعنی همون الفبای زبان هست.
برد تابع هومومورفیسم گاما* هست. یعنی الفبایی که هر حرفِ رشته ی زبان L، به یک یا چند تا از این الفبا نگاشت میشه.
[tex]H(L)=\{H(w)|\: w\in L\}[/tex]
مثال: زبان L و تابع هومومورفیسم H رو در نظر بگیرید.
L={ab, abb, b}A
{x,y}=گاما* (الفبای تابع هومومورفیسم) و
xy = H(a)v یعنی توی رشته های زبان L، به جای a، قرار بده xy.
x = H(b)b یعنی توی رشته های زبان L، به جای b، قرار بده x.
حالا: H(L)A برای این زبان چی میشه؟
H(L)={xyx,xyxx,x}A
یعنی اومدیم توی رشته های زبان L، به جای a، قرار دادیم xy و به جای b، قرار دادیم y
*خانواده ی زبان های منظم تحت عملگر هومومورفیسم بسته است. چرا؟ چون کافیه واسه منظم بودن زبان بشه واسه اون زبان یه DFA کشید. حالا وقتی واسه یه زبانی DFAداریم، وقتی میخوایم ماشین هومومورفیسم یافته ش رو بکشیم، کافیه توی همون DFA به جای هر یال، مقداری که هومورفیسم نگاشت میکنه رو بذاریم، مثلا به جای a بذاریم xy. در نتیجه یه DFA به دست میاد و زبان همچنان منظم هست.
خارج قسمت راست رو هم که دوستمون توضیح دادند.