What is a Regular Language ?

About

A regular language is a language that can be described by regular expressions.

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.

A language is also regular, if its syntax can be expressed by a single context free expression. (ie they can be described by finite automata)

The requirement that a single equation suffices also implies that only terminal symbols occur in the expression. Such an expression is called a regular expression.

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

^{1) 2)}