A grammar, loosely speaking, is a set of rules that can be applied to words to generate sentences in a language. For example, with the grammar of the English language, one can form syntactically correct sentences such as “The elephant drove his bicycle to the moon,” regardless whether the sentence is meaningful or not.
The mathematical abstraction of a grammar is known as a formal grammar. Instead of generating sentences from words, a formal grammar generates words from symbols and other words. The following basic ingredients are necessary in a formal grammar:
a collection of rules, called rewriting rules, specifying how one can generate new words from existing ones, and
a collection of initial words that serve to initialize the generation of new words.
To see how these rewriting rules work, let us look at an example. Let be the alphabet as well as the set of initial words. With the rewriting rules given by: from a word we can form the word , as well as the word , we would be able to generate words like
However, words such as
can not be produced.
Note that by adding an extra symbol to the above alphabet, and two additional rewriting rules given by “from form ” and “from form ”, it is not hard to see that any word that can be generated by the first grammar can be generated by this new grammar.
Formalizing what we have discussed above, we say that a formal grammar is a quadruple , where
is a rewriting system;
is a subset of whose elements are called non-terminals, and the set of terminals;
an element called the starting symbol.
Instead of writing , the quadruple is another way of representing (as long as the conditions and are satisfied).
A formal grammar is variously known as a phrase-structure grammar, an unrestricted grammar, or simply a grammar. A formal grammar is sometimes also called a rewriting system in the literature, although the two notions are distinct on PlanetMath.
Given a formal grammar , a word over such that is called a sentential form of . A sentential form over is called a word generated by . The set of all words generated by is called the formal language generated by , and is denoted by . In other words,
where is the derivability relation in the rewriting system . A formal language is also known as a phrase-structure language.
A language over an alphabet is said to be generable by a formal grammar if there is a formal grammar such that .
Example. Continuing from the example in the previous section, we can put and . For the set of productions, we have four
Then is a formal grammar. It is not hard to see that , as . In fact, consists of all words such that occurs at least once and occurs at most once.
Not every language can be generated by a formal grammar. Given a finite alphabet , is countably infinite, and therefore there are uncountably many languages over . However, there are only a countably infinitely many languages that can be generated by formal grammars.
Every language generated by a formal grammar is recursively enumerable.
- 1 H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
|Date of creation||2013-03-22 16:27:10|
|Last modified on||2013-03-22 16:27:10|
|Last modified by||CWoo (3771)|
|Defines||generable by a formal grammar|