سلام به همه دوستان
برای ارائه یه الگوریتم ساختاری برای عملگر Third به مشکل برخورد کردم ممنون میشم اگر دوستان راهنمایی کنند البته تو کتاب لینز فقط اثبات منظم بودن ان را خواسته .
عملیان Third روی یک رشته از زبان L به شکل زیر تعریف شده است , یک الگوریتم ساختاری برای ان ارائه دهید ؟
[tex]third (a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}....) = a_{3}a_{6}...[/tex]
۲ - ایا میتوان با اعمال عملگرهای تقسیم (راست یا چپ) ,الحاق و .. این عملگر را شبیه سازی کرد؟
منظور شما اینه که چطوری میشه از روی آتاماتایی که زبان L رو می پذیره، آتاماتایی ساخت که [tex]third(L)[/tex] رو بپذیره؟
اره
حالا یا اثبات ساختاری که همان ساخت اتاماتا میباشد یا اثبات به کمک سایر عملگرها که بتونیم نشان بدیم زبان منظم نسبت به این عملگر بسته است .
هر دو اثباتش مد نظرمه چون تا الان هیچی به ذهنم نرسیده .
میتونید یک زبان ساده رو مثال بزنید و براش dfa بکشین و third رو روش پیاده کنید. و بعد به کل زبانهای منظم بسطش بدینو نتیجه بگیرین که زبان حاصله منظمه.
thirdیک زبان در واقع مکانهای مضرب ۳ از رشته های آن زبانو استخراج میکنه.
یه راه حل میتونه به این شکل باشه که در dfa مورد نظر هر state رو به ۳ state تبدیل کنیم. که نشاندهنده مکان حرف ورودی است که باقیماندش ۰ و ۱ و ۲ باشه، بعد یالهایی که باقیماندشون ۱ یا ۲ هست، لاندا میذاریم. و فقط یالهایی موجودیت پیدا میکنند که جایگاه مضرب ۳ رو دارن(باقیمانده ۰)