There is a very natural model of finite-state reduction, namely the most general finite-state transducer -- one input tape, one output tape, non-deterministic, transitions can be labelled with arbitrary regular sets (with empty strings) on both the input and output side. This can be shown equivalent to Henning's single-symbol operations, but allows for much more intuitive reductions, still within the finite-state realm. The ambiguity Henning speaks of is just the non-determinism.
You can even allow such a transducer to have secondary storage (like a Turing Machine, pushdown automaton, etc) as long as there is a uniform constant bound on the size of the secondary storage.
Taking that a step further, you can use transformations that do arbitrary computations, but again show that the size of memory needed over all inputs is uniformly bounded, that is, there's a $k$ not depending on the input that limits the size of all memory used. Thus you can use pseudo-code, Java or whatever formalism you like, including forking, that is, non-determinism -- as long as you have:
- one input and one output tape/stream
- both streams processed in a single pass
- total memory is uniformly bounded across all forks/threads
In other words, you don't have to model finite-state transformations with transitions on a finite graph, which is a very brittle and finicky programming model. You can use any convenient programming formalism or model with any structuring of memory you like, as long as it satisfies those criteria.
In fact, I propose that as a sort of finite-state equivalent of the Turing-Church thesis. Not quite as crisp as the Turing-Church Thesis in the world of recursive functions, but very useful.
Take any nonregular language $L$. Denote by $L^c$ the complement of $L$ in $A^*$. Then the languages $1 + L$ and $1 + L^c$ are also nonregular. However, $A^* = L + L^c \subseteq (1 + L)(1 + L^c)$ and thus $(1 + L)(1 + L^c) = A^*$. This gives you uncountably many counterexamples, since there are only countably many regular languages and uncountably many subsets of $A^*$ if $A$ is nonempty.
Note: Here $+$ denotes union and $1$ denotes the language reduced to the empty word.
Best Answer
For b), let $L_1=\Sigma^{*}$ and let $L_2$ be any non-regular language you like that contains the empty string. Then $L_1 L_2=\Sigma^{*}$.
For a), let $L_2$ be the set of all strings not of the form $a^n b^n$ for $n\ge 1$. (This is clearly non-regular because its complement is non-regular.) Every string is either not of the form $a^n b^n$, or is of that form, but will no longer be after removing a single $a$. So take $L_1=\{a, \varepsilon\}$, which is finite; then $L_1 L_2 = \Sigma^{*}$, which is regular.