Automata Step by Step

Formal Grammar:

A formal grammar, or sometimes simply grammar, is a precise description of a formal language — that is, of a set of strings. The two main categories of formal grammar are that of generative grammars, which are sets of rules for how strings in a language can be generated, and that of analytic grammars, which are sets of rules for how a string can be analyzed to determine whether it is a member of the language. In short, an analytic grammar describes how to recognize when strings are members in the set, whereas a generative grammar describes how to write only those strings in the set.

Now it is necessary to understand the definitions of “String”, “Alphabet”,”Sequence” and “Language”. I will discuss them in the next Post.