Is the sets of possible morphemes of any given language a regular set, and can thus be recognized by a finite state automaton, or, equivalently, matched by regular expressions?
Or are there any examples of recursive syntax in morphology that requires a context free grammar? (That is, recursive other than in trivial ways like left or right recursion that are still regular.)
The general belief of most linguists was expressed here in 1998 this way:
..the complexity and power required to analyze linguistic data is discontinuous in its distribution.
Coarsely put, we have seen over and over that the simplest tools have the broadest coverage, and more and more complexity is required to expand the coverage less and less. Consider the place of natural language as a whole on the Chomsky hierarchy, for instance. Chomsky (1956) demonstrated that natural language is at least context-free in its complexity, and after a number of failed proofs, it is now commonly agreed that natural language is strongly and weakly trans-context-free (Shieber 1985, Kac 1987, Culy 1985, Bresnan et al. 1982).
Yet what is striking about these results is both the relative infrequency of constructions which demonstrate this complexity and the increase in computational power required to account for them. For example, the constructions which are necessarily at least context-free (such as center embedding) seem fairly uncommon in comparison with constructions which could be fairly characterized as finite state; the constructions which are necessarily trans-context-free are even fewer. In other words, a large subset of language can be handled with relatively simple computational tools; a much smaller subset requires a radically more expensive approach; and an even smaller subset something more expensive still.
-- Bayer et al, "Theoretical and Computational Linguistics: Toward a Mutual Understanding", p.224
That's in terms of syntax, mind you, not morphology. But to the extent one considers morphology as a sort of phonological syntax, the same principles apply, provided one can distinguish and mark exceptions. Much of it is quite simple, even in a complex morphology. Some of it is harder; and agreement phenomena slide right over into syntax again.
Finally, I've been informed by Jerry Sadock, an expert on West Greenlandic Eskimo languages, that polysynthetic Eskimo has recursive morphology; it works very simply through noun incorporation, since complement clauses are nouns. So one can theoretically make recursive words of countably infinite length, though performance constraints appear to make these rare.
IIRC, reduplication and circumfix cannot be modelled using regular grammars.
English: food+and other such things
English: frogs+and other such things
English: play+ed
Before we can begin, a bit of house keeping. I will be using regular expressions, regular languages, and finite state automatas interchangeably. While this is not strictly true, it is sufficient for the scope of this answer. See here for more information.
This is a fairly difficult question as the only way to prove a language is regular is by constructing it from the unions, intersections, compliments, and relative compliments of known relative languages. Obviously natural languages would require a relatively complex regular language to describe it meaning a complicated derivation.
It is much easier to prove a language is not regular. A Pumping Lemma is a necessary (but not sufficient) property of regular languages. I.e. if no pumping lemma can be found for a given language it cannot be regular but the existence of a valid pumping lemma does not prove the language is regular. Essentially, a pumping lemma is any x, y, and z such that y is not empty and xynz can be parsed by a given regular language for all values of n ≥ 0.
I was able to find this lecture which takes an intersection of English and a regular language to result in the language AnBn-1died where A denotes a set of determiner phrases (e.g. {the dog, the cat, the mouse, etc.}) and B denotes a set of transitive verbs (e.g. {chased, bit, admired, etc.}). Remember that the intersection of two regular languages is also regular. This means that if no valid pumping lemma can be found then English, by deduction, must be irregular.
Given this regular language, we have only three choices for y:
Assuming x is "the cat", y is "the dog", and z is "chased died" then for n = 1 we get: "the cat the dog chased died", which is obviously valid (i.e. can be parsed by AnBn-1died). However, for n = 0 we see "the dog chased died" which is obviously invalid. Similarly, for n = 2 ("the dog the cat the cat chased died") or higher, the output is obviously invalid.
More generically, if y is all As and the number of times y appears can be variable then it's impossible to ensure that there for exactly one fewer B than As. Therefore there is no possible y such that y is all As.
Assuming y is all Bs (e.g. x is "the cat the dog the man", y is "admired", and z is "chased died"), we see a similar problem to the above where we cannot ensure exactly one fewer B than As
Assuming y is a mixture (e.g. x is "the cat", y is "the dog chased", and z is "died") seems to work a bit better as both n = 0 and n = 1 are valid ("the cat died" and "the cat the dog chased died" respectively) but things start to fall apart at n = 2: "the cat the dog chased the dog chased died".
More generically, if y is a mixture of As and Bs ten as y repeats some B must occur before some A, which is banned by the regular language AnBn-1died.
There is no possibly y such that xynz is valid for AnBn-1died across all values of n. Therefore xynz is not regular, therefore English is not regular, therefore English cannot be [fully] expressed by a regular expression.
Obviously, this only applies to English and I cannot say that there is no natural language that can be fully expressed by a regular expression, but I highly doubt it. For any natural language one could repeat a similar test to prove it is not regular.
Finally, note that I am talking about describing the language fully. That is not to say that under certain conditions a regular expression cannot describe a subset of a natural language nor that regular expressions cannot approximate a natural language in limited contexts. It depends on the scope you're working with and if you can justify the loss of accuracy for increased computability.
Here is where the thoroughness of my answer takes a drop as I am less familiar with examining and proving context-free grammars. However, I was able to find a few articles which address the issue of natural languages as context-free grammars (usually to the negative). Here is an article proving English is not context-free. Here is another article making a similar argument for Swiss German.
Both these articles seem to take a similar approach to the regular language process above where they user the closure properties of context-free grammars to generate a subset of a natural language then prove that that subset is non-context-free thus proving the full natural language is also non-context free.
Most languages (excluding highly polysynthetic ones) generally have a finite set of morphological word forms. From this, it follows that the language's morphology can in the worst case be described as a regular language simply by a disjunction of all possible forms; the question remains how elegant (and how explanatorily adequate) such an approach will be. Affixation can be very easily modeled via finite state automata without the need to explicitly enumerate each possible form, but full reduplication, stem alteration (like suppletion and ablaut) or templatic morphology (as in the semitic languages) require more work.
A good book on the subject is Finite State Morphology by Beesley & Karttunen (see here). Although it makes reference to a proprietary software (the xfst tool), there are open source alternatives that work very analogously.
