(۱۰ بهمن ۱۳۹۲ ۰۷:۰۲ ب.ظ)Jooybari نوشته شده توسط:  سلام. باز هم میگم به تشابه این زبانها دقت کنید: (اگه TEX مشکل داشت روی ارسالم دکمه پاسخ رو بزنید تا کد رو ببینید.)

[tex]L=\{w_1cw_2|w_1=w_2\}[/tex]

روی الفبای a,b حساس به متنه. روی a,b,c هم حساس به متنه.

[tex]L=\{w_1cw_2|w_1\neq w_2\}[/tex]

روی الفبای a,b مستقل ازمتن و روی الفبای a,b,c منظمه.

[tex]L=\{w_1w_2|w_1=w_2\}[/tex]

حساس به متنه.

[tex]L=\{w_1w_2|w_1\neq w_2\}[/tex] (با شرط برابری طول دو زیررشته.)

مستقل از متنه.

(۱۸ بهمن ۱۳۹۲ ۰۷:۲۳ ب.ظ)zahra2012 نوشته شده توسط:  

(10 بهمن ۱۳۹۲ ۰۷:۰۲ ب.ظ)Jooybari نوشته شده توسط:  سلام. باز هم میگم به تشابه این زبانها دقت کنید: (اگه TEX مشکل داشت روی ارسالم دکمه پاسخ رو بزنید تا کد رو ببینید.)

[tex]L=\{w_1cw_2|w_1=w_2\}[/tex]

روی الفبای a,b حساس به متنه. روی a,b,c هم حساس به متنه.

[tex]L=\{w_1cw_2|w_1\neq w_2\}[/tex]

روی الفبای a,b مستقل ازمتن و روی الفبای a,b,c منظمه.

[tex]L=\{w_1w_2|w_1=w_2\}[/tex]

حساس به متنه.

[tex]L=\{w_1w_2|w_1\neq w_2\}[/tex] (با شرط برابری طول دو زیررشته.)

مستقل از متنه.

خیلی ممنون
در مورد دوم چرا با الفبای a,b,c منظم هست؟

(۱۹ بهمن ۱۳۹۲ ۰۱:۴۵ ق.ظ)Jooybari نوشته شده توسط:  

(18 بهمن ۱۳۹۲ ۰۷:۲۳ ب.ظ)zahra2012 نوشته شده توسط:  

(10 بهمن ۱۳۹۲ ۰۷:۰۲ ب.ظ)Jooybari نوشته شده توسط:  سلام. باز هم میگم به تشابه این زبانها دقت کنید: (اگه TEX مشکل داشت روی ارسالم دکمه پاسخ رو بزنید تا کد رو ببینید.)

[tex]L=\{w_1cw_2|w_1=w_2\}[/tex]

روی الفبای a,b حساس به متنه. روی a,b,c هم حساس به متنه.

[tex]L=\{w_1cw_2|w_1\neq w_2\}[/tex]

روی الفبای a,b مستقل ازمتن و روی الفبای a,b,c منظمه.

[tex]L=\{w_1w_2|w_1=w_2\}[/tex]

حساس به متنه.

[tex]L=\{w_1w_2|w_1\neq w_2\}[/tex] (با شرط برابری طول دو زیررشته.)

مستقل از متنه.

خیلی ممنون
در مورد دوم چرا با الفبای a,b,c منظم هست؟

عذرخواهی میکنم. یکم عجله کردم. اگه رشته کلی حداقل ۲ تا c داشت منظم میشد. در غیر این صورت مستقل از متنه.

(۱۹ بهمن ۱۳۹۲ ۰۱:۵۴ ب.ظ)zahra2012 نوشته شده توسط:  یعنی با الفبای {a,b,c} و به این شکل

w1ccw2 که w1 مساوی w2 نیست

منظم هست؟ میشه بگین چرا ؟

(۱۰ بهمن ۱۳۹۲ ۰۱:۱۷ ب.ظ)helena نوشته شده توسط:  در مورد ww: وسط رشته رو نمیتونیم پیدا کنیم. از کجا بدونیم الان رسیدیم وسط رشته ؟!

اگر wcw در نظر بگیریم ، c در حالت اول فقط کمک میکنه وسط رشته رو پیدا کنیم . ولی باز هم مشکل داریم. ساختار LIFO پشته رو تصور کنید. هر حرفی از رشته رو که میخونیم توی پشته push میکنیم. ولی وقتی تا وسط رشته رفتیم چه طوری pop کنیم ؟! از آخرین عنصری که push کردیم pop میشه ، بنابراین رشته درست در نمیاد.
مثلا رشته abbcabb رو در نظر میگیریم. abb توی پشته push میشه .حالا که pop کنیم bba میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متنه.

(۱۰ بهمن ۱۳۹۲ ۰۳:۱۲ ب.ظ)zahra2012 نوشته شده توسط:  

(10 بهمن ۱۳۹۲ ۰۱:۱۷ ب.ظ)helena نوشته شده توسط:  در مورد ww: وسط رشته رو نمیتونیم پیدا کنیم. از کجا بدونیم الان رسیدیم وسط رشته ؟!

اگر wcw در نظر بگیریم ، c در حالت اول فقط کمک میکنه وسط رشته رو پیدا کنیم . ولی باز هم مشکل داریم. ساختار LIFO پشته رو تصور کنید. هر حرفی از رشته رو که میخونیم توی پشته push میکنیم. ولی وقتی تا وسط رشته رفتیم چه طوری pop کنیم ؟! از آخرین عنصری که push کردیم pop میشه ، بنابراین رشته درست در نمیاد.
مثلا رشته abbcabb رو در نظر میگیریم. abb توی پشته push میشه .حالا که pop کنیم bba میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متنه.

پس مستقل از متن نیستن ؟؟!!!!

(۱۰ بهمن ۱۳۹۲ ۰۳:۲۸ ب.ظ)helena نوشته شده توسط:  

(10 بهمن ۱۳۹۲ ۰۳:۱۲ ب.ظ)zahra2012 نوشته شده توسط:  

(10 بهمن ۱۳۹۲ ۰۱:۱۷ ب.ظ)helena نوشته شده توسط:  در مورد ww: وسط رشته رو نمیتونیم پیدا کنیم. از کجا بدونیم الان رسیدیم وسط رشته ؟!

اگر wcw در نظر بگیریم ، c در حالت اول فقط کمک میکنه وسط رشته رو پیدا کنیم . ولی باز هم مشکل داریم. ساختار LIFO پشته رو تصور کنید. هر حرفی از رشته رو که میخونیم توی پشته push میکنیم. ولی وقتی تا وسط رشته رفتیم چه طوری pop کنیم ؟! از آخرین عنصری که push کردیم pop میشه ، بنابراین رشته درست در نمیاد.
مثلا رشته abbcabb رو در نظر میگیریم. abb توی پشته push میشه .حالا که pop کنیم bba میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متنه.

پس مستقل از متن نیستن ؟؟!!!!

با استدلالی که من کردم نه ، مستقل از متن نیستن.

(۱۶ بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)helena نوشته شده توسط:  من الان دچار تناقض شدم با حرفی که خودم زدم !!!
WWR چه طوری مستقل از متنه ؟!‌ با پشته که پیش میریم از کجا میفهمه که رسیدیم وسط رشته باید pop کنه ؟!!!!!!

(۱۷ بهمن ۱۳۹۲ ۰۱:۰۹ ق.ظ)Jooybari نوشته شده توسط:  

(16 بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)helena نوشته شده توسط:  من الان دچار تناقض شدم با حرفی که خودم زدم !!!
WWR چه طوری مستقل از متنه ؟!‌ با پشته که پیش میریم از کجا میفهمه که رسیدیم وسط رشته باید pop کنه ؟!!!!!!

مستقل از متن غیرقطعیه. ماشین خودش باید تمام حالات ممکن برای وسط بودن رشته رو چک کنه (بیچاره! گناه داره ) تا بتونه در یه حالتی به جواب برسه. اگه توی یکی از حالات به حالت نهایی رسید رشته پذیرفتست. این خاصیت غیرقطعیه.