برخی از واژه های نظریه زبانها

مباحث مقدماتی Introductory topics
منطق گزاره ای Propositional logic
منطق مسندی Predicate logic
سیستم اثبات Proof system
نظریه مجموعه ها Set theory
پارادوکس راسل Russells paradox
مجموعه های شمارا و ناشمارا Countable and countable sets
زبان ها و گرامرها Languages and grammars
تئوری عدم قطعیت Uncertainty theory
زبان های منظم Regular language
پذیرنده های متناهی قطعی Deterministic finite acceptor (automation)
پذیرنده های متناهی غیر قطعی Nondeterministic finite acceptor (automation
تبدیل پذیرنده های متناهی غیرقطعی به قطعی Conversion of nondeterministic finite acceptor to deterministic finite acceptor
پذیرنده های متناهی قطعی کمینه Minimality of DFA (deterministic finite automation )
زبان های منظم Regular languages
عبارات منظم Regular expression
گرامرهای راستگرد خطی Right linear grammar
گرامرهای چپگرد قطعی Left linear grammar
گرامرهای منظم Regular grammars
خصوصیات بستاری زبان های منظم Closure properties on regular languages
تصمیم پذیری و زبان های منظم Decidability and regular languages
زبان های نامنظم Irregular languages
لم پمپینگ برای زبان های منظم Pumping lemma for regular languages
زبان های مستقل از متن Context-free languages (CFLs )
گرامرهای مستقل از متن Context – free grammars
زبان های مستقل از متن Context – free languages
اشتقاق چپگرد Leftmost derivation
اشتقاق راستگرد Rightmost derivation
درخت اشتقاق Derivation trees
گرامرهای مبهم Ambiguous grammars
گرامرهای نامبهم Unambiguous grammars
ساده سازی گرامرهای مستقل از متن Simplification of context – free grammars (CFGs)
گرامرهای مستقل از متن بصورت طبیعی چامسکی Context free grammar (CFG) in Chomsky normal form (GNF)
ساده سازی گرامرهای مستقل از متن بصورت گرایباخ Context free grammar (CFG)in greibach normal form (GNF)
مساله عضویت Membership problem
الگوریتم CYK CYK algorithm
ماشین های پوش دان Pushdown automata
هم ارزی ماشین های پوش دان و گرامرهای مستقل از متن Equivalence of pushdown automata with context – free grammar
ماشین های پوش دان قطعی Deterministic pushdown automata
زبان های مستقل از متن قطعی Deterministic context-free grammar
زبان های قطعی غیر مستقل از متن Nondeterministic context –free languages
لم پمپینگ برای زبان های مستقل از متن Pumping lemma for context –free languages
خصوصیات بستاری و تصمیم پذیری زبان های مستقل از متن Closure properties and decidability of context –free languages
زبان های حساس به متن Context – sensitive languages
ماشین های کراندر خطی Linear bounded automata
گرامرهای حساس به متن Context-sensitive grammars
زبان های بدون محدودیت Infinite languages
ماشین تورینگ و انواع آنها و گرامرهای بدون محدودیت Turing machine and infinite grammars
سلسله مراتب زبان های رسمی Formal languages hierarchy
محاسبه پذیری Computability
تز چورچ و تورینگ Church – turing thesis
تصمیم پذیری و تصمیم ناپذیری Decidability and undecidability
مسئله توقف Halting problem
مسئله تخصیص پست Post correspondence problem
پیچیدگی محاسباتی Computational calculations
رده پیچیدگی P Complexity class P
رده پیچیدگی NP Complexity class NP
مسائل کامل NP NP – complete problems
مسائل NP سخت NP – hard problems