ZeePedia

Regular languages, Complement of a language

<< Mealy machines in terms of sequential circuit
Nonregular languages >>
img
Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 24
Reading Material
Introduction to Computer Theory
Chapter 9
Summary
Regular languages, complement of a language, theorem, proof, example, intersection of two regular languages
Regular languages
As already been discussed earlier that any language that can be expressed by a RE is said to be regular language,
so if L1 and L2 are regular languages then L1 + L2 , L1L2 and L1* are also regular languages. This fact can be
proved by the following two methods
By Regular Expressions
As discussed earlier that if r1, r2 are regular expressions, corresponding to the languages L1 and L2 then the
languages L1 + L2 , L1L2 and L1* generated by r1+ r2, r1r2 and r1*, are also regular languages.
By TGs
If L1 and L2 are regular languages then L1 and L2 can also be expressed by some REs as well and hence using
Kleene's theorem, L1 and L2 can also be expressed by some TGs. Following are the methods showing that there
exist TGs corresponding to L1 + L2, L1L2 and L1*
If L1 and L2 are expressed by TG1 and TG2 then following may be a TG accepting L1 + L2
L
L
p-
1-
-
TG1
TG2
n+
m+
If L1 and L2 are expressed by the following TG1 and TG2
n+
m+
p-
1-
TG2
TG1
then following may be a TG accepting L1L2
L
n
m+
p
1-
TG2
TG1
also a TG accepting L1* may be as under
L
n+
1-
TG1
L
Example
aa,bb
aa,bb
Consider the following TGs
ab,ba
2
TG1
1±
ab,ba
a,b
a,b
aaa,bbb
p-
q+
TG2
70
img
Theory of Automata
(CS402)
Following may be a TG accepting L1+L2
-
L
L
a,b
a,b
aa,bb
aa,bb
ab,ba
aaa,bbb
p-
2
q+
TG1
1±
TG2
ab,ba
also a TG accepting L1L2 may be
L
a,b
a,b
aa,bb
aa,bb
ab,ba
aaa,bbb
p
q+
2
1-
TG1
TG2
ab,ba
and a TG accepting L2*
L
a,b
a,b
aaa,bbb
p-
q+
TG2
L
Complement of a language
Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to
L, is called Complement of the language L, denoted by Lc or L'.
Note
To describe the complement of a language, it is very important to describe the alphabet of that language over
which the language is defined.
For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = L
Theorem
If L is a regular language then, Lc is also a regular language.
Proof
Since L is a regular language, so by Kleene's theorem, there exists an FA, say F, accepting the language L.
Converting each of the final states of F to non-final states and old non-final states of F to final states, FA thus
obtained will reject every string belonging to L and will accept every string, defined over Σ, not belonging to L.
Which shows that the new FA accepts the language Lc. Hence using Kleene's theorem Lc can be expressed by
some RE. Thus Lc is regular.
Example
Let L be the language over the alphabet Σ = {a, b}, consisting of only two words aba and abb, then the FA
accepting L may be
a
a,b
b
n-
o
p
q+
a
b
a,b
a,b
r
71
img
Theory of Automata
(CS402)
Converting final states to non-final states and old non-final states to final states, then FA accepting Lc may be
a
a,b
b
n±
p+
o+
q
a
b
a,b
a,b
r+
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.
72
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