لغة شكلية

في الرياضيات والمنطق والمعلوماتية، يطلق مصطلح اللغة الشكلية 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\vee w\in L_2\}$	نعم	لا	نعم	نعم	نعم	نعم
Intersection	$\{w|w\in L_1\wedge w\in L_2\}$	نعم	لا	لا	نعم	نعم	نعم
Complement	$\{w|w\in ̸L_1\}$	نعم	نعم	لا	نعم	نعم	لا
Concatenation	$L_1\cdot L_2=\{w\cdot z|w\in L_1\wedge z\in L_2\}$	نعم	لا	نعم	نعم	نعم	نعم
Kleene star	$L_1^{*}=\{ϵ\}\cup \{w\cdot z|w\in L_1\wedge 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

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

bg:Формален език bs:Formalni jezik ca:Llenguatge formal ckb:زمانی شێوەیی cs:Formální jazyk da:Formelt sprog de:Formale Sprache el:Τυπική γλώσσα Formal language]] es:Lenguaje formal fa:زبان صوری fi:Formaali kieli fr:Langage formel he:שפה פורמלית hi:औपचारिक भाषा hr:Formalni jezik hu:Formális nyelv it:Linguaggio formale (matematica) ja:形式言語 ko:형식 언어 lt:Formali kalba mk:Формален јазик nl:Formele taal no:Formelt språk pl:Język formalny pt:Linguagem formal ro:Limbaje formale ru:Формальный язык sh:Formalni jezik simple:Formal language sk:Formálny jazyk sr:Формални језик sv:Formella språk tr:Biçimsel dil kuramı uk:Формальна мова zh:形式语言