زبان های بازگشتی برشمردنی

در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی برشمردنی یک نوع زبان صوری است که تا حدی تصمیم پذیر یا تصمیم پذیر تورینگ نیز نامیده می شود.این نوع زبان در سلسله مراتب زبان های صوری چامسکی با عنوان زبان نوع صفر شناخته می گردد.کلاس زبان های بازگشتی برشمردنی RE نامیده می شود.

تعاریف:

سه تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:

1-  یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی( recursively enumerable subset ) در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.

2-  یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی(یا تابع قابل محاسبه دیگری)  وجود دارد که تمامی رشته های معتبر زبان راشمارش می کند. توجه داشته باشید که اگر زبان نا متناهی باشد، از آن جائیکه میتوانیم بررسی کنیم که آیا رشته تولید شده برای عدد n ، قبلا" برای عددی کوچکتر از n تولید شده یا نه، الگوریتم شمارش کننده می تواند به گونه ای انتخاب گردد که از تکرار جلوگیری کند. اگر رشته قبلا" تولید شده بود به جای ورودی n+1 از خروجی استفاده کنید(به صورت باز گشتی) ،اما مجددا" بررسی کنید که آیا جدید است یا نه.

3-  یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با هر رشته ورودی موجود در زبان مواجه می گردد، متوقف می شود و  رشته  را می پذیرد، ماشین تورینگ مورد بحث هنگام مواجه با رشته ای که در داخل زبان نیست ممکن است متوقف شود و رشته را نپذیرد یا برای همیشه در حلقه بیا فتد.

تمامی زبان های منظم، مستقل از متن، حساس به متن و بازگشتی، بازگشتی برشمردنی هستند.

RE و مکملش (co-RE)  پایه سلسله مراتب حسابی (arithmetical hierarchy ) را تشکیل می دهند.

خواص بسته بودن:

زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:

- ستاره L

- اتصال L وP

- اجتماع L وP

- اشتراک L وP

توجه کنید که زبان های بازگشتی برشمردنی بر روی اعمال مکمل گیری و تفاضل بسته نیستند.

 

                                               http://en.wikipedia.org/wiki/Recursively_enumerable_language

 

نظرات 0 + ارسال نظر
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)
ایمیل شما بعد از ثبت نمایش داده نخواهد شد