É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*.