زبان wcw اگر الفبا به دو صورت زیر باشد در هر کدوم مستقل هست یا نه؟
۱) (a,b)*
۲) (a,b,c)*
بعد میشه بگین ww چه جوری با پشته ثابت می کنیم مستقل از متن نیست با لم تزریقو می فهمم ممنون میشم .
در مورد ww: وسط رشته رو نمیتونیم پیدا کنیم. از کجا بدونیم الان رسیدیم وسط رشته ؟!
اگر wcw در نظر بگیریم ، c در حالت اول فقط کمک میکنه وسط رشته رو پیدا کنیم . ولی باز هم مشکل داریم. ساختار LIFO پشته رو تصور کنید. هر حرفی از رشته رو که میخونیم توی پشته push میکنیم. ولی وقتی تا وسط رشته رفتیم چه طوری pop کنیم ؟! از آخرین عنصری که push کردیم pop میشه ، بنابراین رشته درست در نمیاد.
مثلا رشته abbcabb رو در نظر میگیریم. abb توی پشته push میشه .حالا که pop کنیم bba میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متن نیست.
(۱۰ بهمن ۱۳۹۲ ۰۱:۱۷ ب.ظ)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 میاد بیرون. راهی نداریم که ادامه رشته رو پیدا کنیم .
در حالت دوم هم که باز همون مشکل رو داریم که نمیتونیم وسط رشته رو مشخص کنیم. پس در هر دو حالت مستقل از متنه.
پس مستقل از متن نیستن ؟؟!!!!
با استدلالی که من کردم نه ، مستقل از متن نیستن.
سلام. باز هم میگم به تشابه این زبانها دقت کنید: (اگه 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] (با شرط برابری طول دو زیررشته.)
مستقل از متنه.
من الان دچار تناقض شدم با حرفی که خودم زدم !!!
WWR چه طوری مستقل از متنه ؟! با پشته که پیش میریم از کجا میفهمه که رسیدیم وسط رشته باید pop کنه ؟!!!!!!
(۱۶ بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)helena نوشته شده توسط: من الان دچار تناقض شدم با حرفی که خودم زدم !!!
WWR چه طوری مستقل از متنه ؟! با پشته که پیش میریم از کجا میفهمه که رسیدیم وسط رشته باید pop کنه ؟!!!!!!
مستقل از متن غیرقطعیه. ماشین خودش باید تمام حالات ممکن برای وسط بودن رشته رو چک کنه (بیچاره! گناه داره
) تا بتونه در یه حالتی به جواب برسه. اگه توی یکی از حالات به حالت نهایی رسید رشته پذیرفتست. 
این خاصیت غیرقطعیه.
(۱۷ بهمن ۱۳۹۲ ۰۱:۰۹ ق.ظ)Jooybari نوشته شده توسط:(16 بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)helena نوشته شده توسط: من الان دچار تناقض شدم با حرفی که خودم زدم !!!
WWR چه طوری مستقل از متنه ؟! با پشته که پیش میریم از کجا میفهمه که رسیدیم وسط رشته باید pop کنه ؟!!!!!!
مستقل از متن غیرقطعیه. ماشین خودش باید تمام حالات ممکن برای وسط بودن رشته رو چک کنه (بیچاره! گناه داره
آهان !!! ممنون فهمیدم !!
(۱۰ بهمن ۱۳۹۲ ۰۷:۰۲ ب.ظ)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 منظم هست؟
(۱۸ بهمن ۱۳۹۲ ۰۷:۲۳ ب.ظ)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 داشت منظم میشد. در غیر این صورت مستقل از متنه.
(۱۹ بهمن ۱۳۹۲ ۰۱:۴۵ ق.ظ)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 داشت منظم میشد. در غیر این صورت مستقل از متنه.
یعنی با الفبای {a,b,c} و به این شکل
w1ccw2 که w1 مساوی w2 نیست
منظم هست؟ میشه بگین چرا ؟
(۱۹ بهمن ۱۳۹۲ ۰۱:۵۴ ب.ظ)zahra2012 نوشته شده توسط: یعنی با الفبای {a,b,c} و به این شکل
w1ccw2 که w1 مساوی w2 نیست
منظم هست؟ میشه بگین چرا ؟
نه. منظورم اینه که اگه در یکی از زیررشته ها حرف c باشه. بیخیال. این زبانی که نوشتم رو نادیده بگیرید. تعریف صریحی نداره. استفاده نمیشه.