Indice
10 relazioni: Automa a pila, Backus-Naur Form, Forma normale di Chomsky, Forma normale di Kuroda, Grammatica formale, Grammatica libera dal contesto, Informatica, Linguaggio formale, Linguaggio libero dal contesto, Stringa vuota.
Automa a pila
Un automa a pila o (noto anche con la sigla PDA, dall'inglese pushdown automaton) è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila, una struttura dati i cui dati possono essere estratti in ordine necessariamente inverso rispetto a quello di inserimento.
Vedere Forma normale di Greibach e Automa a pila
Backus-Naur Form
La BNF (Backus-Naur Form o Backus Normal Form) è una metasintassi, ovvero un formalismo attraverso cui è possibile descrivere la sintassi di linguaggi formali (il prefisso meta ha proprio a che vedere con la natura circolare di questa definizione).
Vedere Forma normale di Greibach e Backus-Naur Form
Forma normale di Chomsky
Nella teoria dei linguaggi formali, una grammatica libera dal contesto si dice essere nella forma normale di Chomsky (CNF,. o FNC, dall'inglese Chomsky normal form) (scoperta da Noam Chomsky) se tutte le sue regole di produzione sono nella forma seguente: dove A, B e C sono simboli non terminali, a è un simbolo terminale (un simbolo che rappresenta un valore costante), S è l'assioma di partenza, varepsilon è la stringa vuota, e B ne S land C ne S.
Vedere Forma normale di Greibach e Forma normale di Chomsky
Forma normale di Kuroda
In informatica, una grammatica formale è espressa in forma normale di Kuroda se tutte le sue produzioni sono della forma: dove A, B, C e D sono simboli non terminali α è un simbolo terminale.
Vedere Forma normale di Greibach e Forma normale di Kuroda
Grammatica formale
La grammatica formale, nella teoria dei linguaggi formali, è una struttura astratta che descrive un linguaggio formale in modo preciso, è cioè un sistema di regole che delineano matematicamente un insieme (di solito infinito) di sequenze finite di simboli (stringhe) appartenenti ad un alfabeto anch'esso finito.
Vedere Forma normale di Greibach e Grammatica formale
Grammatica libera dal contesto
In informatica e in linguistica, una grammatica libera dal contesto (o non contestuale, context-free o CFG) è una grammatica formale in cui ogni regola sintattica è espressa sotto forma di derivazione di un simbolo a sinistra a partire da uno o più simboli a destra.
Vedere Forma normale di Greibach e Grammatica libera dal contesto
Informatica
Linformatica è la scienza o disciplina che si occupa del trattamento dell'informazione mediante procedure automatizzate, avendo in particolare per oggetto lo studio dei fondamenti teorici dell'informazione, della sua computazione a livello logico e delle tecniche pratiche per la sua implementazione e applicazione in sistemi elettronici automatizzati detti quindi sistemi informatici; come tale è una disciplina fortemente connessa con la logica matematica, l'automatica, l'elettronica e anche l'elettromeccanica.
Vedere Forma normale di Greibach e Informatica
Linguaggio formale
Per linguaggio formale, in matematica, logica, informatica e linguistica, si intende un insieme di stringhe costruite sopra un alfabeto, cioè sopra un insieme di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.
Vedere Forma normale di Greibach e Linguaggio formale
Linguaggio libero dal contesto
Un linguaggio libero dal contesto (o non contestuale, o context-free) è un linguaggio formale generato da una grammatica che sia, appunto, non contestuale, ovvero tale che le cui regole agiscono su simboli non terminali a prescindere dal contesto in cui essi appaiono.
Vedere Forma normale di Greibach e Linguaggio libero dal contesto
Stringa vuota
Nella teoria del linguaggio formale, la stringa vuota o parola vuota è la stringa (unica possibile) di lunghezza zero.