Substitution of a letter with a regular expressions in regular expressions identities

30 Views Asked by At

There is an exercise in "Introduction to computer theory" by Daniel IA Cohen (ch. 4, ex. 20) the main part of which goes like:

Explain why we can take any pair of equivalent regular expressions and replace the letter $a$ in both with any regular expression $\mathbf R$ and the letter $b$ with any regular expression $\mathbf S$ and the resulting regular expressions will have the same language.

This book is oriented on a reader unaccostumed to a rigor mathematical language and throughout all the book the author stresses that any kind of a formal notation is of a secondary importance to the ideas that it conveys, thus I think that an informal argument is expected here.

Question 1 What kind of argument should it be? How such a question can be approached?

I find it super difficult to understand because it's not only about a transformation of a particular regular expression, but about the validity of a statement about their generated languages. So I come up with something like "assume we have regular expressions $\mathbf R_1$ and $\mathbf R_2$ which generate the same langauge. A letter $a$ in $\mathbf R_1$ can be met in one of the following subexpressions: $a$, $(a)$, $a \mathbf r$, $a + \mathbf r$, $a^*$..." and it represents a letter $a$ or a string of $a$'s (for $a^*$) in a generated string. And then I just stumble as it seems that I should assume too much to go on: "every string that is generated by $\mathbf R_1$ should also be generated by $\mathbf R_2$ so there should be a part in $\mathbf R_2$ which corresponds to either $a$, or a concatenation of several $a$'s and if we just replace both of this occurences with a regular expression $\mathbf R$ then it will be correspond to one of the words from the language generated by $\mathbf R$ and it will match its said counterpart in $\mathbf R_2$.

Is it an acceptable kind of answer in the informal context and if not, what is the better or an improved version?

Question 2 Where can I find a more strict approach to it?

I can imagine two ways of doing it, first (as the chapter is about finite-state automata) we might prove some kind of correspondence between regular expressions and finite-state automata and the property in question will follow from it. Second, it seems that I have an urge of talking formally in an informal setting, so similar properties should be studied in logic courses in the context of e.g. formal language of Propositional Logic, and I should study a book like Enderton or Mendelson.