زبان wcw اگر الفبا به دو صورت زیر باشد در هر کدوم مستقل هست یا نه؟
1) (a,b)*
2) (a,b,c)*
بعد میشه بگین ww چه جوری با پشته ثابت می کنیم مستقل از متن نیست با لم تزریقو می فهمم ممنون میشم .
در مورد ww: وسط رشته رو نمیتونیم پیدا کنیم. از کجا بدونیم الان رسیدیم وسط رشته ؟!
اگر wcw در نظر بگیریم ، c در حالت اول فقط کمک میکنه وسط رشته رو پیدا کنیم . ولی باز هم مشکل داریم. ساختار LIFO پشته رو تصور کنید. هر حرفی از رشته رو که میخونیم توی پشته push میکنیم. ولی وقتی تا وسط رشته رفتیم چه طوری pop کنیم ؟! از آخرین عنصری که push کردیم pop میشه ، بنابراین رشته درست در نمیاد.
مثلا رشته abbcabb رو در نظر میگیریم. abb توی پشته push میشه .حالا که pop کنیم bba میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متن نیست.
(10 بهمن 1392 01:17 ب.ظ)helena نوشته شده توسط: [ -> ]در مورد ww: وسط رشته رو نمیتونیم پیدا کنیم. از کجا بدونیم الان رسیدیم وسط رشته ؟!
اگر wcw در نظر بگیریم ، c در حالت اول فقط کمک میکنه وسط رشته رو پیدا کنیم . ولی باز هم مشکل داریم. ساختار LIFO پشته رو تصور کنید. هر حرفی از رشته رو که میخونیم توی پشته push میکنیم. ولی وقتی تا وسط رشته رفتیم چه طوری pop کنیم ؟! از آخرین عنصری که push کردیم pop میشه ، بنابراین رشته درست در نمیاد.
مثلا رشته abbcabb رو در نظر میگیریم. abb توی پشته push میشه .حالا که pop کنیم bba میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متنه.
پس مستقل از متن نیستن ؟؟!!!!
(10 بهمن 1392 03:12 ب.ظ)zahra2012 نوشته شده توسط: [ -> ] (10 بهمن 1392 01:17 ب.ظ)helena نوشته شده توسط: [ -> ]در مورد ww: وسط رشته رو نمیتونیم پیدا کنیم. از کجا بدونیم الان رسیدیم وسط رشته ؟!
اگر wcw در نظر بگیریم ، c در حالت اول فقط کمک میکنه وسط رشته رو پیدا کنیم . ولی باز هم مشکل داریم. ساختار LIFO پشته رو تصور کنید. هر حرفی از رشته رو که میخونیم توی پشته push میکنیم. ولی وقتی تا وسط رشته رفتیم چه طوری pop کنیم ؟! از آخرین عنصری که push کردیم pop میشه ، بنابراین رشته درست در نمیاد.
مثلا رشته abbcabb رو در نظر میگیریم. abb توی پشته push میشه .حالا که pop کنیم bba میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متنه.
پس مستقل از متن نیستن ؟؟!!!!
با استدلالی که من کردم نه ، مستقل از متن نیستن.
سلام. باز هم میگم به تشابه این زبانها دقت کنید: (اگه TEX مشکل داشت روی ارسالم دکمه پاسخ رو بزنید تا کد رو ببینید.)
[tex]L=\{w_1 c w_2|w_1=w_2\}[/tex]
روی الفبای a,b حساس به متنه. روی a,b,c هم حساس به متنه.
[tex]L=\{w_1 c w_2|w_1\neq w_2\}[/tex]
روی الفبای a,b مستقل ازمتنه.
[tex]L=\{w_1 w_2|w_1=w_2\}[/tex]
حساس به متنه.
[tex]L=\{w_1w_2|w_1\neq w_2\}[/tex] (با شرط برابری طول دو زیررشته.)
مستقل از متنه.
من الان دچار تناقض شدم با حرفی که خودم زدم !!!
WW
R چه طوری مستقل از متنه ؟! با پشته که پیش میریم از کجا میفهمه که رسیدیم وسط رشته باید pop کنه ؟!!!!!!
(10 بهمن 1392 07:02 ب.ظ)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 منظم هست؟
(18 بهمن 1392 07:23 ب.ظ)zahra2012 نوشته شده توسط: [ -> ] (10 بهمن 1392 07:02 ب.ظ)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 منظم هست؟
عذرخواهی میکنم. یکم عجله کردم. اگه رشته کلی حداقل 2 تا c داشت منظم میشد. در غیر این صورت مستقل از متنه.
(19 بهمن 1392 01:45 ق.ظ)Jooybari نوشته شده توسط: [ -> ] (18 بهمن 1392 07:23 ب.ظ)zahra2012 نوشته شده توسط: [ -> ] (10 بهمن 1392 07:02 ب.ظ)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 داشت منظم میشد. در غیر این صورت مستقل از متنه.
یعنی با الفبای {a,b,c} و به این شکل
w1ccw2 که w1 مساوی w2 نیست
منظم هست؟ میشه بگین چرا ؟
(19 بهمن 1392 01:54 ب.ظ)zahra2012 نوشته شده توسط: [ -> ]یعنی با الفبای {a,b,c} و به این شکل
w1ccw2 که w1 مساوی w2 نیست
منظم هست؟ میشه بگین چرا ؟
نه. منظورم اینه که اگه در یکی از زیررشته ها حرف c باشه. بیخیال. این زبانی که نوشتم رو نادیده بگیرید. تعریف صریحی نداره. استفاده نمیشه.
) تا بتونه در یه حالتی به جواب برسه. اگه توی یکی از حالات به حالت نهایی رسید رشته پذیرفتست. 
این خاصیت غیرقطعیه.