Some useful properties of CFGs and RGs

1. Metalinear grammars.CFGs with rules of the form or , for are called metalinear grammars; they are a special case in having only one centre of recursion.
2. Non-deterministic CF languages such as are distinguised from deterministic CF languages such as ; it is not possible to define a nondeterministic CF language with a deterministic CF grammar, the reverse relation is valid.
3. There are no non-deterministic regular languages; for any non-deterministic regular language, there is an equivalent deterministic regular language.
4. For any left-linear grammar there is a right-linear grammar which generates the same language.