patternMinor
Which language families admit inductive definitions?
Viewed 0 times
familieslanguagewhichinductiveadmitdefinitions
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#26199, answer score: 4
Revisions (0)
No revisions yet.