Język rekurencyjny
Z Wikipedii, wolnej encyclopedia
Język rekurencyjny – rodzaj języka formalnego, dla którego z podanymi regułami jego składni da się opracować automatyczny sposób sprawdzania, czy dane słowo jest zbudowane zgodnie z tymi regułami (tzn. czy należy do języka).
W teorii złożoności oznaczana jest literą R[1]. Klasa języków rekurencyjnych nie została uwzględniona w hierarchii Chomsky’ego.