Non-generable formal languages

Article type: Research Article

Authors: Cenzer, Douglas

Affiliations: University of Florida

Abstract: A set A of words on a finite alphabet Σ is said to be generable if it is the closure of a computable inductive operator; in particular, if S is a semi-Thue system then the set of words derivable in S is generable. An RE set of words (equivalently, a phrase-structure or type 0 language in the sense of Chomsky [Information and Control 2 (1959), 137–167]) which is non-generable is constructed by means of a finite injury priority argument. The construction is refined to obtain a non-generable set of degree 0′ and, for any degree d, a non-generable set of degree ⩽ d.

Keywords: formal language, semi-Thue system, recursive function, inductive definition, generable, degree of unsolvability

DOI: 10.3233/FI-1980-3108

Journal: Fundamenta Informaticae, vol. 3, no. 1, pp. 95-103, 1980