By
using FA's and regular expressions, we have been able to define many languages.
Although these languages have had many different structures, they took only a
few basic forms: languages with required substrings, languages that do not
accept some substrings, languages that begin or end with certain strings,
languages with certain even/odd properties, and so on. On the contrary we can’t
draw an FA for languages such as PALINDROME or the language PRIME of all words
aP where p is a prime number, as neither of these are regular
languages. More powerful machines are needed to define them.
Pumping
Lemma is used to prove that certain languages are not regular.
Pumping Lemma
Suppose L is a regular language.
If L is accepted by a finite automaton M and if n is the number of states of M,
then for every x ∈ L satisfying |x| ≥ n, there are three strings u, v,
and w such that x = uvw and the following three conditions are true:
1. |uv |≤ n.
2. |v| > 0 (i.e., v is not
equal to NULL).
3. For every i ≥ 0, the
string uviw also belongs to L.
Here the same substring has
to be pumped repeatedly and the language is regular only if after the same
substring v is pumped i times and after that also it still belongs to the
language. We have to check with all possible values of v and if atleast for one
of the value of v, uviw does not belong to L, then the language is not
regular.
For example
Check if 0m1m is regular
|x|= 0m1m
> 0
x = uviw
Case 1: v only has 0’s, number of zeroes will exceed number
of 1’s and not be equal to m. Therefore uviw does not belong to L.
Case 2: v is only 1’s, number of 1’s will exceed number of 0’s
and not be equal to m. Therefore uviw does not belong to L.
Case 3: v is a combination of 0’s and 1’s,
eg:
u = 000
v = 0011
w = 111
Then uv2w = 0000011001111, all the 0’s are not followed by the
1’s.
Therefore uviw does not belong to L.
Therefore by contradiction 0m1m
is not regular.
Another example
Check if the language of
squares, ai*i is a regular language.
Let it be a regular language
with ‘n’ states.
|x| > n and x = an*n
Let i = 2
n2 = uvw
uv2w = |uvw| + |v|
≤ n2 + n < n2 + 2n + 1 < (n+1)2
This is a contradiction,
because condition 3 says that |uv2w| must be i2 for some
integer i, but there is no integer i whose square is strictly between n2 and
(n+1)2.
Another example
Check if the language of palindromes is regular.
Let language of palindromes
be regular with an FA with ‘n’ states.
Let x = an bn
bn an = uviw
if uv = an
w = bn bn an
then the number of a’s will increase and not
belong to L.
Therefore by contradiction,
the language of palindromes is not regular.
Feel free to comment if you have any doubts.
Comments
Post a Comment