سلام دوستان
زبان های DCF نسبت به الحاق و بستار ستاره ای بسته هستن؟
بچه‌ها لطفا با اثباتکی(چیزی شبیه اثبات)، مثال نقضی توضیح بدین که تو ذهنمون بمونه.
مرسی
من زبانهای CFL رو میدونم این دو خاصیت رو دارن اونم به این صورت:
طبق الحاق بسته است چون میتونیم دو تا زبان که داریم که یکی با S1 , دیگری با S2 شروع میشه رو به صورت S--->S1S2 بنویسیم.
برای بستار ستاره ای هم میتونیم S---->SS بنویسیم که باز همینو میشه یکی از S های سمت راست رو SSبا جایگزین کرد و نوشت S---->SSS و الی آخر
دو زبان زیر رو در نظر بگیرید:
[tex]L_{1} = \{ w\in \{a,b\}^{*}\mid n_{a}(w)=n_{b}(w) \}[/tex]
[tex]L_{2} = \{ w\in \{a,b\}^{*}\mid n_{a}(w)=2n_{b}(w) \}[/tex]
L1,L2 مستقل از متن قطعی هستند اما اتصال آن‌ها مستقل از متن قطعی نیست چون اگر w متعلق به L1.L2 باشه که در اون w=uv اونوقت u متعلق به L1 و v متعلق به L2 هست و هیچ DPDA برای L1.L2 وجود ندارد که بتونه مرز بین u و v رو بو صورت قطعی مشخص کنه.
[tex]L_{2} = \{ w\in \{a,b\}^{*}\mid n_{a}(w)=2n_{b}(w) \}[/tex]