لغة صورية

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

إذا اعتبرنا اللغة الصورية مجموعة كلمات : تكون المجموعة A نا يدعى أبجدية للغة L ، عناصر هذه الأبجدية تدعى كلمات . إذا اعتبرنا اللغة الصورية مجموعة جمل عندئذ تكون المجموعة A ذخيرة مفردات vocabulary أو تدعى أيضا lexicon للغة 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.
Union	$\{w|w\in L_{1}\lor w\in L_{2}\}$	نعم	لا	نعم	نعم	نعم	نعم
Intersection	$\{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.

 انظر أيضاً

• نحو صوريFormal grammar
• Grammar framework
• Formal method
• Formal science
• نظام شكلي Formal system
• تدوين رياضي Mathematical notation
• لغة برمجة

 وصلات خارجية

• Alphabet على بلانيت ماث
• Language على بلانيت ماث
• University of Maryland, Formal Language Definitions
• James Power, "Notes on Formal Language Theory and Parsing", 29 November 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