تالار گفتمان مانشت
عملیات third بروی یک زبان منظم - نسخه‌ی قابل چاپ

عملیات third بروی یک زبان منظم - hadi_m - 01 دى ۱۳۹۰ ۱۲:۴۴ ب.ظ

سلام به همه دوستان
برای ارائه یه الگوریتم ساختاری برای عملگر Third به مشکل برخورد کردم ممنون میشم اگر دوستان راهنمایی کنند البته تو کتاب لینز فقط اثبات منظم بودن ان را خواسته .

عملیان Third روی یک رشته از زبان L به شکل زیر تعریف شده است , یک الگوریتم ساختاری برای ان ارائه دهید ؟

[tex]third (a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}....) = a_{3}a_{6}...[/tex]

۲ - ایا میتوان با اعمال عملگرهای تقسیم (راست یا چپ) ,الحاق و .. این عملگر را شبیه سازی کرد؟

RE: عملیات third بروی یک زبان منظم - mfXpert - 01 دى ۱۳۹۰ ۰۸:۳۳ ب.ظ

منظور شما اینه که چطوری میشه از روی آتاماتایی که زبان L رو می پذیره‌، آتاماتایی ساخت که [tex]third(L)[/tex] رو بپذیره؟

عملیات third بروی یک زبان منظم - hadi_m - 01 دى ۱۳۹۰ ۰۸:۵۴ ب.ظ

اره
حالا یا اثبات ساختاری که همان ساخت اتاماتا میباشد یا اثبات به کمک سایر عملگرها که بتونیم نشان بدیم زبان منظم نسبت به این عملگر بسته است .
هر دو اثباتش مد نظرمه چون تا الان هیچی به ذهنم نرسیده .

RE: عملیات third بروی یک زبان منظم - reyhaneh64 - 14 دى ۱۳۹۰ ۰۴:۵۹ ب.ظ

میتونید یک زبان ساده رو مثال بزنید و براش dfa بکشین و third رو روش پیاده کنید. و بعد به کل زبانهای منظم بسطش بدینو نتیجه بگیرین که زبان حاصله منظمه.
thirdیک زبان در واقع مکانهای مضرب ۳ از رشته های آن زبانو استخراج میکنه.
یه راه حل میتونه به این شکل باشه که در dfa مورد نظر هر state رو به ۳ state تبدیل کنیم. که نشاندهنده مکان حرف ورودی است که باقیماندش ۰ و ۱ و ۲ باشه، بعد یالهایی که باقیماندشون ۱ یا ۲ هست‌، لاندا میذاریم. و فقط یالهایی موجودیت پیدا میکنند که جایگاه مضرب ۳ رو دارن(باقیمانده ۰)