Expressive Power
There is a direct one-to-one correspondence between the rules of a (strictly) left regular grammar and those of a nondeterministic finite automaton, such that the grammar generates exactly the language the automaton accepts. Hence, the left regular grammars generate exactly all regular languages. The right regular grammars describe the reverses of all such languages, that is, exactly the regular languages as well.
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.
Read more about this topic: Regular Grammar
Famous quotes containing the words expressive and/or power:
“Coming on such an ancient human trace
Seems as expressive of the human race
As meeting someone living, face to face.”
—Robert Frost (1874–1963)
“He admired the terrible recreative power of his memory. It was only with the weakening of this generator whose fecundity diminishes with age that he could hope for his torture to be appeased. But it appeared that the power to make him suffer of one of Odette’s statements seemed exhausted, then one of these statements on which Swann’s spirit had until then not dwelled, an almost new word relayed the others and struck him with new vigor.”
—Marcel Proust (1871–1922)