Vés al contingut

Lema de bombament per a llenguatges regulars

De la Viquipèdia, l'enciclopèdia lliure

En la teoria de llenguatges formals, el lema del bombament per a llenguatges regulars descriu una propietat essencial de tot llenguatge regular. Informalment, diu que qualsevol paraula suficientment llarga en un llenguatge regular pot ser bombada - això és, repetir una secció en la meitat de la paraula un nombre arbitrari de vegades - per produir una nova paraula que també pertany al mateix llenguatge.

El lema de bombament fou enunciat per primera vegada per I. Bar-Hillel, M. Perles, I. Shamir en 1961.[1] És útil per demostrar que un llenguatge específic no és regular.

Enunciat formal

[modifica]

Sigui un llenguatge regular. Aleshores existeix un enter (al que anomenem "longitud de bombament" i que dependrà exclusivament de ) tal que qualsevol cadena pertanyent a , de longitud major o igual que , pot ser escrita com (p. ex. dividint en tres subcadenes), de forma que es satisfacin les següents condicions:

és la subcadena que pot ser bombada (esborrada o repetida un número de vegades com s'indica en (3), i la cadena resultant seguirà pertanyent a ). (1) significa que la cadena que es bomba ha de tenir com a mínim longitud u. (2) significa que ha d'estar dintre dels primers caràcters. No hi ha restriccions sobre de o .

Referències

[modifica]
  1. Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.

Enllaços externs

[modifica]