27 آبان 1389, 08:03 ب.ظ
28 آبان 1389, 01:05 ق.ظ
من زبانهای CFL رو میدونم این دو خاصیت رو دارن اونم به این صورت:
طبق الحاق بسته است چون میتونیم دو تا زبان که داریم که یکی با S1 , دیگری با S2 شروع میشه رو به صورت S--->S1S2 بنویسیم.
برای بستار ستاره ای هم میتونیم S---->SS بنویسیم که باز همینو میشه یکی از S های سمت راست رو SSبا جایگزین کرد و نوشت S---->SSS و الی آخر
طبق الحاق بسته است چون میتونیم دو تا زبان که داریم که یکی با S1 , دیگری با S2 شروع میشه رو به صورت S--->S1S2 بنویسیم.
برای بستار ستاره ای هم میتونیم S---->SS بنویسیم که باز همینو میشه یکی از S های سمت راست رو SSبا جایگزین کرد و نوشت S---->SSS و الی آخر
28 آبان 1389, 02:01 ق.ظ
دو زبان زیر رو در نظر بگیرید:
[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]