سلام
توی کتاب سودکمپ نوشته
فرض کنید که [tex]u,v\in \Sigma ^*[/tex] باشد. الحاق u و v ، که بصورت uv نوشته می شود، یک عمل دودویی روی [tex]\Sigma ^*[/tex] است که به صورت زیر تعریف می شود:
i) پایه: اگر Length(v)=0 باشد انگاه [tex]v=\lambda[/tex] و uv=u خواهد بود.
ii) گام بازگشت: فرض کنید که v یک رشته با طول length(v)=n>0 باشد.در اینصورت به ازای برخی رشته های w با طول n-1 و [tex]a\in \Sigma[/tex] ، v=wa و در نتیجه uv=(uw)a خواهد بود.
یکی به زبان ساده به من این چیزارو بفهمونه
۱-یک عمل دودویی یعنی چی؟
۲-گام بازگشت داره میگه که ما در هر بار اجرای این گام یک حرف از سمت راست v جدا می کنیم که نتیجه میشه wa و باز این گام رو برای w تکرار میکنیم تا جایی که به length(w)=0 برسیم و در اون صورت w نهایی که طولش صفر شده به u الحاق شده و تشکیل uw=u رو خواهد داد.آیا برداشت من درسته؟
با سلام
جواب سوال اولی که پرسیدید که عمل دودویی چیه؛ عمل دودویی عملی هست که روی دو تا عملوند عمل می کنه. مثلا جمع،تفریق،ضرب از مثال های عمل دودویی هستند،(اینجا همون طور که می بینید داره روی دو تا واژه یعنی u و v عمل صورت می گیره) در مقابل عمل یکانی که فقط روی یک عملوند انجام میشه، مثل عملگر منفی که یک عدد رو قرینه میکنه.
در پاسخ به سوال دوم شما فکر کنم که برداشتتون اشتباه بوده یا برداشت من از برداشت شما اشتباه هست. دقت کنید که تعریف برای الحاق v و u هست نه w و u.
خلاصه و شسته و رفته ی مفهوم گام بازگشتی که تعریفشو در بالا آورده اید این میشه که : می گیم v به u الحاق شده(چسبیده شده
) وقتی که به صورت بازگشتی یکی یکی حرف های v رو ازش کند(جدا کرد) و این عمل رو تکرار کرد تا جایی که فقط همون u بمونه.
یه توصیه به شما دوست عزیز :
مطالب نظریه رو از روی کتاب لینز ترجمه مهندس صراف زاده بخونید و فقط بحث ماشینهای پشته ای و عبارت های منظم و پیچیدگی محاسباتی رو از روی سودکمپ بخونید . بسیار روی حل تمرینات لینز توصیه دارم .
در مورد الحاق هم تعریف راحتی هستش یعنی دو رشته رو بهم بچسبونی تا تبدیل به یه رشته جدید شه . حالا دوستمون هم کاملتر گفتن موضوع رو .
سلام
من سر کلاس وقتی استاد می گفت الحاق یعنی چسباندن دو تا رشته به هم خوب برام خیلی واضح و بدیهی بود.کما اینکه توی برنامه نویسی بارها با رشته ها و الحاقشون و این چیزا کار کردم.اما وقتی تعریف ریاضی سودکپ رو خوندم برام ملموس نبود.خواستم ملموس بشه برام!وگرنه دیگه الحاق چیه که کسی متوجه ش نشه!
یبار دیگه تعریف رو خوندم.فکر کنم منظور تعریف اینه که الحاق یعنی دوتا شته رو کنار هم بگذای جوری که اخرین حرف سمت راست رشته اول به اولین حرف سمت چپ رشته دوم بچسبه.
مثلا تصور کنید طول رشته دوم ۱ باشه v=wa که در اینجا طول w برابر ۰ است لذا داریم [tex]uv=uwa=(uw)a=ua[/tex]
و به همین ترتیب...
فکر کنم زیادی گیر دادم به تعاریف.
ممنون از راهنمایی
راستی اینم بگم چون درس مورد علاقه م بود و هست واستم اساسی یاد بگیرم جوری که بتونم یروز به دانشجوهام خوب یادش بدم!(ارزو بر جوانان عیب نیست!) و اینکه وقتی یکی ازم سوال پرسید مثل استادای خوبم بدونم گیر دانشجوم کجاست و به راحتی گیرشو رفع کنم و گیجش نکنم.
بازم ممنون