La inversió també admet la definició recursiva següent:
1.1.2 Operations amb llenguatges
Com que els llenguatges són conjunts (de cadenes), shi poden aplicar totes les operacions usuals sobre conjunts, com ara la unió, la intersecció, el complement i la resta. Aquestes operacions, les escriurem com a
A més a més, les operacions amb cadenes es poden estendre al cas de llenguatges, de la mateixa manera que sha fet amb la concatenació.
En general, donada qualsevol operació interna m-ària amb cadenes, O, la seua extensió a llenguatges és donada per
A banda, hi ha altres operacions especifiques amb llenguatges.
El quocient de dos llenguatges, L1 i L2, és donat pels prefixos daquelles cadenes de L1 que es poden factoritzar com el mateix prefix seguit dun sufix en L2.
Loperació quocient també es pot definir per a cadenes:
Per exemple, abc/c = ab i abc/ac no està definit.
Aquesta operació també sanomena quocient per la dreta i es pot veure com la inversa de la operació concatenació per la dreta.
La extensió a llenguatges es pot dur a terme com a quocient entre un llenguatge i una cadena
i també com a quocient entre dos llenguatges
Aquesta darrera definició és equivalent a la primera que sha donat.
Per exemple, si L1 = {an | n 0 i L2= {an bm | n, m 0}, aleshores L1/a = L1, L2//b = L2 i L2//a = L1.
De la mateixa manera es poden definir també els quocients per lesquerra entre cadenes o llenguatges. En alguns textos els quocients entre z i y per la dreta i per lesquerra sescriuen com a zy1 i y1z, respectivament.
El quocient per lesquerra entre una cadena x i un llenguatge L, x1 L, sanomena derivada de L respecte de x i està format pels anomenats sufixos dexenL (també de vegades bons finals de x en L).
Per exemple, està format per cadenes de zero o més símbols b perqué són les úniques que afegides a ab estàn en
Anomenem substitució una funció que a cada símbol dun alfabet li fa correspondre un llenguatge sobre un altre alfabet .
Matemàticament,
La substitució sestén trivialment a cadenes. Donada una cadena, la substitució que shi aplique donarà com a resultat la concatenació de les substitucions sobre cada un dels seus símbols.
Perquè tinga sentit, cal definir la substitució sobre la cadena buida, que ha de donar lògicament la cadena buida.
Escrivint-ho recursivament:
També ho podem escriure com
Les substitucions sestenen també trivialment per a llenguatges de la manera següent:
Un cas particular de substitució és lhomomorfisme7 que és una substitució en la qual es compleix que a tot símbol de li correspon (com a màxim) una única cadena de . És a dir, h: *. Normalment escriurem les substitucions com a f i els homomorfismes com a h.
Considerem com a exemple una substitució entre els alfabets {0,1} i {a, b, c} donada per
Aleshores es compliria que
Donat un homomorfisme h: , anomenem homomorfisme invers de la cadena y , i ho escrivim com a h1(y), el conjunt de cadenes de * tals que transformades per h donen y. És a dir,
També es pot definir lhomomorfisme invers dun llenguatge quasi de la mateixa manera.
Considerem com a exemple el llenguatge i lhomomorfisme donat per h(0) = ab, h (1) = b, h(2) = a, h(3) = cc. Aleshores es compleix que
Per a tot homomorfisme sempre es compleix que
i també
Per a lexemple anterior es té que
És important adonar-se que la propietat anterior no es compleix si intercanviem lordre daplicacio de lhomomorfisme i linvers. Seguint amb el mateix exemple, tenim que
Si de lanterior definició sexclou el terme L0, sobté lanomenat tancament positiu: