Grammaire régulière

In theoretical computer science and formal language theory, a regular grammar is a grammar that is right-regular or left-regular. While their exact definition varies from textbook to textbook, they all require that all production rules have at most one non-terminal symbol; that symbol is either always at the end or always at the start of the rule's right-hand side. Every regular grammar describes a regular language. A right-regular grammar (also called right-linear grammar) is a formal grammar (N, Σ, P, S) in which all production rules in P are of one of the following forms: A → a A → aB A → ε where A, B, S ∈ N are non-terminal symbols, a ∈ Σ is a terminal symbol, and ε denotes the empty string, i.e. the string of length 0. S is called the start symbol. In a left-regular grammar, (also called left-linear grammar), all rules obey the forms A → a A → Ba A → ε The language described by a given grammar is the set of all strings that contain only terminal symbols and can be derived from the start symbol by repeated application of production rules. Two grammars are called weakly equivalent if they describe the same language. Rules of both kinds must not be mixed; for example, the grammar with rule set { S→aT, T→Sb, S→ε } is not regular, and describes the language , which is not regular, either. Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages. An extended right-regular grammar is one in which all rules obey one of A → w, where A is a non-terminal in N and w is in a (possibly empty) string of terminals Σ* A → wB, where A and B are in N and w is in Σ*. Some authors call this type of grammar a right-regular grammar (or right-linear grammar) and the type above a strictly right-regular grammar (or strictly right-linear grammar). An extended left-regular grammar is one in which all rules obey one of A → w, where A is a non-terminal in N and w is in Σ* A → Bw, where A and B are in N and w is in Σ*.