لغة شكلية

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في الرياضيات والمنطق والمعلوماتية، يطلق مصطلح اللغة الشكلية L على أي مجموعة من الجمل محدودة الطول المأخوذة من مجموعة نهائية A تسمى الحروف الأبجدية. فمن خلال مختلف تطبيقات اللغات الشكلية، يمكن أن ننظر إلى اللغة الشكلية على أنها مماثلة لمجموعة كلمات أو مجموعة جمل.

عمليات على اللغات[عدل]

Closure properties of language families (L_1 Op L_2 where both L_1 and L_2 are in the language family given by the column). After Hopcroft and Ullman.
العملية regular DCFL CFL CSL recursive r.e.
الاتحاد \{w | w \in L_1 \lor w \in L_2\} نعم لا نعم نعم نعم نعم
التقاطع \{w | w \in L_1 \land w \in L_2\} نعم لا لا نعم نعم نعم
Complement \{w | w \not\in L_1\} نعم نعم لا نعم نعم لا
Concatenation L_1\cdot L_2 = \{w\cdot z | w \in L_1 \land z \in L_2\} نعم لا نعم نعم نعم نعم
Kleene star L_1^{*} = \{\epsilon\} \cup \{w \cdot z | w \in L_1 \land z \in L_1^{*}\} نعم لا نعم نعم نعم نعم
Homomorphism نعم لا نعم نعم لا نعم
Substitution نعم لا نعم نعم لا نعم
Inverse Homomorphism نعم نعم نعم نعم نعم نعم
Reverse \{w^R | w \in L\} نعم لا نعم نعم نعم نعم

المصادر[عدل]

  • A. G. Hamilton, Logic for Mathematicians, Cambridge University Press, 1978, ISBN 0-521-21838-1.
  • Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN 0-7204-2506-9.
  • Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978.
  • John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-029880-X.
  • Grzegorz Rozenberg, Arto Salomaa, Handbook of Formal Languages: Volume I-III, Springer, 1997, ISBN 3-540-61486-9.
  • Patrick Suppes, Introduction to Logic, D. Van Nostrand, 1957, ISBN 0-442-08072-7.

انظر أيضاً[عدل]

وصلات خارجية[عدل]

قالب:لغة ونحو صوريين