We recall that a grammar G1 = (T, N, S, R) is right regular if the rules of R are of the form: A → aB or A → a with A, B ∈ N and a ∈ T.
We recall that a grammar G2 = (T, N, S, R) is left regular if the rules of R are of the form: A → Ba or A → a with A, B ∈ N and a ∈ T.
The interest of distinguishing regular left or right grammars appears during the analysis: if we read the symbols of the word to be analyzed from left to right, then
- a right regular grammar will be used for a top-down analysis, from the axiom to the word
- a left regular grammar will be used for an bottom-up analysis, from the word to the axiom.
For example, to analyze the word aaabb with the grammar G1, we will construct the derivation S1 ⇒ aS1 ⇒ aaS1 ⇒ aaaU1 ⇒ aaabU1 ⇒ aaabb; while to analyze this word with grammar G2, we will construct the derivation aaabb ⇐ U2aabb ⇐ U2abb ⇐ U2bb ⇐ S2b ⇐ S2.
Language and expression
Operators *,. and | have a decreasing priority. If necessary, we can add parentheses.
The equivalence between regular expressions and regular languages is established by the following two implications:
- Any regular expression describes a regular language.
- Any regular language can be described by a regular expression.
Trivial equivalence list:
Automate creation process from a regular expression