Llenguatge Formal

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 ${\displaystyle \epsilon \,}$, ${\displaystyle i\,}$ o ${\displaystyle \lambda \,}$.

• Un conjunt de totes les paraules sobre ${\displaystyle \{a,b\}\,}$ .
• El conjunt ${\displaystyle \{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.

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

• Cadenes produïdes per una gramàtica formal (vegeu Jerarquia de Chomsky).
• Cadenes produïdes per una expressió regular.
• Cadenes acceptades per un autòmat, tal com una màquina de Turing.

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

• La concatenació L₁L₂ consisteix en totes aquelles paraules de la manera vw on v és una paraula de L₁ i w és una paraula de L₂
• La intersecció L₁ & L₂ consisteix en totes aquelles paraules que estan contingudes tant en L₁ com en L₂
• La unió L₁|L₂ consisteix en totes aquelles paraules que estan contingudes ja sigui en L₁ o en L₂
• El complement ~ L₁ consisteix en totes aquelles paraules produïdes sobre l'alfabet de L₁ que no estan ja contingudes en L₁
• El quocient L₁/L₂ consisteix en totes aquelles paraules v per a les quals hi ha una paraula w a L₂ tals que vw es troba en L₁
• L'estrella L₁^* consisteix en totes aquelles paraules que poden ser escrites de la manera W₁W₂...W_n on tot W_i es troba en L₁ i n≥0. (Noteu que aquesta definició inclou ε en qualsevol L*)
• La intercalació L₁* L₂ consisteix en totes aquelles paraules que poden ser escrites de la manera v₁w₁v₂w₂...v_nw_n; són paraules tals que la concatenació v₁...v_n és a L₁, i la concatenació w₁...w_n é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.

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

Teorema 2: Els llenguatges són conjunts numerables

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

• Teoria de la computabilitat
• Ciències de la computació
• Llenguatge d'especificació
• Llenguatge formalitzat