زبان های بازگشتی

در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی یک نوع زبان صوری است که همچنین بازگشتی، تصمیم پذیر یا تصمیم پذیر بازگشتی نامیده می شود.کلاس تمامی زبان های بازگشتی غالبا" R نامیده می شود، با اینکه این نام برای کلاس RP نیز استفاده می شود.

این نوع از زبان به طور واضحی از سلسله مراتب چامسکی(Chomsky hierarchy) جا مانده است.

تعاریف:

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

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

2-  یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با یک رشته ورودی مواجه می گردد، متوقف می شود و اگر رشته در زبان موجود  باشد آن را می پذیرد، در غیر این صورت متوقف می گردد و آن رشته را نمی پذیرد. ماشین تورینگ همیشه متوقف می گردد: این ماشین به عنوان تصمیم پذیر شناخته می شود. 

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

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

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

- ستاره L

- اتصال L وP

- اجتماع L وP

- اشتراک L وP

- اختلاف L وP