linguaggio context-free
linguaggio context-free
linguaggio context-free linguaggio formale generato da una → grammatica generativa G = 〈AN, A, P, s〉, dove A è l’alfabeto dei simboli terminali, AN è l’alfabeto dei simboli non terminali, s ∈ AN è l’assioma, P è un insieme di regole di riscrittura (produzioni) del tipo α → β, così intendendo che la stringa a sinistra della freccia può essere rimpiazzata da quella a destra, con α ∈ AN e β ∈ (AN ∪ A)+. Tali regole indicano che un simbolo non terminale può essere sostituito da una stringa non vuota di simboli terminali e non terminali. Poiché a sinistra della freccia compare solo un simbolo non terminale, la regola si applica indipendentemente dal contesto (context-free). Linguaggi di questo tipo sono alla base di linguaggi di programmazione, a partire da uno dei primi linguaggi evoluti l’ALGOL, da cui si sono sviluppati i linguaggi di programmazione oggi in uso.