۰
subtitle
ارسال: #۱
چرا زبان uww^Rv منظمه؟ حل شد
قول میدم این سوال آخری باشه که امروز میپرسم.
این زبان به نظر خودم منظم نیست. نظر دوستان چیه؟
[tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
فکر کنم مشکل من با اون + باشه و نتونستم درست متوجه بشم.
این زبان به نظر خودم منظم نیست. نظر دوستان چیه؟
[tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
فکر کنم مشکل من با اون + باشه و نتونستم درست متوجه بشم.
۱
ارسال: #۲
RE: چرا زبان uww^Rv منظمه؟ حل شد
فکر کنم راه حل اشتباهی بود چون این زبان سیگما پلاس نیست
چون اگه سیگما پلاس باشه باید بتونه رشته abab را بسازه در صورتی که اینجور نیست
بلکه این یه زبانیه که حتما باید وسطش یه چیز قرینه بیاد و اول آخرش دیگه مهم نیست چی باشه
مثلا فرض که w=Sa (برای Sb هم به همین شکل اثبات میشه) و [tex]w^{R}[/tex] هم میشه aS. که S هر ترکیبی از a,b هست.
پس رشته ما به شکل زیر در میاد
[tex]uSaaSv[/tex]
پس زبان به شکل زیر در میاد که
[tex](a b)^{ } (a b)^{*} aa (a b)^{*} (a b)^{ }[/tex]
و در نتیجه میشه به شکل زیر با استفاده از این قانون که [tex]\sum^{*}.\sum^{ }=\sum^{ }[/tex]
[tex](a b)^{ } aa (a b)^{ }[/tex]
خب این زبان هم مشخصه که منظمه . یعنی اول و آخرش هر چی خواست بیاد، فقط وسطش حتما یکی از حالتهای aa یا bb اومده باشه
پس ما به اشتباه نتیجه گرفتیم که زبان بالا میشه سیگما پلاس
چون اگه سیگما پلاس باشه باید بتونه رشته abab را بسازه در صورتی که اینجور نیست
بلکه این یه زبانیه که حتما باید وسطش یه چیز قرینه بیاد و اول آخرش دیگه مهم نیست چی باشه
مثلا فرض که w=Sa (برای Sb هم به همین شکل اثبات میشه) و [tex]w^{R}[/tex] هم میشه aS. که S هر ترکیبی از a,b هست.
پس رشته ما به شکل زیر در میاد
[tex]uSaaSv[/tex]
پس زبان به شکل زیر در میاد که
[tex](a b)^{ } (a b)^{*} aa (a b)^{*} (a b)^{ }[/tex]
و در نتیجه میشه به شکل زیر با استفاده از این قانون که [tex]\sum^{*}.\sum^{ }=\sum^{ }[/tex]
[tex](a b)^{ } aa (a b)^{ }[/tex]
خب این زبان هم مشخصه که منظمه . یعنی اول و آخرش هر چی خواست بیاد، فقط وسطش حتما یکی از حالتهای aa یا bb اومده باشه
پس ما به اشتباه نتیجه گرفتیم که زبان بالا میشه سیگما پلاس
ارسال: #۳
RE: چرا زبان uww^Rv منظمه؟ حل شد
(۰۸ مهر ۱۳۹۲ ۰۳:۱۱ ب.ظ)zimenswall نوشته شده توسط: پس زبان به شکل زیر در میاد که
[tex](a b)^{ } (a b)^{*} aa (a b)^{*} (a b)^{ }[/tex]
و در نتیجه میشه به شکل زیر با استفاده از این قانون که [tex]\sum^{*}.\sum^{ }=\sum^{ }[/tex]
[tex](a b)^{ } aa (a b)^{ }[/tex]
بله درست میگید، پاسخ خودتون کاملتره:
[tex](a b)^{ } (aa bb) (a b)^{ }[/tex]
ارسال: #۴
RE: چرا زبان uww^Rv منظمه؟ حل شد
(۰۸ مهر ۱۳۹۲ ۰۵:۳۳ ب.ظ)Ghiasoddin نوشته شده توسط:(08 مهر ۱۳۹۲ ۰۳:۱۱ ب.ظ)zimenswall نوشته شده توسط: پس زبان به شکل زیر در میاد که
[tex](a b)^{ } (a b)^{*} aa (a b)^{*} (a b)^{ }[/tex]
و در نتیجه میشه به شکل زیر با استفاده از این قانون که [tex]\sum^{*}.\sum^{ }=\sum^{ }[/tex]
[tex](a b)^{ } aa (a b)^{ }[/tex]
بله درست میگید، پاسخ خودتون کاملتره:
[tex](a b)^{ } (aa bb) (a b)^{ }[/tex]
ممنون از شما که در بحث شرکت کردید.
باز هم مثل اون چندتا سوال قبلی که پرسیده بودم زیادی ذهنم به سیگما بودن زبان متوجه میشد و اینبار هم همینطور شد.
در کل هرچند سیگما شدن زبان یکی از راههای خوب واسه تشخیص نوع زبان هست ولی امثال من که دقت کافی ندارن باید دقتشون را بالا ببرن که سوال را اشتباه حل نکنند
۰
ارسال: #۵
RE: چرا زبان uww^Rv منظمه؟
(۰۷ مهر ۱۳۹۲ ۰۸:۴۶ ب.ظ)zimenswall نوشته شده توسط: قول میدم این سوال آخری باشه که امروز میپرسم.
این زبان به نظر خودم منظم نیست. نظر دوستان چیه؟
[tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
فکر کنم مشکل من با اون + باشه و نتونستم درست متوجه بشم.
در یکی دو تا تاپیک سوالای مشابه این بحث شده؛
مثلا یه راه ساده اینه که اول اون قسمت wwr رو بزارید کنار؛ چیزی که باقی میمونه u در اول و v در آخر هر کدوم به تنهایی قادر سیگما پلاس رو تولید کنن؛ بنابراین الحاق اونها هم میشه سیگما پلاس؛ بزرگترین مجموعه ای که میشه با حروف الفبای یه زبان ساخت سیگما استاره؛ از طرفی سیگما پلاس فقط یه لاندا از سیگما استار کمتر داره؛ حالا وقتی اون قسمت wwr رو اضافه بکنید، از اونجایی که w نمیتونه لاندا باشه، زبان حاصل بزرگتر از همون سیگما پلاس نخواهد بود (سیگما پلاس هم که منظمه)؛
ارسال: #۶
RE: چرا زبان uww^Rv منظمه؟
(۰۷ مهر ۱۳۹۲ ۱۰:۴۷ ب.ظ)Ghiasoddin نوشته شده توسط:(07 مهر ۱۳۹۲ ۰۸:۴۶ ب.ظ)zimenswall نوشته شده توسط: قول میدم این سوال آخری باشه که امروز میپرسم.
این زبان به نظر خودم منظم نیست. نظر دوستان چیه؟
[tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
فکر کنم مشکل من با اون + باشه و نتونستم درست متوجه بشم.
در یکی دو تا تاپیک سوالای مشابه این بحث شده؛
مثلا یه راه ساده اینه که اول اون قسمت wwr رو بزارید کنار؛ چیزی که باقی میمونه u در اول و v در آخر هر کدوم به تنهایی قادر سیگما پلاس رو تولید کنن؛ بنابراین الحاق اونها هم میشه سیگما پلاس؛ بزرگترین مجموعه ای که میشه با حروف الفبای یه زبان ساخت سیگما استاره؛ از طرفی سیگما پلاس فقط یه لاندا از سیگما استار کمتر داره؛ حالا وقتی اون قسمت wwr رو اضافه بکنید، از اونجایی که w نمیتونه لاندا باشه، زبان حاصل بزرگتر از همون سیگما پلاس نخواهد بود (سیگما پلاس هم که منظمه)؛
تشکر
اول اینکه تو انجمن سخت میشه اینجور سوالها رو پیدا کرد چون معمولا تیتر سوالها مبین خود سوال نیست و اگه تکراری بود شرمنده
دوم اینکه اینطور که شما میگید کاربرد سیگما پلاس در اثبات منظم بودن زبانها مثل سیگما استار هست. یعنی اگه تونستیم اثبات کنیم که یه زبانی سیگما استار یا سیگما پلاس بشه پس منظمه.
ارسال: #۷
RE: چرا زبان uww^Rv منظمه؟
ارسال: #۸
RE: چرا زبان uww^Rv منظمه؟ حل شد
(۰۷ مهر ۱۳۹۲ ۱۰:۴۷ ب.ظ)Ghiasoddin نوشته شده توسط:(07 مهر ۱۳۹۲ ۰۸:۴۶ ب.ظ)zimenswall نوشته شده توسط: [tex]uww^{R}v : u,v,w\in \left \{ a,b \right \}^{ }[/tex]
مثلا یه راه ساده اینه که اول اون قسمت wwr رو بزارید کنار؛
یه شبهه ای برام پیش اومده، اینکه آیا ما میتونیم ww^R را کنار بذاریم و به این نتیجه برسیم که سیگما پلاسه؟
آخه طول w نمیتونه صفر باشه و کنار گذاشتنش به نظرم منطقی نمیاد
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close