لغة شكلية

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

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

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.
العملية		اللغات المنتظمة	DCFL	CFL	لغة حساسة للسياق	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}\}$	نعم	لا	نعم	نعم	نعم	نعم
نجمة كلين	$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\}$	نعم	لا	نعم	نعم	نعم	نعم