1
$\begingroup$

The family of regular sets is the smallest full trio (closed under intersection with regular sets, homomorphisms, and inverse of homomorphisms) and also the smallest full AFL (closed under union, concatenation, and Kleene star).

The definition of regular expressions is in terms of closure under union, concatenation, and Kleene star.

Why can regular expressions be defined without mentioning closure under the three full trio operations: intersection with regular sets, homomorphisms, and inverse of homomorphisms?

If a family of language is closed under union, concatenation, and Kleene star, is it necessarily closed under intersection with regular sets, homomorphisms, and inverse of homomorphisms? (Ullman's Introduction to Automata, Language and Computation only mentions that closure under union, concatenation, or intersection with regular sets can be derived from closure on the other 5 operations in the definition of AFLs.)

Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

The answer is no. Take a non-regular language $L$ on the alphabet $A = \{a, b\}$, say $L = \{a^nb^n \mid n \geqslant 0\}$ and consider the family ${\cal L} = \{L^*\}$. Then $\cal L$ is closed under union, product and star, but it is not closed under intersection with regular sets (take the intersection with any cofinite language), homomorphisms (take the morphism $\varphi$ defined by $\varphi(u) = 1$ for every word $u$), inverse of homomorphisms (take the same $\varphi$ and observe that $\varphi^{-1}(L^*) = A^*$).

Let me also answer your first question "Why can regular expressions be defined without mentioning closure ...". Regular languages are sometimes defined using regular expressions and sometimes using automata. There is no harm as long as these two definitions define the same class. This is Kleene's theorem, which implies that regular languages are closed under intersection and complement. However, these two definitions are no longer equivalent in the more general setting described below.

Let $M$ be a monoid. The rational subsets of $M$ are those defined from singletons using the operations of finite union, product and star. Here the product of two subsets $S$ and $T$ is the set $ST = \{st \mid s \in S, t \in T\}$ and $S^*$ is the submonoid of $M$ generated by $S$. But now, rational sets are not necessarily closed under intersection or complement. They are closed under monoid homomorphisms, but not necessarily under inverses of homomorphisms.

A subset $P$ of $M$ is recognizable if there is a finite monoid $F$ and a monoid homomorphism $f: M \to F$ such that $P = f^{-1}(f(P))$. One can show that recognizable sets are closed under finite union, finite intersection, complement and inverse of homomorphisms. However, there are not necessarily closed under homomorphisms.

To come back to languages, if $M$ is a free monoid, the two notions, rational and recognizable, coincide and both define the regular sets.

$\endgroup$
3
  • $\begingroup$ Thanks. If I may ask, is your book irif.fr/~jep//PDF/MPRI/MPRI.pdf focused within finite automata and therefore within regular/rational languages only, and nothing about CFL, CSL, recursive, r.e.? Or is it unrelated to Chomsky hierarchy and not subject to the classifications/types of languages in the hierarchy? Are stringology, combinatorics on word, and automatic sequences also focused within finite automata and regular/rational languages only? $\endgroup$ Commented Jun 24, 2020 at 16:04
  • $\begingroup$ Yes my book is not concerned with CFL, CSL and recursive languages. It is an algebraic and topological approach to subclasses of regular languages called varieties of languages. $\endgroup$ Commented Jun 25, 2020 at 8:43
  • $\begingroup$ Thanks. Does your book cover the same topic as stringology, combinatorics on word, and automatic sequences ? What are stringology, combinatorics on word, and automatic sequences concerned with? $\endgroup$ Commented Jun 25, 2020 at 12:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.