# Which language families admit inductive definitions?

I am self-learning about formal languages. I learned that the family of the regular languages can be defined inductively, in terms of the operations they are closed under (namely the smallest fix-point). This definition doesn't rely on regular grammars or finite state machines.

I wonder which other families of formal languages can be defined inductively; in particular, I am interested in the classic classes of the Chomsky hierarchy but also the (semi-)decidable languages.

• Does Chomsky–Schützenberger correspond to your notion? cs.stackexchange.com/a/19799/683 May 29, 2014 at 2:32
• Maybe. I followed here en.wikipedia.org/wiki/Template:Formal_languages_and_grammars.
– Tim
May 29, 2014 at 2:39
• Recursive languages can: en.wikipedia.org/wiki/Recursive_language May 29, 2014 at 2:57
• @Luke: (1) what can they do? (2) I only saw recursive languages can be closed under certain operations. I didn't see they can be defined that way.
– Tim
May 29, 2014 at 2:59
• For what it's worth, the class of all languages is the closure of $\{\epsilon\}$ under the operations of concatenation of a single character, and arbitrary union. May 29, 2014 at 8:44

We can study families of languages in terms of their closure properties, it then makes sense to consider languages which generate the family under those closure properties.

Some work in this area has been done (particularly for cones/AFLs) and there may be known results for some or all of the families of languages that you mention but the only result which I know off the top of my head is for the context-free languages:

The context-free languages are the smallest cone generated by the Dyck language on two symbols.

For a proof of this theorem and some similar results for other language classes within context-free see Berstel's book which is now freely available on his website here.

the recursively-enumerable languages are literally recursively enumerable. this was proven originally mainly with the Lambda calculus which has a 1-1 correspondence with recursively enumerable languages. in other words all legal Lambda Calculus expressions (which can be defined as a closed set of recursive construction operations) correspond to the recursively enumerable languages. all other languages you list are a subset of recursively-enumerable so therefore also can be generated recursively.

• thanks. can you point out how recursivley-enumerable languages can be defined recursively and in terms of the operations under which they are closed, just like how regular languages are defined in my link to Wikipedia?
– Tim
May 30, 2014 at 20:43
• admittedly this answer is a sketch & has some handwaving. (1) legal lambda expressions can be recursively defined mainly in terms of balanced parenthesis and nested expressions etc, details are in early papers exploring lambda calculus, and (2) as long as limited grammar rules exist for each grammar class, all instances of those languages can be enumerated, and anything that can be enumerated can be enumerated using a recursive algorithm. so unless you define your question terms more technically (which may not be possible) the answer remains a sketch.
– vzn
May 30, 2014 at 20:50
• "all other languages [classes] you list are a subset of recursively-enumerable so therefore also can be generated recursively." If this is true, it would also hold for R. Can you provide a decidable grammar or a set of rules that only generates lambda expression that coresspond to a decidable language? I am not aware that this was done before. May 31, 2014 at 23:07
• sorry replace "so therefore" with "and". there are actually quite a few ways to generate languages and most methods can lead to recursive definitions. arguably any algorithm process to generate languages can be recursively constructed. might work up some examples/details later.
– vzn
Jun 1, 2014 at 3:28