Examples of Regular Language and Regular Expressions in automata theory (Concepts, Tricks) | 065
Playlist for all videos on this topic: • Theory of Computation or Automata The...
Examples of Regular Language, Examples of Regular Expressions
Regular language, The set of regular languages over an alphabet is defined recursively as below. Any language belonging to this set is a regular language over . Definition of Set of Regular Languages :Basis Clause: , {} and {a} for any symbol a are regular languages.
Inductive Clause: If Lr and Ls are regular languages, then Lr Ls , LrLs and Lr* are regular languages.
Extremal Clause: Nothing is a regular language unless it is obtained from the above two clauses.
For example, let = {a, b}. Then since {a} and {b} are regular languages, {a, b} ( = {a} {b} ) and {ab} ( = {a}{b} ) are regular languages. Also since {a} is regular, {a}* is a regular language which is the set of strings consisting of a's such as , a, aa, aaa, aaaa etc. Note also that *, which is the set of strings consisting of a's and b's, is a regular language because {a, b} is regular.
( a + b )2 corresponds to the language {aa, ab, ba, bb}, that is the set of strings of length 2 over the alphabet {a, b}.
In general ( a + b )k corresponds to the set of strings of length k over the alphabet {a, b}. ( a + b )* corresponds to the set of all strings over the alphabet {a, b}.
a*b* corresponds to the set of strings consisting of zero or more a's followed by zero or more b's.
a*b+a* corresponds to the set of strings consisting of zero or more a's followed by one or more b's followed by zero or more a's.
( ab )+ corresponds to the language {ab, abab, ababab, ... }, that is, the set of strings of repeated ab's.
Definition of Equality of Regular Expressions
Regular expressions are equal if and only if they correspond to the same language.
Thus for example ( a + b )* = ( a*b* )* , because they both represent the language of all strings over the alphabet {a, b}.