Vés al contingut

Llenguatge formal

De la Viquipèdia, l'enciclopèdia lliure
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 formals

[modifica]
  • 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 formals

[modifica]

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

Operacions

[modifica]

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ó L1L₂ consisteix en totes aquelles paraules de la manera vw on v és una paraula de L1 i w és una paraula de L
  • La intersecció L1 & L₂ consisteix en totes aquelles paraules que estan contingudes tant en L1 com en L
  • La unió L1|L₂ consisteix en totes aquelles paraules que estan contingudes ja sigui en L1 o en L
  • 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/L₂ consisteix en totes aquelles paraules v per a les quals hi ha una paraula w a L₂ tals que vw es troba en L1
  • L'estrella L1* consisteix en totes aquelles paraules que poden ser escrites de la manera W1W₂...Wn on tot Wi es troba en L1 i n≥0. (Noteu que aquesta definició inclou ε en qualsevol L*)
  • La intercalació L1* L₂ consisteix en totes aquelles paraules que poden ser escrites de la manera v1w1vw₂...vnwn; són paraules tals que la concatenació v1...vn és a L1, i la concatenació w1...wn és a L

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 formals

[modifica]

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ències

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

Enllaços externs

[modifica]