Indietro

ⓘ Categoria:Teoria dei linguaggi formali




                                               

Simboli logici

                                               

Albero sintattico

Un albero sintattico o concreto è un albero che rappresenta la struttura sintattica di una stringa in accordo a determinate forme grammaticali. Un programma che produce questalbero viene chiamato parser. Gli alberi sintattici possono essere generati per frasi delle lingue naturali attraverso lelaborazione del linguaggio naturale, così come durante lelaborazione di linguaggi formali e di linguaggi di programmazione. La struttura ad albero è stata mutuata dalla teoria dei grafi per rappresentare lidea intuitiva che le frasi delle lingue naturali possono essere segmentate in unità più piccole ...

                                               

Alfabeto concorrente

Nella teoria dei linguaggi formali, e in particolare nellambito dei linguaggi traccia, un alfabeto concorrente è costituito da una coppia {\displaystyle } in cui Σ {\displaystyle \Sigma } rappresenta un generico alfabeto e θ {\displaystyle \theta } rappresenta una relazione binaria su Σ {\displaystyle \Sigma } detta relazione di indipendenza. Dati due simboli a, b ∈ Σ {\displaystyle a,b\in \Sigma }, se ∈ θ {\displaystyle \in \theta } si dice che a {\displaystyle a} e b {\displaystyle b} sono indipendenti. La relazione di indipendenza θ {\displaystyle \theta } è definita come una relazione ...

                                               

Altezza star

In matematica, considerata una espressione regolare E sopra un alfabeto finito A, si dice altezza star di E lintero naturale che denotiamo con h definito dalle seguenti richieste ricorsive: h E c:= h E per ogni intero positivo c h E *:= h E + 1 h a:= 0 per ogni lettera a ∈ A. h ∅:= 0, h μ:= 0 h E ∩ F:= h E F:= maxh E, h F) Si definisce inoltre come altezza star h L di un linguaggio regolare L la minima delle altezze star delle espressioni regolari che esprimono L. Marcel Schützenberger nel 1965 ha dimostrato che un linguaggio regolare L ha altezza star uguale a 0 se e solo se il suo monoid ...

                                               

Augmented transition network

Una augmented transition network è una tipologia di grafo usato per la definizione operazionale dei linguaggi formali, specialmente per quanto riguarda il parsing di lingue naturali relativamente complessi, ha ampia applicazione in intelligenza artificiale. Una ATN può, in teoria, analizzare la struttura di qualunque frase, anche se complicata. Le ATN sono costruite sullidea di utilizzare macchine a stati finiti modello di Markov per effettuare il parsing di parole. W. A. Woods in "Transition Network Grammars for Natural Language Analysis" indica che aggiungendo il meccanismo di ricorsione ...

                                               

Automa (informatica)

In teoria dei sistemi dinamici, un automa è un sistema dinamico discreto e tempo-invariante. Quando lautoma si trova in un dato stato, esso può accettare solo un sottoinsieme dei simboli del suo alfabeto. Levoluzione di un automa parte da un particolare stato detto stato iniziale. Un sottoinsieme privilegiato dei suoi stati è detto insieme degli stati finali o marcati. In genere gli automi sono deterministici, ovvero dato uno stato ed un simbolo in ingresso è possibile una sola transizione. Esistono comunque anche automi non deterministici, o stocastici.