[Overview] [Previous] [Next]

Notes on Terminology

Every regular grammar is a context-free grammar, in the same way that every dog is an animal.

In normal speech we try to be as specific as possible. If we know that, say, Fido is a dog, we generally refer to Fido as a dog. We don't refer to Fido as an animal (unless we are trying to be deliberately vague). But if asked whether Fido is an animal, the correct answer is certainly "yes."

In the same way, if language L is a regular language, we generally refer to L as a regular language. We don't refer to L as a context-free language unless we are being deliberately vague. But if asked whether L is a context-free language, the correct answer is "yes."

The usual convention of being as specific as possible sometimes leads to confusion. If I say language L is a context-free language, I probably mean either (a) L is not regular, or (b) I don't know whether L is regular. If I do know that L is a regular language, I should call it a regular language, not a context-free language.


Copyright © 1996 by David Matuszek
Last modified Feb 26, 1996