۰
subtitle
ارسال: #۱
خواص زبان dcf
سلام دوستان
زبان های DCF نسبت به الحاق و بستار ستاره ای بسته هستن؟
بچه‌ها لطفا با اثباتکی(چیزی شبیه اثبات)، مثال نقضی توضیح بدین که تو ذهنمون بمونه.
مرسی
زبان های DCF نسبت به الحاق و بستار ستاره ای بسته هستن؟
بچه‌ها لطفا با اثباتکی(چیزی شبیه اثبات)، مثال نقضی توضیح بدین که تو ذهنمون بمونه.
مرسی
۰
ارسال: #۲
خواص زبان dcf
من زبانهای CFL رو میدونم این دو خاصیت رو دارن اونم به این صورت:
طبق الحاق بسته است چون میتونیم دو تا زبان که داریم که یکی با S1 , دیگری با S2 شروع میشه رو به صورت S--->S1S2 بنویسیم.
برای بستار ستاره ای هم میتونیم S---->SS بنویسیم که باز همینو میشه یکی از S های سمت راست رو SSبا جایگزین کرد و نوشت S---->SSS و الی آخر
طبق الحاق بسته است چون میتونیم دو تا زبان که داریم که یکی با S1 , دیگری با S2 شروع میشه رو به صورت S--->S1S2 بنویسیم.
برای بستار ستاره ای هم میتونیم S---->SS بنویسیم که باز همینو میشه یکی از S های سمت راست رو SSبا جایگزین کرد و نوشت S---->SSS و الی آخر
۰
ارسال: #۳
RE: خواص زبان dcf
دو زبان زیر رو در نظر بگیرید:
[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]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close