Obre el menú principal
Aquesta imatge mostra la relació entre les cadenes de caràcters, les fórmules ben formades i els teoremes. 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.[1] Al conjunt dels símbols primitius se l'anomena l'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.

Per exemple, un alfabet podria ser el conjunt {a, b}, i una gramàtica podria definir a les fórmules ben formades com aquelles que tenen el mateix nombre de símbols a que b. Llavors, algunes fórmules ben formades del llenguatge serien: ab, ba, abab, ababba, etc., I el llenguatge formal seria el conjunt de totes aquestes fórmules ben formades.

Per a alguns llenguatges formals hi ha una semàntica formal que pot interpretar i donar significat a les fórmules ben formades del llenguatge. Tanmateix, una semàntica formal no és condició necessària per definir un llenguatge formal, i això és una diferència essencial amb els llenguatges naturals.

En alguns llenguatges formals, la paraula buida (és a dir, la cadena de símbols de longitud zero) està permesa, notant-se freqüentment mitjançant , o .

Exemples de llenguatges formalsModifica

  • Un conjunt de totes les paraules sobre  .
  • El conjunt   és un nombre primer.
  • El conjunt de tots els programes sintàcticament vàlids en un determinat llenguatge de programació.
  • El conjunt de totes les fórmules ben formades a la lògica de primer ordre.

Especificació de llenguatges formalsModifica

Els llenguatges formals trobareu d'una àmplia varietat de formes, com per exemple:

OperacionsModifica

Es poden utilitzar diverses operacions per a produir nous llenguatges a partir d'altres daus. Suposem que L 1 i L 2 són llenguatges sobre un alfabet comú. Llavors:

  • La concatenació L1V2 consisteix de totes aquelles paraules de la manera vw on v és una paraula de L1 i w és una paraula de L2
  • La intersecció L1 & L2 consisteix en totes aquelles paraules que estan contingudes tant en L1 com en L2
  • La unió L1|L2 consisteix en totes aquelles paraules que estan contingudes ja sigui en L1 o en L2
  • El complement ~ L1 consisteix en totes aquelles paraules produïdes sobre l'alfabet de L1 que no estan ja contingudes en L1
  • El quocient L1/L2 consisteix de totes aquelles paraules v per a les quals hi ha una paraula w a L2 tals que vw es troba en L1
  • L'estrella L1* consisteix de totes aquelles paraules que poden ser escrites de la manera W1W2...Wn on tot Wi es troba en L1 i n≥0. (Noteu que aquesta definició inclou ε en qualsevol L*)
  • La intercalació L1*L2 consisteix de totes aquelles paraules que poden ser escrites de la manera v1w1v2w2...vnwn; són paraules tals que la concatenació v1...vn és a L1, i la concatenació w1...wn és a L2

Una pregunta que es fa típicament sobre un determinat llenguatge formal L és com és de difícil decidir si inclou o no una determinada paraula v. Aquest tema és del domini de la teoria de la computabilitat i la teoria de la complexitat computacional.

Per contraposició al llenguatge propi dels éssers vius i en especial el llenguatge humà, considerats llenguatges naturals, es denomina llenguatge formal als llenguatges «artificials» propis de les matemàtiques o la informàtica, els llenguatges artificials són anomenats llenguatges formals (incloent llenguatges de programació). No obstant això, el llenguatge humà té una característica que no es troba en els llenguatges de programació: la diversitat.

El 1956, Noam Chomsky va crear la Jerarquia de Chomsky per organitzar els diferents tipus de llenguatge formal.

Veritats concernents als llenguatges formalsModifica

Teorema 1: El conjunt de llenguatges en general (incloent-hi els no formals) és no numerable .

Lema 1: El conjunt de llenguatges en un alfabet no buit donat és no numerable

Afirmar que un alfabet és no-buit equival a afirmar que aquest alfabet contingui com a mínim un símbol, ergo, només cal demostrar que el conjunt de llenguatges en l'alfabet   és no numerable. Com sabem, un llenguatge L dins   és un subconjunt de  , això ens porta a la conclusió que, el conjunt de tots els llenguatges en   és justament   (el conjunt de tots els subconjunts o conjunt potència de  ) i és evident que   és infinit (de fet, numerable), també ha estat demostrat que si   és un conjunt infinit (numerable o no), llavors   és major que   perquè   passa a ser un conjunt infinit d'ordres de l'infinit, en ser més gran, no hi haurà bijecció entre   i  , el que fa a   un conjunt infinit no numerable, la prova ha finalitzat.

Demostració del Teorema 1: pot derivar fàcilment que l'asseveració delineada en el teorema 1 és vertadera, perquè el conjunt de llenguatges en general és justament una unió infinita de conjunts del tipus  , on   és un conjunt infinit numerable.

Teorema 2: Els llenguatges són conjunts numerables

Se sap que un llenguatge   en un alfabet   és un subconjunt de   i com ja es va fer menció,   és infinit no numerable, per tant,   és com a molt un conjunt infinit no numerable (de la mateixa mida que  ), la prova ha culminat.

Teorema 3: El conjunt de llenguatges formals és numerable

Com sabem un llenguatge formal pot ser generat per una gramàtica formal (o d'estructura de frase), la qual cosa implica que tot llenguatge formal pot ser acceptat per una MT, el que al seu torn implica que es pot definir una bijecció entre el conjunt de llenguatges formals i el conjunt de les MT's (degut a la propietat transitiva de la relació "hi ha bijecció entre   i  "). Per demostrar el teorema s'utilitzarà el concepte de codificació de MT's que s'introdueix en l'estudi de les MT's universals, generalment es codifica una MT amb una funció que té precisament com a domini el conjunt de les MT ' s (l'anomenarem  ) i com a abast  , aquesta funció pot ser una bijecció si el Codomini passa a ser I (un subconjunt de  ) i com   és numerable, aquest subconjunt també serà numerable i com existeix aquesta bijecció (entre   i  ), l'asseveració ha estat demostrada, prova conclosa.

Vegeu tambéModifica

Notes i referènciesModifica

  1. Mellema, Gregory. «formal language» (en anglès). Oxford University Press. [Consulta: 7 febrer 2010].

Enllaç externModifica

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Llenguatge formal