مساله Prolan

یک زبان برنامه نویسی به نام Prolan را به این شکل تعریف میکنیم:

هر برنامه به زیان Prolan دنباله ای از دستورات به شکل (s1,s2) است که در آن s1 و s2 دو رشته از نویسه ها (کاراکتر ها) هستند. برای اجرای یک دستور از زبان Prolan مانند (s1,s2) یک رشته به عنوان رشته ورودی به آن داده می شود و اگر زیر رشته s1 در رشته ورودی وجود داشت، این زیر رشته در اولین محلی که در رشته ورودی ظاهر شود تبدیل به s2 خواهد شد و اگر رشته s1 در رشته ورودی موجود نباشد، دستور (s1,s2) بر روی این رشته اجرا نخواهد شد. به عنوان مثال نتیجه اجرای دستور (ab,xa) روی رشته ababab، رشته xaaabab است. توجه کنید که همین دستور بر روی رشته bacb قابل اجرا نیست، چون زیر رشته ab در آن وجود ندارد.

یک برنامه به زبان به زبان Prolan به این شکل اجرا می شود: در ابتدا یک رشته به عنوان ورودی به آن برنامه داده می شود و این رشته در طی مراحلی تغییر می یابد. در هر مرحله اولین دستور قابل اجرای برنامه بر روی رشته اجرا می شود و آن را تغییر می دهد. پس از آن دوباره رشته تغییر یافته به شروع برنامه بر میگردد و مرحله قبل روی آن انجام میشود. کار تا آنجا ادامه پیدا میکند که دستور قابل اجرایی بر روی رشته خاصل در برنامه موجود نباشد. در این هنگام رشته حاصل خروجی برنامه میباشد.

1. روی زبان Prolan مسائل جالبی مطرح میشود که آنها را به مرور در این تاپیک خواهم آورد. توجه آنکه این زبان صرفا ارزش تئوری دارد و بدرد ارضای حس مبارزه طلبی میخورد. (مبارزه طلباش بیان جلو :P )

2. یک مثال:
برنامه زیر را در نظر بگیرید:

(a,bc)

(ccc,x)

(cb,bc)

(xb,mba)

نتیجه اجرای برنامه فوق بر روی رشته xacab خواهد بود:

نتیجه              رشته اولیه              دستور 

(a,bc)             xacab                   xbccab 

(a,bc)             xbccab                  xbccbcb 

(cb,bc)            xbccbcb                 xbcbccb 

(cb,bc)            xbcbccb                 xbbcccb 

(ccc,x)            xbbcccb                 xbbxb 

(xb,mba)           xbbxb                   mbabxb 

(a,bc)             mbabxb                  mbbcbxb 

(cb,bc)            mbbcbxb                 mbbbcxb 

(xb,mba)           mbbbcxb                 mbbbcmba 

(a,bc)             mbbbbcmba               mbbbcmbbc 

و خروجی برنامه رشته mbbbbcmbbc خواهد بود.

3. اصل مساله مال فصلنامه المپیاد/ پاییز 73 میباشد

4. مفسر Prolan در ضمیمه آمده است.

اگه حاضرید، اولین مساله رو پست کنم :)

بابا حاضریم::: :موافق:
فکر کنم من یکم ساده ترشو تو کتاب Complexity and compution در قسمت ماشین تورینگ دیدم.

ممنون

مساله اول
برنامه ای به زبان Prolan بنویسید که رشته ورودی به صورت <s> که s رشته ای ار نویسه های a و b است را دریافت کند و آنرا به رشته ss تبدیل کند.
مثال: برنامه شما باید <abb> را به abbabb تبدیل کند.

موفق باشید :)

من که تو همین مسئله اول گیر کردم. :)
حالا شاید اگر راه حل این مسئله رو بگی، دو زاریم بیفته که جریان از چه قراره. :wink:

اینهم راه حل مساله اول:

a1,1a

a2,2a

b1,1b

b2,2b

1,A

2,B

<a,a1<

<b,b2<

<>,

A,a

B,b

اندکی تحلیل:
مرحله اول(خطوط 7 و 8 ) : کشیدن تک تک کاراکترها به بیرون از پرانتز و افزودن کاراکتر اضافی ( 1 به جای a و 2 به جای b)
مرحله دوم (خطوط 1 تا 4): بردن کاراکترهای اضافه شده 1 و 2 به دست چپ
مرحله سوم (خطوط 5 و 6): برای جلوگیری از انتقال بیش از حد نویسه های 1و2 به سمت چپ. (اگر این مرحله نباشد، بعد از اینکه در مرحله آخر شروع به تعویض 1و 2 با a و b می کنیم، قرو قاطی میشه.... :? )
مرحله آخر (3 خط آخر): تعویض نهایی کاراکترها

می بخشید که یه کم بد توضیح دادم، اما تشریح الگوریتمای Prolan به علت غیر خطی بودن اونها واقعا سخته. :cry: اما فکر کنم اگه الگوریتم رو trace کنین قضیه کاملا جا بیفته (از سوییچ d استفاده کنید)

مساله دوم

برنامه ای به زبان Prolan بنویسید که رشته ورودی به شکل <s> که s رشته ای از نویسه های a و b است را دریافت کند و آنرا وارون کند.
مثال: برنامه شما باید رشته <aaba> را به رشته abaa تبدیل نماید.

موفق باشید :)