these configurations will be saved for each time you visit this page using this browser
In a left regular grammar (also called left linear grammar), all rules obey the forms # A → a - where A is a non-terminal in N and a is a terminal in Σ # A → Ba - where A and B are in N and a is in Σ # A → ε - where A is in N and ε is the empty string.
An example of a right regular grammar G with N = {S, A}, Σ = {a, b, c}, P consists of the following rules : S → aS : S → bA : A → ε : A → cA and S is the start symbol. This grammar describes the same language as the regular expression a*bc*.
A regular grammar is a left regular or right regular grammar.
Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.
An extended left regular grammar is one in which all rules obey one of # A → a - where A is a non-terminal in N and a is a terminal in Σ # A → Bw - where A and B are in N and w is in Σ* # A → ε - where A is in N and ε is the empty string. Some authors call this type of grammar a left regular grammar and the type above a strictly left regular grammar.
Every strict right regular grammar is extended right regular, while every extended right regular grammar can be made strict by inserting new nonterminals, such that the result generates the same language; hence, extended right regular grammars generate the regular languages as well. Analogously, so do the extended left regular grammars.
If empty productions are disallowed, only all regular languages that do not include the empty string can be generated.
For instance, the grammar G with N = {S, A}, Σ = {a, b}, P with start symbol S and rules : S → aA : A → Sb : S → ε generates , the paradigmatic non-regular linear language.
This text is licensed under the Creative Commons CC-BY-SA License. This text was originally published on Wikipedia and was developed by the Wikipedia community.
