نظریه زبان‌ها: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بازنویسی و حذف اشتباهات + گسترش برچسب‌ها: متن دارای ویکی‌متن نامتناظر ویرایشگر دیداری |
اصلاح اشتباهات مقاله |
||
خط ۳۳:
[[مسئله تصمیم|مسئلهٔ تصمیم]] معادل [[عنصر (ریاضیات)|عضویت]] در یک زبان صوری است. مجموعهٔ همهٔ رشته‌هایی که یک اتوماتا می‌پذیرد (یا یک گرامر تولید می‌کند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبان‌ها یک حوزه کاربردی اصلی در [[نظریه رایانش‌پذیری]] و [[نظریه پیچیدگی محاسباتی|نظریهٔ پیچیدگی محاسباتی]] است.<ref name=":2" />
زبان‌های صوری را می‌توان به کمک [[وراثت چامسکی]] بر اساس قدرت مولد ([[دستور زبان صوری|گرامر]]) آنها و یا پیچیدگی [[نظریه اتوماتا|اتوماتای]] تصمیم آنها طبقه بندی کرد.
== جستارهای وابسته ==
| |||