Llenguatge formal: diferència entre les revisions

[[Fitxer: Entitats sintàctiques.svg|thumb|230px|right|Aquesta imatge mostra la relació entre les [[Cadena de caràcters|cadenes de caràcters]], les [[Fórmula ben formada|fórmules ben formades]] i els [[teorema|teoremes]] s. En alguns sistemes formals, però, el conjunt dels teoremes coincideix amb el de les fórmules ben formades.]]

A [[matemàtiques]], [[lògica]], i [[ciències de la computació]], un ''' llenguatge formal ''' és un [[llenguatge]] on els símbols primitius i regles per a unir aquests símbols estan formalment especificats.<ref>{{citar web| cognom=Mellema| nom=Gregory| títol=formal language| llengua=anglès| url=http://www.oxfordreference.com/views/ENTRY.html?subview=Main&entry=t116.e929| editor=Oxford University Press| consulta=07/02/2010}}</ref> Al conjunt dels símbols primitius se l'anomena el [[alfabet]] (o vocabulari) del llenguatge, i al conjunt de les regles se l'anomena la [[gramàtica formal]] (o sintaxi). A una cadena de símbols formada d'acord amb la gramàtica se l'anomena una [[fórmula ben formada]] (o paraula) del llenguatge. Estrictament parlant, un llenguatge formal és idèntic al conjunt de totes les seves fórmules ben formades. A diferència del que passa amb l'alfabet (que ha de ser un conjunt finit) i amb cada fórmula ben formada (que ha de tenir una longitud també finita), un llenguatge formal pot estar compost per un nombre infinit de fórmules ben formades.