Languages Are Defined By A Grammar

intro
prev: Languages and Recognition

To be a language, there must be rules that distinguish what is "in" that language from what is not in the language. If we can distinguish Egyptian hieroglyphs from random doodles, there must be a set of rules that tell us when the pictures are hieroglyphs. Those rules are the grammar.

Technically, the grammar is said to define the language. That is the rules of the grammar say precisely what is in the language and what is not. If the symbols follow the rules laid down by the grammar, they are in the language. If they do not follow the rules, they are not in the language.

Remember that deciding if a set of symbols is in a language is called recognition. Therefore, by applying the rules of the grammar to the set of symbols one can decide if the symbols are recognized by the grammar, and thus are in the language.

Any set of rules which allow you to decide if something is in a language or not is a grammar. However, we are going to concentrate on rules that follow a specific pattern. These rules will be called a formal grammar.

There are rules about what is a formal grammar. We will learn those rules. Since the rules of a formal grammar allow one to distinguish what is a formal grammar from what is not. There is a language of formal grammars and a grammar of formal grammars.

By the way, the rules of what is a formal grammar are quite simple and many people who deal with this topic often at this point quickly just expound the rules and assume that a reader will get the subtleties embodied therein. However, I am going to avoid that and carefully develop the parts of a formal grammar, so that you can see how the parts come together and build complexity.

You can liken this to the way you learned numbers. First one learns to count to ten, then one learns to add, then to count to one hundred, subtract, add two-digit numbers, subtract two-digit numbers, count to a thousand, multiply, recognize numbers by place-value, divide evenly, use fractions, and so on. All despite the fact that the whole of real number arithmetic can be expressed by some simple rules--rules which one only understands by the building up of the parts. I will try to approach this topic the same way.

next: Symbols