stringa di un linguaggio formale

Nella teoria dei linguaggi formali, una stringa è una sequenza composta da un certo numero di oggetti che ci si aspetta venga sottoposta ad elaborazioni come analisi, composizioni e trasformazioni in altre stringhe o strutture discrete come grafi o configurazioni numeriche, senza modificare gli oggetti componenti. Gli oggetti costitutivi possono essere semplici (come bit, caratteri o simboli) o compositi, ma da trattare come se fossero semplici (come parole, espressioni, frammenti di testo o contrassegni di oggetti compositi ma che non si vogliono analizzare o decomporre). Dal punto di vista della costituzione si distinguono innanzi tutto le stringhe di oggetti semplici: stringhe di bit (stringhe binarie), stringhe composte da caratteri (stringhe letterali), stringhe di simboli (stringhe simboliche). Tra le stringhe di oggetti compositi si collocano le stringhe composte da unità lessicali (dette anche token), i frammenti di testo (come i titoli dei paragrafi o le citazioni bibliografiche) e le stringhe che rappresentano molecole dotate di struttura complessiva filamentosa, come quelle che rappresentano una proteina o una struttura di DNA. Tra gli strumenti che possono sottoporre le stringhe ad elaborazioni si distinguono quelli formali, come gli automi, le macchine di Turing, le grammatiche formali o altri e quelli più concreti costituiti da programmi o routine di sistemi software. In linea di principio gli strumenti del secondo genere si possono considerare implementazioni dei primi.