5
$\begingroup$

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.

Improve this question
$\endgroup$
8

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Tim
    May 30, 2014 at 20:43
  • $\begingroup$ 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. $\endgroup$
    – vzn
    May 30, 2014 at 20:50
  • $\begingroup$ "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. $\endgroup$
    – Simon S
    May 31, 2014 at 23:07
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Jun 1, 2014 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.