Non-Regular Languages

Regular Expressions

                                                      Source:http://surl.li/bcakh

Regular Expressions are usually used to indicate the regular languages. 

• The language that gets acquired by the finite automata(FA) can also be described by the simple expressions which are called as Regular Expressions. It is the most effective and reliable way to represent any language.
• The languages that is accepted by some regular expression is referred as Regular languages.
• A regular expression can also be described as a chain of patterns that defines a string.
• Regular expressions are usually used to match the character combinations in the strings. String searching algorithm are used in this pattern to find the operations on a string. 

Examples of regular expression:

1. Construct a regular expression for the language which accepts all the strings which starts with 1 and ends with 0 over ∑ = {0, 1}.

Solution:

In this regular expression, the starting symbol should be 1 and the ending symbol should be 0 and in between 1 and 0 we can have any type of strings. So, The regular expression for this language is as follows:

R = 1 (0+1)* 0  

2. Construct a regular expression which starts with 'a' but will not have back to back b's.

Solution: 

The regular expression for this language is:

L = {a, aba, aab, aba,abab, abababaa,...} 

So, the regular expression for the language will be:

R = {a + ab}*   

Regular Language

A regular language is the language that can be demonstrated with the regular expression or can also be expressed by a deterministic or the non-deterministic finite automata or even the state machine. A language is actually defined as the set of stings which are basically made up of the characters from a specified alphabet or the set of symbols. Regular languages are actually the subset of the set of all the strings. Basically each and every set which is finite represents a regular language.

Examples of regular language:

All the languages which are finite are also regular; in particular the empty string language {ε} = Ø* is regular. Other such examples include the language made of all strings over the alphabet {a, b} which contain an even number of a's etc. Some other examples are:

• a*b* is regular language
• {w belongs to {a, b}* : every a is immediately followed by b} is regular language

Non-Regular language

A language which is not defined by the regular expression is called nonregular language or an irregular language. The existence of the languages which are not regular is basically guaranteed by the fact that the regular languages of any alphabet can be counted, and we know that the set of all the subsets of the strings are not countable. 

Examples of non regular language:

An example of non regular language is { a^nb^n | n ≥ 0 }. This language cannot be recognized with the help of finite automata, since the finite automata has finite memory and it basically cannot remember the exact number of a's. Some other examples are:

• {w ∈{a, b}* : every a has a matching b somewhere} is not a regular language
• {a^n: n >=1 is a prime number} is not regular language.

Pumping lemma for Regular languages

Source:http://surl.li/bcalj

To identify whether a language is regular or non regular ,Pigeon Hole Principle can be used. This is also generally named as Pumping Lemma.

• It gives a method for pumping  or generating a lot of substrings from a given string.
• We can also say that it provides a means to break a given long input string into several substrings.
• It specifies the requirements for proving that a set of strings is not regular.

But the pumping lemma is a contradiction test which means that if any language does not satisfy the pumping lemma, then we can say that the language it is not regular. But, if it satisfies the conditions of the pumping lemma, then we can say that the language may or may not be regular.

Pumping Lemma is actually a mathematical proof, which takes a lot of time and also sometimes creates a lot of confusion.

Every language that is finite is also regular, that means if there is a limit to language then we can basically say it is regular.

Consider the following language as an example:

       L = { a10b20} is a regular language whereas,

       L = { anbn| n > 0} is not a regular language.

Suppose, if there is an infinite language, then we will have to  check whether its deterministic finite automata i.e. DFA can be created or not. If we can’t create the DFA, then the language will not be a regular language.

The length of a string follows an arithmetic progression, and the language must have a pattern in order to generate finite automata (FA).

Let’s consider some examples to identify whether the language is regular or not.

Example 1

Consider all the strings which are of length 2 over an alphabet {a, b}*

The language is:

       L = {aa, ab, ba, bb}.

In this problem, we have been given an expression of all the strings of length 2 over the alphabets {a, b}* which is a non-regular language, but the value is bounded by a constant like length which is equal to 2. So, we can say that the language is a regular language. 

Example 2

Prove that the language L = { ai bi | i ≥ 0} is not regular.

Sol-

The strings which can be produced by this language are:

L = {ab, aabb, aaabbb, aaaabbbb, .....}

Let us take any string from this language. 

E.g. 

1. Let us take the string aaabbb.
2. Now, we have to divide this string into three parts x, y and z, |y| >0, |xy|< P. Let us say x = aa,
   y = ab and z = bb. 
3. Now, according to pumping lemma, we have to pump the string y. So, let us pump it to y^2 i.e.
   y = abab.
4. The new string formed is xyz = aaababbb.
5. This string does not belong to the language L. 
6. Therefore, By Pumping Lemma, the language L = { ai bi | i ≥ 0} is not a regular language.

How can you tell whether a language is regular or not?

There is a very well established theorem to identify whether a language is regular or not, which is based on Pigeon Hole Principle, called as Pumping Lemma. But the problem with the pumping lemma is that it is a negativity test, i.e. if a language doesn’t satisfy the pumping lemma, then we can definitely say that it is not a regular language, but if it satisfies the pumping lemma, then the language may or may not be a regular language. 

Here are some quick rules that will help in finding whether a language is regular or non regular.

1. Every finite set represents a regular language. 

Example 1: 

All strings of length = 2 over alphabets {a, b}* i.e. L = {aa, ab, ba, bb} is regular. 

2. The pattern of strings form an A.P. is regular, 

but the pattern with G.P. is not regular and it comes under class of Context Sensitive Language. 

Example 2a: 

L = { | n>=2 } is regular. It forms an A.P., so we can draw a finite automata for it with 3 states.

 

Example 2b: 

L = { a2^n | n>=1 } is not regular. It forms a Geometric Progression, so we cannot have a fixed pattern which repeated would generate all strings of this language. If ‘n’ is like n<10000 then it becomes a regular language as it is finite.  

3. No pattern is present, that could be repeated to generate all the strings in language is not regular. Finding prime itself is not possible with FA. 

Example 3: 

L = { | p is prime. } is not regular. 

 

4. A concatenation of regular and non regular language is also not a regular language.

 

Example 4:

L1 = { | n≥1 }, L2 = {n≥1 } then L1.L2 is not regular. 

Conclusion

Regular languages are those languages all of whose members can be expressed with just a regular expression (RE). Non regular languages are those whose members can not be expressed with RE’s Or a regular language is a language that can be modeled by finite automata while non regular languages can not.

References:

1. https://www.javatpoint.com/automata-regular-expression

2. https://brilliant.org/wiki/regular-languages/

3. https://www.geeksforgeeks.org/how-to-identify-if-a-language-is-regular-or-not/

4. https://www.cs.wcupa.edu/rkline/fcs/re-pump.html

5. https://www.geeksforgeeks.org/pumping-lemma-in-theory-of-computation/