Discrete Structures and Automata Theory

1. The union of two languages ~ and L.;., denoted ~ U L.;., is the set of string that are 1. The co,
in either ~ or L.;., or both. languag
For example, if ~={OOI,lO,lII} and L.;.={E,OOI} then ~uL.;.={E,lO,OOI,III). That is
2. The concatenation of languages ~ and L.;. is a set of strings that can be formed by 2. If a is ~
taking any string in L" and concatenation it with any strings in L.;.. We denote {a}. Tt
concatenation of languages either with a dot. 3. A vari,
For example, if ~ ={OOI,lO,II}andL.;. ={E,OOI} then languag

~ . L.;. = {OOl, 10, 111,00100 1, 10001, 11100 I} 14.1.4 Indl

3.The closure (or star, or kleene closure) of a language L is denoted by L* and represents There are fot
the set of those strings that can be formed by taking any number of strings from L, introduction c
possibily with repetitions (that is same string can be repeated more then once) and
1. If Ij ar
concaterating all of then. union (
For example L = {O, I} then L * is all string of O's and 1's including null string.
2. If 'i ai
More formally, L * is the infinite union u j ?:. Or" where LO= {E}, (; = Land l'" for
i > 1 is LL .. · L. concate
4. The positive closure of a language L is denoted by L + and represent the set of those 3. If r is
strings that can be formed by taking any number of strings from L, possibily with L(r) t
repetitions and concatenating all of them, excluding null string i.e. 4. If r is .
denotin
L+ = L*-E
Now)1­
More for mally, C is the infinite union uj?:.l t, where L' = L and I!, for i > I il
LL .. · L. Exa~l' l
and at least

14.1.2 Definition of Regular Expression

The set of regular expression is defined by the following rules:

I. Every letter of r can be made into a regular expression, null string, E itself is 3
regular expression.
2. If Ij and r2 are regular expression, then
(i) (r,)
(ii) Ij r2
r, + r2
(iii)
r,'
(iv)
(v) rt
are also regular expression.
3. Nothing else is regular expression. Solution:
Illvvv'vV'JU
14.1 .3 Building Regular Expression
and it hou
The algebra of regular expressions follows this path using constants and variables that den(l(e onward f
languages, and operators for three operations of union, dot and star. We can describe IItt So
regular expression recursively, as follows.
In this definition, we not only describe what the legal regular expression are, but (or
each regular expression E, we describe the language it represents, which we denote L (fl.
We can consider some facts:
 Regular Expression and Languages

1. The constants E (null string) and ¢ (empty set) are regular expression, denoting the
languages {E} ¢, respecti vely.
That is, L(E ) = {E}, and L(¢) =¢
2. If a is any symbol, then a is regular expression . This expression denotes the language
(a}. That is L(a) = (a} .
3. A variable , usually capitalized and italic such as L is a variable , representing any
language.

14.1.4 Inductive Step

There are four parts to the inductive step, one for each of three operators and one for the
introduction of parantheses .
I. If 'I and '2 are regular expressions, then Ij +'2 is a regular expression denoting the
union of L('I) and L('2) that is L('I +(2)=L(Ij)uL('2) '
2. If Ij and '2 are regular expression then 't'2 is a regular expression denoting the
concatenating of L('I) and L('2) that is L('I (2)=L('I)·L('2)'
3. If, is a regular expression then ,*
is a regular expression denoting the closure of
L(r ) that is, L(r*)=(L(r»)*. .
If , is a regular expression, then (E), a parenthesized " is also a regular expression ,
denoting are same language as r formally, L ((r» = L(r).
Now us discuss some example of Building Regular expression for better understanding.
Write the regular expression over alphabet (a, b, c) containing at least one a
at least one b.
: Let us first analyse the language of regular expression.
Problem is very simple and the language will have set of string , like ab, a bbbb, abab,
baaaa .... .. .. So, string are 1 a Z b ;2, any combination of a's, b's and is possible at
places 1, 2 and 3 and any combination of a, b, c means (a + b + c)*.
So regular expression is
r = (a + b + c)* a (a + b + c)*b (a + b + c )* + (a + b + c)*b (a + b + c )* a (a + b + c)*

If ,=rt +r2 (say)

then minimum string of Ij is ab and minimum string of r2 is ba.
/write the regular expression for the set of strings of O's and 1 s whose tenth
from the right end is 1­
I = {O, I} given the set of string according to the required regular expression are
1001 1 010101010 ........... So clearly we concern about only tenth position
I.!.VVVVVVVCIV,

it should be I, rest 9 places from the right are either 0 or 1. Similarly positions 11th
from right and may be either 0 to 1.
So regular expression is
, == (0 + 1)*1 (0 + 1) (0 + I) (0 + 1) (0 + 1) (0 + 1) (0 + 1) (0 + 1) (0 + 1) (0 + 1)
 Discrete Structures and Automata Theory

-
Sc
Example 3. Write the regular expression for the set of strings of an equal number o/O s
s
and 1:S such that in every prefix, the number of O's differs from the number of 1 by al /IIosl Exampl,
1.
SOlution:
Solution: Clearly the set of strings is having strings like 01010101, 10101010,0110,1001....
So regular expression will be r == (OJ + 10)' Cas
Cas
Example 4. Write a regular expression for the set of strings of O:S and 1:S not conta;/lill~
101 as a substring. Let
Solution : When we analyse the set of strings the it becomes clear that string may start witb
'0' and O's may be repeated, whenever one is encoute.Ied then no single 0 must folio", it
so strings ~Iike 0000010, 00000111111, 1001001.. ....... . Let J

Regular expression is r == (0*1*00)* O' 1*

Example ~ Write the regular expression over alphabet (a, b), for the set of slrillgs "'I~ Let n
even nuJ;i~r of a's followed by odd number of b:S that for the language

L = {a 211 b 2111 +1 .n_ 0

• > ,m_
> O}
Example 9.
Solution: Clearly every string of language L will start with even number of (/'S i.e. at/tall
two a's should be there in the begining of the string. String should end with at least thrtt Solution: /c
b's (i.e. odd number of b's). fOllowed by
Regular expression is r == (aa)" (bb)* b.

Example 6. Write the regular expression for the language L = (WE (0,1)* : HI has no POll
of consecutive zeros}.
Solution: Clearly whenever a 0 occurs it must be followed by a 1. Such a substring JIll}
be preceded and followed by any number of 1's, that is (1*011*)*. But strings ending ioU
or consisting of all 1 's are un accounted here, that is 1* (O+E).
So regular expression is ~ So/utio,,:

rl =(1* 011*)' (O+E)+I*(O+E)

Another possible solution is

r2 = (1 + 01)* (0+ E)
Although the two expression look different, both anwers are correct, as they deoOfttl
same language. Generally, there are an unlimited number of regular expression for any~.
language. SOlutiol/ :
So
E~le 7. Write the regular expression for the language L={a/l blllll~ 4, m~3}.
Solution:Language contain the set of strings such that every string start with at fest 4
and end with at the most 3 b's.
 Regular Expression and Languages

So regular expression will be r=a 4 a* (E +b+b 2 +b 3 )

Exampl~ the regular expression for the language L = {a " b m : (n + m) is even}

Sollll;ol/: We know (n + m) can be even in two cases

Case J : nand m both are even
Case 2 : nand m both are odd
Let regular expression for case 1 is 'i then

Let regular expression for case 2 is r2 then

r2 = (aa)* a (bb)' b
Let regular expression for language L is r then r = 'i + r2

r = (aa)* (bb)* + (aat a (bb)* b

lumpl. ~e the "g .Ia, expms'on /0' the lang .age L ={ab" w, n >3, WE Ca, b)'},
Sollll;on : Clearl y every string of language L starts with a followed by at least three b's
rollowed by at least one a or one b that is strings are like a b 3 a, abbbbba,··· ···
So regular expression is :

r=ab 3 b*(a+bt
Here + is positive closure i.e. (a+bt =(a+b)*-E

Exampl~ Write the regular expression/or the language L = {w:1 wi mod 3 = o}, WE (a, b)'

Solulion: Let us first understand are meaning of 1 W I mod 3 = O. When length of string
belongs to the language L, is di vided by 3 then reminder should be 0 that is length of w must
be 0, 3, 6, 9... ... Clearl y multiple of three.

Regular expression is : r=((a+b)3)*.

/
fxamp~ Write the regular expression/or the language L = {WE (a, b)*: na(w) mod 3 = O}

SOlulioll: /I" (w) mod 3 = 0 means , number of a's in string should be 0, 3, 6, 9 ......

So regular expression is :