Formal grammars of these two languages of hereditarily finite sets.

29 Views Asked by At

This is a follow-up to my previous question, here: How to formally define this language of hereditarily finite sets?. Let our alphabet be composed of the left brace, right brace, the comma, and the empty set symbol $\emptyset$. I want a formal definition in terms of formal grammars of two languages $L$ and $L'$. Language $L$ is simply the language of hereditarily finite sets, augmented with the empty set symbol. So, for example, the three words $\emptyset$, $\{\}$, and $\{\{\}\}$, are all in language $L$, which represent the empty set, the empty set, and the set containing the empty set, respectively. Language $L'$ is a proper subset of language $L$, where we must replace every instance of the word $\{\}$ with $\emptyset$. So, while $\emptyset$ and $\{\emptyset\}$ are both valid words of language $L'$, the words $\{\}$ and $\{\{\}\}$ are not valid words of language $L'$, although they are valid words of language $L$. Can anyone formally define the intuitive notion of these two languages in terms of formal grammars?