Llenguatge formal

De Viquipèdia
Dreceres ràpides: navegació, cerca
Aquesta imatge mostra la relació entre les cadenes de caràcters, les fórmules ben formades i els teorema 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 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 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.

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 \epsilon\, ,  i\, o \lambda\, .

Exemples de llenguatges formals[modifica | modifica el codi]

  • Un conjunt de totes les paraules sobre \{a, b\}\, .
  • El conjunt \{a^n: n\}\, é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 | modifica el codi]

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

Operacions[modifica | modifica el codi]

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ó L 1 V 2 consisteix de totes aquelles paraules de la manera vw on v és una paraula d L < sub> 1 i w és una paraula d L 2
  • L' intersecció L 1 & L 2 consisteix en totes aquelles paraules que estan contingudes tant en L 1 com en L 2
  • L' unió L 1 | L 2 consisteix en totes aquelles paraules que estan contingudes ja sigui en L 1 o en L 2
  • El complement { L 1 consisteix en totes aquelles paraules produïdes sobre l'alfabet de L 1 que no estan ja contingudes en L 1
  • El quocient L 1 / L 2 consisteix de totes aquelles paraules v per a les quals hi ha una paraula w a L < sub> 2 tals que vw es troba en L 1
  • L' estrella L 1 * consisteix de totes aquelles paraules que poden ser escrites de la manera W 1 W 2 ... W n on tot W i es troba en L 1 in = 0. (Noteu que aquesta definició inclou ae en qualsevol L *)
  • La intercalació L 1 * L 2 consisteix de totes aquelles paraules que poden ser escrites de la manera v 1 w 1 v 2 w 2 ... v n w n , són paraules tals que la concatenació v 1 ... v n és a L 1 , i la concatenació w 1 ... w n és a L 2

Una pregunta que es fa típicament sobre un determinat llenguatge formal L és com de difícil és 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 | modifica el codi]

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 que aquest alfabet contingui com a mínim un símbol, ergo, només cal demostrar que el conjunt de llenguatges en l'alfabet \{a\}\, és no numerable. Com sabem, un llenguatge L dins \{a\}\, és un subconjunt de \{a\}^*\, , això ens porta a la conclusió que, el conjunt de tots els llenguatges en \{a\}\, és justament  2^\{a\}^*\, (el conjunt de tots els subconjunts o conjunt potència de \{a\}^*\, ) i és evident que \{a\}^*\, és infinit (de fet, numerable), també ha estat demostrat que si  A és un conjunt infinit (numerable o no), llavors  2^A és major que  A perquè  2^A passa a ser un conjunt infinit d'ordres de l'infinit, en ser més gran, no hi haurà bijecció entre  A i  2^A , el que fa a < math> 2^A </math> 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  2^A , on < math> A </math> és un conjunt infinit numerable.

Teorema 2: Els llenguatges són conjunts numerables

Se sap que un llenguatge  L en un alfabet \Sigma és un subconjunt de \Sigma^* i com ja es va fer menció, \Sigma^* és infinit no numerable, per tant,  L és com a molt un conjunt infinit no numerable (de la mateixa mida que \Sigma^* ), 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  A i  B "). 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  X ) i com a abast \{0, 1\}^*\, , aquesta funció pot ser una bijecció si el Codomini passa a ser I (un subconjunt de \{0, 1\}^*\, ) i com \{0, 1\}^*\, és numerable, aquest subconjunt també serà numerable i com existeix aquesta bijecció (entre  X i  I ), l'asseveració ha estat demostrada, prova conclosa.

Vegeu també[modifica | modifica el codi]

Notes i referències[modifica | modifica el codi]

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

Enllaç extern[modifica | modifica el codi]