补充资料：形式语言

形式语言
formal language

　　形式语言[肠旧日lh卿.罗冲opMa几‘““.，3““] 由某个(有限的或无穷的)字母枣(alphabet)v(有时亦称为字典(dictiona卿))上的元素组成的串(即字(word))的任意集合，亦即形如田=a:，…，ak的表示的集合，这里a、，…，久任V;串。的长度是数k，通常记为}田}.一般空串也被考虑在内，记为凡规定{A}二0.通常说字母表F上的一个语言，而省略“形式”二字.在数学语言学(n篮1 thorr以6口」五ngll云允)以及自动机理论(aLIt0H坦ta，thooryof)中，人们考虑用各种类型的形式文法(ga代叮坦r，场~1)及自动机来有效地描述形式语言，在大多数情况下这些都是修改了的多带非确定T耐l嗯机(Turmg叮以chine)，对机器在工作带上的工作模式加了一些限制. 形式语言的运算.除了常见的集合运算，还考虑形式的语言乘法(m』tiP五口tion)(或称直接乘法( di代CtmLdtiPli以tion)，或毗连(co暇把nation)): L:几二{xy二x任L.，y任仁};左除(leftdi姑ion):拼卜注】细节见形式语言与自动机(fon力alla理阳笋朗da以olr以ta).鲍丰译李廉校LZ\L一{x:日夕，z(夕‘L:%26z任几%26夕二zx)}:布咚(咖division)几/几的定义类似左除;举作卿粤(妞eration): L’二L“日刀U…，这里L0指{八}，而刀十，”厂L(特别地，V上所有串组成的集合就是V’);截迭代闭包(甘切以习让d iteratio们): L+二刀日刀日…;代换(s咖titution):如果L是有限字母表{马，…，气}上的一个语言，L:，…，从是任意语言，则 S(L;a，，…，久}L，，…，人)= ={x，，’二x:*“a‘、…a“EL%26x‘，6L，%26…%26x，*‘L‘*};如果每个语言吞(i=1，…，n)都是由一个串:，组成的，这个代人称为同态(加伽伽印比m);如果所有的共都不是空字，则称为不可缩同态(幽bbreha让d holrlo-二rp油m)·如果语言{x}仅由一个串二组成，则一般写成xL，x\L等，而不写成{x}L，{x}\L等· 一个语言簇(份比ty ofla飞胆笋)是一个有序对(g，劝(或丫，如果g是共认的)，这里g是一个无穷字母表，丫是一个语言的集合，满足:l)对任何L‘、，存在有限字母表公C=苏，使得LC艺’;2)存在某个L〔丫，有L笋必;3)了在并、乘积、与正规集的交、截闭包、不可缩同态及任意同态的逆的运算下封闭.对任意同态封闭的簇，称为完全的(田mPlete).
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。