نظریه زبان‌ها: تفاوت میان نسخه‌ها

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

ویرایش