ماشین مور http://en.wikipedia.org/wiki/Moore_machine
ماشین ملی http://en.wikipedia.org/wiki/Mealy_machine
ماشن مجازی http://en.wikipedia.org/wiki/Virtual_finite_state_machine
در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی برشمردنی یک نوع زبان صوری است که تا حدی تصمیم پذیر یا تصمیم پذیر تورینگ نیز نامیده می شود.این نوع زبان در سلسله مراتب زبان های صوری چامسکی با عنوان زبان نوع صفر شناخته می گردد.کلاس زبان های بازگشتی برشمردنی 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
در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی یک نوع زبان صوری است که همچنین بازگشتی، تصمیم پذیر یا تصمیم پذیر بازگشتی نامیده می شود.کلاس تمامی زبان های بازگشتی غالبا" R نامیده می شود، با اینکه این نام برای کلاس RP نیز استفاده می شود.
این نوع از زبان به طور واضحی از سلسله مراتب چامسکی(Chomsky hierarchy) جا مانده است.
تعاریف:
دو تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:
1- یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی(recursive subset)در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.
2- یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با یک رشته ورودی مواجه می گردد، متوقف می شود و اگر رشته در زبان موجود باشد آن را می پذیرد، در غیر این صورت متوقف می گردد و آن رشته را نمی پذیرد. ماشین تورینگ همیشه متوقف می گردد: این ماشین به عنوان تصمیم پذیر شناخته می شود.
تمامی زبان های بازگشتی بازگشتی برشمردنی نیز هستند. تمامی زبان های منظم، مستقل از متن وحساس به متن زبان های بازگشتی می باشند.
خواص بسته بودن:
زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:
- ستاره L
- اتصال L وP
- اجتماع L وP
- اشتراک L وP
- اختلاف L وP
در ریاضیات، منطق و علوم کامپوتر، زبان صوری یک مجموعه از کلمات (رشته های کاراکتری) با طول متناهی است که از برخی الفباهای متناهی مشتق می گردد، و نظریه علمی که مرتبط با این مفاهیم است به عنوان نظریه زبان صوری شناخته می شود.
یک الفبا ممکن است {a,b} ،و رشته بر روی آن ababba باشد.یک زبان نمونه بر روی این الفبا، که دارای رشته عنوان شده است، ممکن است مجموعه تمام رشته های باشد که شامل علائم a و b با تعداد مساوی است.
رشته تهی (رشتهای با طول صفر) رشته با معنا تلقی می گردد و با علامe, ε, Λ. نمایش داده می شود. از آن جایی که الفبا یک مجموعه متناهی است وهر عبارت دارای طول محدود است، زبان ممکن است دارای رشته های عضو نامحدود باشد.
سوالی که اغلب در مورد زبان های صوری پرسیده می شود این است " آیا یک عبارت داده شده به زبان تعلق دارد یا خیر؟" ، که جواب آن، بحث مورد برسی نظریه محاسبات و نظریه پیچیدگی است
چند مثال از زبان های صوری:
1- مجموعه رشته های تولید شده بر روی a و b .
2- مجموعه {a^n}،n یک عدد اول است.
3- زبانی متناهی مانند a،aa،bba .
4- مجموعای از برنامه های یک زبان برنامه نویسی که از نظر نحوی صحیح می باشند.
5- مجموعای از ورودی ها که ماشین تورینگ خاصی بر روی آن متوقف می گردد.
یک زبان صوری به وسیله راه های مختلفی مشخص می گردد، از جمله:
1- رشته هایی که توسط گرام های صوری تولید می شوند.
2- رشته هایی که توسط عبارات منظم تولید می شوند
3- رشته هایی که توسط برخی ماشین ها، مانند ماشین تورینگ یا ماشین حالت متناهی پذیرفته می شوند.
4- آن دسته از سوالات بله/ خیر که جوابشان بله است.