Stringa (linguaggi formali): differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
| (62 versioni intermedie di 40 utenti non mostrate) | |||
Riga 1:
{{F|matematica|dicembre 2010}}
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 [[grafo|grafi]] o configurazioni numeriche, senza modificare gli oggetti componenti.
Gli oggetti costitutivi possono essere semplici (come
Dal punto di vista della costituzione si distinguono innanzi tutto le stringhe di oggetti semplici: stringhe di [[Bit (informatica)|bit]] (
Tra gli strumenti che possono sottoporre le stringhe ad elaborazioni si distinguono quelli formali, come gli [[automa (informatica)|automi]], le [[macchina di Turing|macchine di Turing]], le [[grammatiche formali]] o altri [[sistema di riscrittura|sistemi di riscrittura]] e quelli più concreti costituiti da programmi o
== Trattamento formale ==
Dato un [[insieme finito]] [[insieme vuoto|non-vuoto]] <math>\Sigma</math>, chiamato [[alfabeto (teoria dei linguaggi formali)|alfabeto]], composto da ''caratteri'' o ''simboli'' è possibile definire una ''stringa'' (o ''parola'') sull'alfabeto <math>\Sigma</math> come [[disposizione]] (o [[ennupla]]) finita dei caratteri di <math>\Sigma</math><ref name="uniroma1">{{Cita web
|url = http://www.dis.uniroma1.it/~fiii/materiale_schaerf/9-Linguaggi.pdf
|titolo = Linguaggi formali e grammatiche di Chomsky
|autore =
|editore =
|data =
|formato = doc
|pagine = 4-7
|accesso = 19 maggio 2017
|urlarchivio = https://web.archive.org/web/20100602063032/http://www.dis.uniroma1.it/~fiii/materiale_schaerf/9-Linguaggi.pdf
|dataarchivio = 2 giugno 2010
|urlmorto = no
}}</ref><ref name="PoliBa">{{Cita web
|url = http://www-ictserv.poliba.it/piscitelli/doc/lucidi%20LFC/2_LFC_i%20linguaggi%20formali_12.pdf
|titolo = Linguaggi Formali e Compilatori
|autore = Giacomo Piscitelli
|sito =
|data =
|formato = pdf
|pagina = 4
|accesso = 17 maggio 2017
|urlarchivio = https://web.archive.org/web/20150616083424/http://www-ictserv.poliba.it/piscitelli/doc/lucidi%20LFC/2_LFC_i%20linguaggi%20formali_12.pdf
|dataarchivio = 16 giugno 2015
|urlmorto = sì
}}</ref>.
È possibile definire la ''lunghezza'' di una stringa, <math>\left | w \right |</math> come il numero di caratteri presenti nella stringa. La stringa di lunghezza 0 prende il nome di ''[[stringa vuota]]'' o ''stringa nulla'' e viene indicata con <math>\varepsilon</math> o <math>\lambda</math><ref name="uniroma1" />.
Per esempio, preso l'alfabeto binario <math>\Sigma = \left \{ 0, 1 \right \}</math>, alcune delle parole che possono essere generate a partire da <math>\Sigma</math> sono le stringhe <math>\left \{ \varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, \cdots \right \} </math>.
Possiamo definire l'operazione ''elevamento a potenza'' di un alfabeto, <math>\Sigma^{k}</math>, come l'insieme di stringhe di lunghezza k sull'alfabeto, ponendo <math>\Sigma^{0} = \varepsilon</math>.
L'insieme di tutte le parole sull'alfabeto <math>\Sigma</math> è indicato con <math>\Sigma^{*}</math>. Data l'esistenza di una [[corrispondenza biunivoca]] tra la tupla <math>\left ( a_1, a_2, \cdots, a_n \right )</math> e la stringa <math>a_1 a_2 \cdots a_n</math>, è possibile definire la [[star chiusura]] come l'[[insieme infinito]] <math>\Sigma^{*} = \bigcup_{n \in \N} \Sigma^{n}</math>.
È possibile definire l'insieme delle parole di lunghezza sull'alfabeto <math>\Sigma</math>, la [[cross chiusura]], come <math>\Sigma^{+} = \Sigma^{*} \setminus \Sigma^{0}</math>.
È inoltre possibile definire un'[[operazione binaria]] denominata ''concatenazione di stringhe''<ref name="uniroma1" />. Siano ''s'' e ''t'' appartenenti rispettivamente agli alfabeti <math>\Sigma^{\prime}</math> e <math>\Sigma^{\prime\prime}</math>. La concatenazione delle due stringhe, indicata come ''st'', è definita come la stringa di lunghezza <math>\left | s \right | + \left | t \right |</math> appartenente a <math>\Sigma^{\prime} \cup \Sigma^{\prime\prime}</math> , che presenta ordinatamente i caratteri di ''s'' seguiti dai simboli di ''t''.
Ad esempio se <math>s = \mbox{topo}</math> e <math>t = \mbox{ragno}</math> allora <math>st = \mbox{toporagno}</math> e <math>ts = \mbox{ragnotopo}</math>.
La concatenazione di stringhe è un'operazione [[associatività|associativa]], ma non [[commutatività|commutativa]]<ref name="uniroma1" />. Rispetto alla concatenazione, la stringa vuota è l'[[elemento neutro]]. In termini [[algebra|algebrici]], l'insieme <math>\Sigma^{*}</math> costituisce un [[monoide]] rispetto alla concatenazione di stringhe<ref name="uniroma1" />. <math>\Sigma^{*}</math> è il [[monoide libero]] generato da <math>\Sigma</math>, mentre <math>\Sigma^{+}</math> è il relativo [[semigruppo]] libero.
Sempre da un punto di vista algebrico, dato che la lunghezza è un [[numero naturale]], è possibile dire che la funzione lunghezza definisce un [[omomorfismo]] da <math>\Sigma^{*}</math> in <math>\N</math>.
Una stringa ''s'' si dice ''sottostringa'' o ''fattore'' di ''t'' se esistono due stringhe ''u'' e ''v'' tali che <math>t = usv</math>. Se <math>u = \varepsilon</math> o <math>v = \varepsilon</math> si parla di ''prefisso'' o ''suffisso'' della stringa ''t''. La [[relazione binaria|relazione]] "è una sottostringa di" definisce una [[relazione d'ordine]] su <math>\Sigma^{*}</math>, il cui minimo risulta la stringa vuota.
Se l'alfabeto <math>\Sigma^{*}</math> è [[relazione d'ordine#Ordinamenti ben fondati|ben ordinato]], il cosiddetto [[ordine lessicografico]] costituisce un altro [[insieme totalmente ordinato|ordinamento totale]] su <math>\Sigma^{*}</math> di frequente utilizzo per le applicazioni informatiche.
Un insieme di stringhe su <math>\Sigma</math> (cioè un [[sottoinsieme]] di <math>\Sigma^{*}</math>) è anche detto ''[[linguaggio formale]]'' su <math>\Sigma</math>. Nonostante l'alfabeto <math>\Sigma</math> sia finito e non vuoto e le stringhe siano di lunghezza finita, i linguaggi formali possono avere [[cardinalità]] [[infinito (matematica)|infinita]] o [[insieme vuoto|nulla]]. Esempi di linguaggi formali sono forniti dalle [[espressione regolare|espressioni regolari]] e dalle [[grammatica formale|grammatiche formali]].
== Note ==
<references />
== Bibliografia ==
* {{cita libro |nome = John E. |cognome = Hopcroft |wkautore = John Hopcroft |coautori = Rajeev Motwani; [[Jeffrey Ullman|Jeffrey D. Ullman]] |titolo = Introduction to Automata Theory, Languages, and Computation |editore = Addison Wesley |anno = 2006 |mese = luglio |giorno = 15 |lingua = inglese |capitolo = Strings |ISBN = 978-0-321-46225-1}}
* {{cita libro |nome = Martin |cognome = Davis |wkautore = Martin Davis |coautori = Ron Sigal; Elaine J. Weyuker |titolo = Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science |editore = Morgan Kaufmann |anno = 1994 |mese = febbraio |giorno = 17 |lingua = inglese |capitolo = Alphabets and Strings |ISBN = 978-0-12-206382-4}}
==
* [[Stringa (informatica)]]
* [[Alfabeto (teoria dei linguaggi formali)]]
* [[Linguaggio formale]]
{{portale|informatica|matematica}}
[[Categoria:Teoria dei linguaggi formali]]
| |||