لغة شكلية

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

عمليات على اللغات

Closure properties of language families (${\displaystyle L_{1}}$ Op ${\displaystyle L_{2}}$ where both ${\displaystyle L_{1}}$ and ${\displaystyle L_{2}}$ are in the language family given by the column). After Hopcroft and Ullman.

العملية		regular	DCFL	CFL	لغة حساسة للسياق	recursive	r.e.
الاتحاد	${\displaystyle \{w|w\in L_{1}\lor w\in L_{2}\}}$	نعم	لا	نعم	نعم	نعم	نعم
التقاطع	${\displaystyle \{w|w\in L_{1}\land w\in L_{2}\}}$	نعم	لا	لا	نعم	نعم	نعم
Complement	${\displaystyle \{w|w\not \in L_{1}\}}$	نعم	نعم	لا	نعم	نعم	لا
Concatenation	${\displaystyle L_{1}\cdot L_{2}=\{w\cdot z|w\in L_{1}\land z\in L_{2}\}}$	نعم	لا	نعم	نعم	نعم	نعم
نجمة كلين	${\displaystyle L_{1}^{*}=\{\epsilon \}\cup \{w\cdot z|w\in L_{1}\land z\in L_{1}^{*}\}}$	نعم	لا	نعم	نعم	نعم	نعم
Homomorphism		نعم	لا	نعم	نعم	لا	نعم
Substitution		نعم	لا	نعم	نعم	لا	نعم
Inverse Homomorphism		نعم	نعم	نعم	نعم	نعم	نعم
Reverse	${\displaystyle \{w^{R}|w\in L\}}$	نعم	لا	نعم	نعم	نعم	نعم

انظر أيضاً

• علم النحو
• أساليب رسمية
• علوم شكلية
• نظام شكلي Formal system
• تدوين رياضي Mathematical notation
• لغة برمجة

وصلات خارجية

• Alphabet على بلانيت ماث
• Language على بلانيت ماث
• جامعة ماريلاند مدرسة الطب, Formal Language Definitions
• James Power, "Notes on Formal Language Theory and Parsing", 29 نوفمبر 2002.
• Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1-3, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997):t
  • Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39
  • Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1
  • Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1
  • Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1
  • Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510
  • Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746
  • M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2
  • Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267

المصادر

موسوعات ذات صلة :

• موسوعة رياضيات
• موسوعة اللغة
• موسوعة علم الحاسوب
• موسوعة تقنية المعلومات