ZeePedia

Nonregular languages

<< Regular languages, Complement of a language
Pumping Lemma >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 25
Reading Material
Introduction to Computer Theory
Chapter 9,10
Summary
Intersection of two regular languages, examples, non regular language, example
Theorem
Statement
If L1 and L2 are two regular languages, then L1 Č L2 is also regular.
Proof
Using De-Morgan's law for sets
(L1c « L2c)c = (L1c)c Č (L2c)c = L1 Č L2
Since L1 and L2 are regular languages, so are L1c and L2c. L1c and L2c being regular provide that L1c « L2c is also
regular language and so (L1c « L2c)c = L1 Č L2, being complement of regular language is regular language.
Following is a remark
Remark
If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs. Finding regular
expressions defining the language L1 Č L2 is not so easy and building corresponding FA is rather harder.
Following are example of finding an FA accepting the intersection of two regular languages
Example
Consider two regular languages L1 and L2, defined over the alphabet Σ = {a, b}, where
L1 = language of words with double a's.
L2 = language of words containing even number of a's.
FAs accepting languages L1 and L2 may be as follows
a,b
b
a
a
q
p-
r+
FA1
b
b
b
a
FA2
1±
2
a
Their corresponding REs may be
r1 = (a+b)*aa(a+b)*
r2 = (b+ab*a)*
Now FAs accepting L1c and L2c , by definition, may be
a,b
b
a
a
q+
p±
r
FA1c
b
b
a
b
FA2c
1-
2+
a
Now FA accepting L1c « L2c , using the method described earlier, may be as follows
73
img
Theory of Automata
(CS402)
New States after reading
Old States
a
b
z1±∫(p,1)
(q,2)∫z4
(p,1)∫z1
z2+∫(p,2)
(q,1)∫z3
(p,2)∫ z2
z3+∫(q,1)
(r,2)∫z6
(p,1)∫ z1
z4+∫(q,2)
(r,1)∫ z5
(p,2)∫ z2
z5∫(r,1)
(r,2)∫ z6
(r,1)∫ z5
z6+∫(r,2)
(r,1)∫ z5
(r,2)∫ z6
Here all the possible combinations of states of FA1c and FA2care considered
z1±
b
a
b
b
z2+
z3+
z4+
a
b
a
a
b
b
a
z5
z6+
a
An FA that accepts the language (L1c « L2c)c=L1Č L2may be
b
z1-
b
b
a
z2
z3
z4
a
b
a
a
b
b
a
z6
z5+
a
Corresponding RE can be determined as follows
The regular expression defining the language L1 Č L2 can be obtained, converting and reducing the previous FA
into a GTG as after eliminating states z2 and z6
b  z1-
a
b
bb*a
z4
z3
b+abb*ab
z1-
a
a
ab*a
ab*a+b
z4
z5+
after eliminating state z3
a+bb*aab*a
b+ab*a
z5+
74
img
Theory of Automata
(CS402)
z4 can obviously be
b+abb*ab
b+ab*a
eliminated as follows
a(a+bb*aab*a)
z5+
z1-
eliminating the loops at z1 and z5
(b+abb*ab)*a(a+bb*aab*a)(b+ab*a)*
z1-
z5+
Thus the required RE may be (b+abb*ab)*a(a+bb*aab*a)(b+ab*a)*
FA corresponding to intersection of two regular languages
(short method)
Let FA3 be an FA accepting L1 Č L2, then the initial state of FA3 must correspond to the initial state of FA1 and
the initial state of FA2.
Since the language corresponding to L1 Č L2 is the intersection of corresponding languages L1 and L2, consists
of the strings belonging to both L1and L2, therefore a final state of FA3 must correspond to a final state of FA1
and FA2. Following is an example regarding short method of finding an FA corresponding to the intersection of
two regular languages.
Example
Let r1 = (a+b)*aa(a+b)* and FA1 be
a,b
b
a
a
q
p-
r+
b
also r2 = (b+ab*a)* and FA2 be
b
b
a
1±
2
a
An FA corresponding to L1 Č L2 can be determined as follows
New States after reading
Old States
a
b
z1-∫(p,1)
(q,2)∫z4
(p,1)∫z1
z2∫(p,2)
(q,1)∫z3
(p,2)∫ z2
z3∫(q,1)
(r,2)∫z6
(p,1)∫ z1
z4∫(q,2)
(r,1)∫ z5
(p,2)∫ z2
z5+∫(r,1)
(r,2)∫ z6
(r,1)∫ z5
z6∫(r,2)
(r,1)∫ z5
(r,2)∫ z6
The corresponding transition diagram may be as follows
b
z1-
a
b
b
z2
z3
z4
a
b
a
a
a
b
b
z6
z5+
a
75
img
Theory of Automata
(CS402)
Nonregular languages
The language that cannot be expressed by any regular expression is called a Nonregular language.
The languages PALINDROME and PRIME are the examples of nonregular languages.
Note:  It is to be noted that a nonregular language, by Kleene's theorem, can't be accepted by any FA or TG.
Example
Consider the language L = {Λ, ab, aabb, aaabbb, ...} i.e. {an bn : n=0,1,2,3,...}
Suppose, it is required to prove that this language is nonregular. Let, contrary, L be a regular language then by
Kleene's theorem it must be accepted by an FA, say, F. Since every FA has finite number of states then the
language L (being infinite) accepted by F must have words of length more than the number of states. Which
shows that, F must contain a circuit.
For the sake of convenience suppose that F has 10 states. Consider the word a9 b9 from the language L and let
the path traced by this word be shown as under
b
a
9
5
3
1-
7
b
a
a
b
a
a
b
b
a
8
6
4
10
2
But, looping the circuit generated by the states 3,4,6,5,3 with a-edges once more, F also accepts the word a9+4 b9,
while a13b9 is not a word in L. It may also be observed that, because of the circuit discussed above, F also
accepts the words a9(a4 )m b9, m = 1,2,3, ...
Moreover, there is another circuit generated by the states 9,10,9. Including the possibility of looping this circuit,
F accepts the words  a9(a4 )m b9(b2 )n where m,n=0,1,2,3,...(m and n not being 0 simultaneously).Which shows
that F accepts words that are not belonging to L.
76
Table of Contents:
  1. What does automata mean, Introduction to languages
  2. Kleene Star Closure, Recursive definition of languages
  3. Regular Expression, Recursive definition of Regular Expression
  4. Equivalent Regular Expressions
  5. Finite Automaton
  6. Equivalent FAs
  7. FA corresponding to finite languages
  8. Examples of TGs: accepting all strings
  9. Generalized Transition Graphs
  10. Nondeterminism, Kleene’s Theorem
  11. Proof(Kleene’s Theorem Part II)
  12. Kleene’s Theorem Part III
  13. Concatenation of FAs
  14. Closure of an FA
  15. Nondeterministic Finite Automaton, Converting an FA to an equivalent NFA
  16. NFA with Null String
  17. NFA and Kleene’s Theorem
  18. NFA corresponding to Concatenation of FAs
  19. Distinguishable strings and Indistinguishable strings
  20. Finite Automaton with output, Moore machine
  21. Mealy machine
  22. Equivalent machines
  23. Mealy machines in terms of sequential circuit
  24. Regular languages, Complement of a language
  25. Nonregular languages
  26. Pumping Lemma
  27. Pumping Lemma version II
  28. Pseudo theorem
  29. Decidability
  30. finiteness of a language
  31. Context Free Grammar (CFG), CFG terminologies
  32. Trees
  33. Polish Notation (o-o-o)
  34. Total language tree, Regular Grammar
  35. Null Production
  36. Chomsky Normal Form (CNF)
  37. A new format for FAs
  38. Nondeterministic PDA
  39. PDA corresponding to CFG
  40. Conversion form of PDA
  41. Conversion Form, Joints of the machine
  42. Row language, Nonterminals
  43. Non-Context-Free language, Pumping lemma for CFLs
  44. Decidablity, Parsing Techniques
  45. Turing machine