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:
É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:
Si, abusant de la notació, considerem lalfabet E com un llenguatge finit format per cadenes de longitud 1, podem escriure
Aquests dos conjunts reben el nom de monoide lliure i semigrup lliure engendrats per E. Dara endavant utilitzarem aquests noms i la notació * i + per referirnos a aquests conjunts.
En el context de la teoria de llenguatges formals només tenen importància els llenguatges que són infinits. Fins i tot dins daquests, els més importants són els que defineixen les cadenes que hi pertanyen en funció duna certa estructura dins de les cadenes.
1.2 Generació de llenguatges
En el context de la teoria de llenguatges formals només tenen importància els llenguatges que són infinits. Fins i tot dins daquests, els més importants són els que defineixen les cadenes que i ertanyen en funció duna certa estructura dins de les cadenes.
Un exemple daquest tipus de llenguatge és el que està format per aquelles cadenes sobre lalfabet ex = {x, +, *, (, )} que són expressions aritmètiques vàlides (ben parentitzades). És a dir,
Encara que és ben clar quin és aquest llenguatge, no pot ser definit duna forma compacta (amb una descripció finita) de la mateixa manera que sha fet en els exemples anteriors.
Una forma de definir aquest tipus de llenguatges és mitjançant una definició recursiva. Un mecanisme que permet introduir definicions recursives en el context de cadenes de símbols és donat pels sistemes de reescriptura, un cas particular dels quals són les gramàtiques.
Els elements de lalfabet no terminal, VN, sanomenen símbols no terminals, símbols auxiliars o, simplement, variables de la gramàtica.
Una producció α ß significa que la cadena a es pot reescriure com a ß(es pot canviar luna per laltra). Ens referirem a α i a β com les parts esquerra i dreta de la producció, respectivament. Per representar de forma compacta diverses produccions amb la mateixa part esquerra escriurem
en lloc de
Diem que una cadena y deriva directament duna cadena x segons una gramàtica G, i ho escrivim com a si i només si , de forma que
Diem que una cadena y deriva duna cadena x segons una gramàtica, i ho escrivim com a si i només si x = y o si existeix una seqüència finita de paraules tal que
Si, pel context, està clar a quina gramàtica ens estem referint, suprimirem la referència a la gramàtica en el símbol .
Les cadenes de V que es poden derivar a partir de laxioma reben el nom de formes sentencials de G. Si, a més a mes, són cadenes exclusivament de Vt es diu que són sentències de G.
Per exemple, el llenguatge Lex és generat per la gramàtica
on P és
Un exemple de derivació amb aquesta gramàtica seria
En aquest exemple hem subratllat en cada forma sentencial els símbols no terminals sobre els quals saplica la producció següent (la producció que saplica és òbvia per inspecció de la cadena derivada).
Es pot demostrar mitjançant un argument purament numèric i relativament senzill que hi ha llenguatges que no són generats per cap gramàtica. La demostració consisteix a mostrar que el conjunt de totes les gramàtiques sobre un determinat alfabet és numerable (atès que una gramàtica és una descripció finita), mentre que el conjunt de tots els possibles llenguatges sobre el mateix alfabet (igual que el conjunt potència de qualsevol conjunt infinit) és no numerable8.
1.2.1 La jerarquia de Chomsky
Es pot distingir entre quatre tipus de gramàtiques dacord amb la forma de les productions.
tipus 0 o també gramàtiques estructurades per frases o gramàtiques sense restrictions. Les productions no tenen cap tipus de restricció additional.
tipus 1 o també gramàtiques sensibles al context o gramàtiques contextuals.Les produccions han de ser necessàriament de la forma
onxiy són cadenes de V*, β és una cadena de V+ i A és qualsevol símbol no terminal. El prefix x i el sufix y de la part esquerra (i dreta) de cada producció rep el nom de context.
tipus 2 o també gramàtiques de context lliure, gramàtiques independents del context o gramàtiques incontextuals9. Les produccions han de ser de la forma
Aa
on A és qualsevol símbol no terminal i a és qualsevol cadena de V*.