linguaggio regolare

linguaggio regolare

linguaggio regolare 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 con β simbolo terminale oppure simbolo terminale seguito da un simbolo non terminale. Le produzioni sono molto semplici e il linguaggio generato risulta piuttosto povero; i problemi che lo riguardano (l’appartenenza di una stringa al linguaggio generato da una data grammatica, le operazioni tra due linguaggi dello stesso tipo ecc.) sono tutti decidibili. Un linguaggio regolare è riconosciuto da un automa a stati finiti.