A language which cannot be described by a regular expression is called non-regular.
Context Free Grammar
Regular expressions are not very powerful at describing languages mostly due to their lack of recursion definition.
Context-free grammar(CFG) has been created to resolve this problem and defines any kind of recursive language.
Programs are particularly simple and efficient:
- for the recognition of regular sentences
- ie for the determination of the structure of the sentence,
- ie for the determination of whether the sentence is well-formed
Via Memory definition
If the algorithm takes:
- a fixed, finite amount of memory, independent of the size of the input string, then the language is regular.
- a memory amount that depends on the input string size, then the language is non-regular