1) با استفاده از w وضعیت dfa مربوط به زبان f را رسم کنید
f={w|w E {0,1}* ,w شامل هیچ جفت 1ی نباشد که بین آنها تعداد فردی کاراکتر وجود داشته باشد (به عبارت دیگر بین هر دو 1ی حتما تعداد زوجی کاراکتر وجود داشته باشد.
2)dfA مربوط به زبان d همچنین عبارت منظم مربوط به این زبان را بپذیرد.
[tex]D={W|n_{a}(w)=2K,n_{b}(w)=2K 1}[/tex]
و w شامل زیر رشته ab نباشد.
در حل زیر لطفا وضعیت تله را به صورتی که با هر کدام از سمبلهای الفبای زبان به خودش برمیگردد رسم کنید (طوقه )
1-اگر دو تا 1 پشت سر هم بیاد دیگه نباید بعدش 1 بیاد چون تعداد کاراکترهای بین 1 سوم و یکی از یک‌ها ناچار فرد میشه
مثلا
1101 یا 11001 یا 111
پس اگه 11 داشتیم بعدش فقط میتونیم 0 ببینیم.
در ابتدا میتونیم هر تعداد 0 که خواستیم بخونیم .(طوقه با برچسب 0 )وضعیت 0
در وضعیت 0 اگر 1 خوندیم به وضعیت 1 میرویم و در این وضعیت 1 دو حالت داریم یا یک میخوانیم به وضعیت 2 میرویم که حالت پذیرش است و طوقه با برچسب 0 دارد و با خواندن یک به حالت تله میرویم.
در وضعیت 1 اگر 0 خواندیم به وضعیت 3 میرویم و از 3 با 0 دوباره به همان حالت قبلی 1 برمیگردیم اگر در وضعیت 3 یک خواندیم به یک حالت تله میرویم چون در این صورت بین 2 تا 1 خوانده شده یک 0 است که دیگر رشته عضو زبان نیست.
دقت کنید که حالت های 0 و 1 و 2 و 3 همه حالت پذیرش هستند و فقط حالت تله غیرپذیرش است.
چون همه رشته‌ها عضو زبان هستند مگر اینکه شرط برقرار شود و مشخص شود که رشته عضو زبان نیست.
حالا رشته 00001000011
را به dfa میدهیم با خواندن صفرها در وضعیت 0 می ماند و با خواندن 1 به وضعیت 1 میرود با خواندن 4 صفر به همان حالت 1 برمیگردد با خواندن 1 به حالت 2 میرود و در آنجا با خواندن 1 به حالت تله میرود.پس رشته عضو زبان نیست و نمی پذیرد اگر دقت کنید بین 1 اول و 1 آخر 5 کاراکتر فاصله است.
2- تعداد b باید فرد باشد پس حتما باید یک b داشته باشیم گفته است ab نداشته باشد پس اگر a خواندیم بعدش نمیتوانیم b بخوانیم پس رشته ای مثل aaaa نمیتواند عضو زبان باشد یعنی حتما باید رشته با b شروع شود.
پس از وضعیت 0 با خواندن b به وضعیت 1 میروید و از 0 با خواندن a به یک وضعیت تله میروید.
این یک b خوانده شده باعث میشود که در مراحل بعد فقط به دنبال خواندن تعداد زوج b و تعداد زوج a باشیم. به این نکته دقت کنید تا دلیل نام گذاری وضعیتها را متوجه شوید.
وضعیت qab که در آن a باقیمانده تعداد a خوانده شده تا این مرحله بر عدد 2 و b نیز باقیمانده تعداد b های خوانده شده بر 2 است.
وضعیت 1 را وضعیت q00 می نامید یعنی تعداد a زوج و تعداد b زوج است.
وضعیت های زیر را در راسهای یک 4 ضلعی بکشید.
q00 تعداد a زوج و تعداد b زوج حالت پذیرش
q10 تعداد a فرد و تعداد b زوج
q01 تعداد a زوج و تعداد b فرد
q22 تعداد a زوج و تعداد b زوج و حالت پذیرش دقت کنید که با حالت q00 تفاوت دارد از این لحاظ که در این وضعیت خواندن b منجر به عدم پذیرش رشته و رفتن به وضعیت تله میشود.( باقیمانده بر 2، 0 یا 1 میشود ولی برای تمایز با حالت 00، 22 بگذارید)
در وسط چهار ضلعی وضعیت q11 را قرار دهید که حالت تله می باشد.
از q00 با خواندن a به وضعیت q10 میرویم.
از q00 با خواندن b به وضعیت q01 میرویم.
از q10 با خواندن a به حالت q22 میرویم.
از q10 با خواندن b به وضعیت q11 میرویم.(تله)
از q01 با خواندن b به وضعیت q00 برمیگردیم.
از q01 با خواندن a به حالت q11 میرویم. (تله)
از q22 با خواندن b به وضعیت q11 میرویم.(تله)
از q22 با خواندن a به حالت q10 برمیگردیم.
حال برای مثال رشته baaaa پذیرفته میشود.
bbbab رد میشود.
نکته کلی:
در مسائلی که میگوید رشته هایی که فاقد فلان زیر رشته هستند شما همه وضعیتها را حالت پذیرش قرار میدهید به جز وضعیت هایی که منجر به تولید آن زیر رشته میشود.( یعنی تا ثابت نشود که این رشته عضو زبان نیست رشته را عضو زبان میگیریم) و این وضعیت غیرپذیرش تله هستند چون اگر زیر رشته رویت شد دیگر با خواندن هیچ سمبلی رشته عضو زبان نمیشود.
اما در مسائلی که میگوید رشته شامل فلان زیر رشته باشد برعکس است یعنی همه حالتها غیرپذیرش هستند مگر آنکه زیر رشته رویت شود و آن وضعیت پذیرش است که در این نوع مسائل تله نداریم مگر آنکه مساله شرط دیگری داشته باشد.
مسئله 1 جزو حالت اول بود و مسئله 2 جزو حالت دوم ولی دارای شرط دیگری بود.
چرا مسئله 2 جزو حالت دوم بود علت آن است که ما به دنبال تعداد فردی b و تعداد زوجی a هستیم پس رشته عضو زبان نیست مگر آنکه تعداد فردی b و زوجی a بخواند و علت تله هم وجود شرط شامل ab نباشد می باشد.
تفاوت دیگر مسئله 2 با حالت دوم این است که شامل زیر رشته بودن تغیییری نمیکند یعنی اگر خواستیم رشته شامل ba باشد به محض مشاهده ba پذیرش میشود اما مثلا حالت فرد بودن b تغییر میکند یعنی اگر در حال حاضر در حالت پذیرش باشیم یک b بخوانیم دیگر تعداد bها فرد نیست و به حالت دیگری میرویم یعنی پذیرش در این مسئله موقتی و مشروط است .
ببخشید طولانی شد خواستم یه جوری توضیح بدم که مسائل مشابه رو هم بتونید حل کنید.