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.)

  • 1
    I'm pretty sure that in Turkish the suffix -ki can take an inflected noun and renominalise it, so that it can take further inflections. If I am right, then Turkish morphology is at least theoretically arbitrarily embedded. – Colin Fine Feb 5 '13 at 14:56
  • 1
    @ColinFine Here's an example: "bendeki" (the one that I have), "bendekindeki" (the one that the one that I have has), "bendekindekindeki" (the one that the one that the one that I have has has) and so on. – cyco130 Apr 10 '14 at 9:54
  • When I asked questions about the number of possible forms of Japanese verbs people seemed to believe that there is no limit because of the possibility of recursion: [1] What is the maximum number of forms a (modern) Japanese verb can take?, [2] How many forms can a Japanese verb take? – hippietrail Apr 16 '14 at 2:03
  • And somebody has just posted the Japanese example 知らなくなくなくなくなくなくない - I can't tell you whether the only way to analyse this is as a single inflected verb or if you could also break it into particles and/or auxiliaries, etc. This is the extra dimension you get in languages which don't indicate word breaks in their orthography. – hippietrail Apr 16 '14 at 2:47

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.

  • 2
    So it's the old 80-20 rule (also called the law of diminishing returns)? 80% of the coverage is handled by 20% of the effort. I alluded to this in my answer but this goes into much more detail. – acattle Feb 1 '13 at 17:53
  • 1
    The article goes on to point out that such painstaking coverage is economically self-defeating, since corpus-based systems train up their own rules, which usually include only what is necessary to harvest the low-hanging fruit. Because of the builtin redundancy of natural language, that was good enough even in 1995 to extract 95% of the meaning from a text without any parsing at all. – jlawler Feb 1 '13 at 17:58
  • I feel like the best answer would be if we merged ours together: technically natural languages aren't regular nor are they context-free but in practice a well designed regular language/context-free grammar is usually sufficient. – acattle Feb 1 '13 at 19:51
  • Well, we each voted for the other one; that's good enough, by our standards. There is no best answer, anyway. That's the point, if there is any, to the stack exchange model. – jlawler Feb 1 '13 at 20:06

IIRC, reduplication and circumfix cannot be modelled using regular grammars.

Examples of reduplication:

English: food+and other such things

  • Hindi: khaanaa+vaanaa
  • Kannada: ooTaa+geeTaa

English: frogs+and other such things

  • Hindi: mai.NDak+vai.NDak
  • Kannada: kappe+gippe

Example of circumfix:

English: play+ed

  • German: ge-spiel-t

Natural Languages as Regular Languages

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.

Testing English for Irregularity

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:

  1. y is all As
  2. y is all Bs
  3. y is a mixture of As and Bs

*y* is all As

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.

*y* is all Bs

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

*y* is a mixture of As and Bs

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.

Natural Languages as Context-free Grammars

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.

  • 2
    The question was about morphology. I think nobody questions that syntax cannot be described by finite-state automata. – Fryie Feb 3 '13 at 2:32
  • @Fryie Fair enough. In that case I'd have to say my anecdotal experience is that they are not regular nor context-free due to irregular verb forms and the context needed in inflections (French uses the base form verb ending [-er, -ir, -re, etc.]. Korean uses whether or not the base form verb has a coda and/or is 하다 [hada, to do]). Also, In morphologically rich languages like Korean, inflections and morphological grammatical markers cannot be pumped indefinitely, thus failing pumping lemma. – acattle Feb 3 '13 at 5:16
  • 2
    but irregular verb forms etc. can simply be accomodated by enumeration – Fryie Feb 3 '13 at 5:46
  • It would benefit your answer to get your scientific language right. "A pumping lemma is any x, y, and z ...". No, the pumping lemma for regular languages is a lemma which states that all regular languages have a certain property. – dainichi Feb 5 '13 at 10:25
  • Sure, but informally, and at talks, it's common for specialists to speak of it this way. It doesn't make any difference for natural languages, anyway; unlike mathematics, linguistics has data, so nothing can ever be proved the way it can in math. – jlawler Feb 6 '13 at 18:20

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.

  • Is it really true that most languages have a finite set of morphological word forms? Morris Halle observed an apparent case of centre embedding in morphology: We can have an anti-missile missile, namely a missile whose role is to counter-act missiles, but also an anti- anti-missile missile missile, a missile whose role is to counter-act missiles which themselves counteract missiles, and ad inifinitum to the limits of our processing abilities. If you have in mind inflectional morphology then sure, maybe, but derivational morphology rocks the boat a bit. – P Elliott Apr 10 '14 at 18:06
  • 1
    See the comments under the question. Turkish has theoretically infinite inflectional forms due to "-ki" suffix. If you also consider derivational morphology, I expect most languages can add deverbal + denominal suffix pairs in a potentially infinite way. – cyco130 Apr 11 '14 at 6:01
  • 1
    Fair enough; an infinite number of derivational suffixes or a suffix like "-ki" can be modeled by a regular language, though, even if the set is infinite. The embedding example with the anti-missile is more interesting; it's true that this cannot be modeled by regular languages. I would argue that the traditional line drawn between morphology and syntax can be blurry and that indeed in such a case morphology behaves more 'syntax-like'; still, a very large portion of morphology is regular, and I think that's an important insight. – Fryie Apr 11 '14 at 9:01
  • The set of existing forms is not the set of all possible forms. – Kaz Nov 10 '15 at 15:37
  • Then what is the set of all possible forms? We can build nice theoretical models about what's possible in a language and it's all useful and such, but in the end, language is so dynamic and ever-changing that it does not represent reality all that well. The notion of possible forms makes sense for formal languages but it is much less clear that it does so for natural ones. – Fryie Nov 10 '15 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.