www.alljntuworld.

in JNTU World

N
Formal J Languages
TU
& Automata

W o
Theory Complete
rld
Notes

Downloaded From JNTU World (http://www.alljntuworld.in)

www.alljntuworld.in JNTU World

Contents 1 Mathematical 2 Formal 2.1 2.2 2.3 2.4 3 Grammars 3.1 3.2 3.3 3.4 4
 JN
Finite 4.1 4.2 4.3 4.4 4.5 4.6 Preliminaries Languages

Strings . . . . . . . . . . . . . . . . . . . Languages . . . . . . . Properties . . . . . . . Finite

Representation . 2.4.1 Regular Expressions Context-Free Derivation 3.2.1 Regular Digraph
Deterministic Nondeterministic Equivalence 4.3.1 Minimization 4.4.1 Automata

T
Ambiguity Heuristics Myhill-Nerode Grammars Representation Trees of
 U
Grammars of Finite NFA DFA . Finite to . . . . . . . . Automata

W
and Convert . Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .....

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Automata . . . DFA .
 o
. . . . . NFA to DFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..............

r
. ............................................................... .

.........................................................................
 ld
........................

3
4 5 6 10 13 13
18 19 26 31 32 36
38 39 49 54 58 61 61 4.4.2 Algorithmic Procedure for Minimization . . . . . . . . 65 Regular
Languages . . . . . . . . . . . . . . . . . . . . . . . . 72 4.5.1 Equivalence of Finite Automata and
Regular Languages 72 4.5.2 Equivalence of Finite Automata and Regular Grammars 84
Variants of Finite Automata . . . . . . . . . . . . . . . . . . . 89 4.6.1 Two-way Finite Automaton . . .
. . . . . . . . . . . . 89 4.6.2 Mealy Machines . . . . . . . . . . . . . . . . . . . . . . 91
1 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
 JN
5 Properties of Regular Languages 94 5.1 5.2 Closure

Properties . . . 5.1.1 Set Theoretic Properties 5.1.2 Other Properties Pumping Lemma . . . .

TU
........................
W o
........................ ..................

r ld
.......... . . . . 104 94 94 97

2 Downloaded From JNTU World (http://www.alljntuworld.in)

www.alljntuworld.in JNTU World

J
Chapter Mathematical

NT
1
U
Preliminaries

World
3 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
J
Chapter Formal A facts all ming One is siders sequence

learning In construction being common quence sentence may with one a language

N
1. 2. 3. this the "The sequence more may be enough and languages.

Learning Its Formation rules instead a varieties learning, of language treated of words
features English of broadly some concepts. special categorized of a can symbols
 T
punctuation language of of the of its symbols of - sentences be words; as

step of Let as completely symbol, languages language.

that of see Languages alphabet articles sentences seen a For various a of us

U
2 3 sequence that word has has is and its of look formalizing as

into the marks namely the and underlying a a the a sequences a - such and language script,
 at ignoring system - the most word - underlying following sequence concentrate of two
some a, such as a symbols symbols blank-space sentence difficult is natural then an the
types: suitable common a as alphabet. about is of and combination notion

W
a of three comma, symbols it alphabet. that collection various

from (human) can on part. to the sentences for indefinite which steps. features steps of are
agree be It the expression full-stop, - Let a of observed is used words language For are its
languages of of is 1 Roman observed upon us and across one sentences; used syllables.

o
alphabet. example, in postpone that colon the and both may 2. that of to
one alphabet the follow and that certain language. For separate definite." look and are the a

r
must If languages. a to program- word the one sentence a English just discuss

further certain formal at ideas,

along cover
time con-

ld
two is the
se- a
words. Thus, abstractly, a sentence or a word may be interchangeably used
4 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
for a sequence of symbols from an alphabet. With this discussion we start

J
with notion and We via 2.1 We the elements one write a letters strings.

Example are ( we if Although infinite tal manipulate concatenation. concatenation string Σ )

N
require Further, A Since The One facts in end regular some formally
symbols writes discuss = the string it earlier {0,1}, towards of the for set as of is Strings
basic the we of examples language the also a 2.1.1. the a aexpressions. algebraic any
chapter of and an over in 1asequence a, introduce special define empty notation; thenset all

T
2 definitions of this most alphabet. b, the known ···aLet alphabet generate

an c, the strings ΣΣLet chapter, . ∗ end formally. of ∗ with an alphabet sequence x n, .

symbol. fundamental is properties pair . = strings as = Σ as i.e. with but alphabet infinite,
 U
some of {ε,0,1,00,01,10,11,000,001,...}. an = over a(aa of

strings. Σ. x, English 1aby with 1,aword {a, we aintroduction alphabets or 2 y 1aΣ We string

over is ···aan In juxtaposing 2,...,adenoted introduce b} without 2 is it of a the as ···aorder

alphabet use or a finite is n be operations languages alphabet, Σ. a finite and notation a a

operations, nbnon-empty an ε, n), countable sentence. and 1bto sequence, by to subscripts

W
alphabet; y 2 some to sequence in understand ···bdenote Σ xy =
 the strings finite the with namely is adapted bused is 1bm. of symbols denoted present 2
the Normally, which set. finite the respect representation ···bit the and of for or then is string

z,y,x,w, operations symbols In m 0,1,2,..., for also empty string some then set. in context, in

o
fact, by be aa, to the turn a that we Σtwo We those ab, we string. such

manipulation ∗ string. Σpresent of . etc., use ∗ bba, introduce For normally are order. on Σ.

r
strings. of is we etc. operations. fundamen- lower countably languages
languages
Although
to baaba, example, useful Which prefer context for denote Thus, case

The the

ld
use the

. to
to . is
is .
5 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Clearly, the binary operation concatenation on Σ∗ is associative, i.e., for all x,y,z ∈ Σ∗ ,
x(yz)=(xy)z. Thus, x(yz) may simply be written as xyz. Also, since ε is the empty string, it
satisfies the property
εx = xε = x for any sting x ∈ Σ∗ . Hence, Σ∗ is a monoid with respect to concatenation. The
operation concatenation is not commutative on Σ∗ .
For a string x and an integer n ≥ 0, we write
xn+1 = xnx with the base condition x0 = ε.
That is, xn is obtained by concatenating n copies of x. Also, whenever n = 0, the string x1

···xn represents the empty string ε.

Let x be a string over an alphabet Σ. For a ∈ Σ, the number of occur- rences of a in x shall be
denoted by |x|a. The length of a string x denoted by |x| is defined as
∑
|x| = a∈ Σ

Downloaded From JNTU World (http://www.alljntuworld.in)

|x|a.
Essentially, the length of a string is obtained by counting the number of symbols in the
string. For example, |aab| = 3, |a| = 1. Note that |ε| = 0.
If we denote An to be the set of all strings of length n over Σ, then one can easily

⋃
J
ascertain that Σ∗ = n≥0And hence, We say some Similarly, string x 2.2
 N
We elements broad alphabet. in Generalizing have y. strings x,

T
spectrum, Languages we of got x that being is adopt u a and suffix
 U
the x Athe is n v. notation a a of notation The substring finite y if

substring used v set, = |y|of ε.

W A
Σfor x ∗ as y is number x if the a is x countably n. number said

occurs of to occurrences in be of infinite y, occurrences a acquainted with the formal

notion of strings a language. In order to define the notion it is felt that it can be any
 orld
collection

set. that is y = uxv for prefix of y if u = ε.

of symbol a in a of a string
that are basic of a language in a of strings over an
Thus we define a language over an alphabet Σ as a subset of Σ∗ .
6
www.alljntuworld.in JNTU World
Example 2.2.1.

J Remark any whereas, such of Example Remark concatenation

N
1. 2. 3. 1. 2. 1. 2. 3. Since The string as The a The The If LFor LSince

languages. Hence, The product L1L1L1 language union, Lconcatenation 2.2.2. 2.2.4. ⊆ |{ε}|

languages 1 2 2 Lemptyset set set but number 2.2.3. = = = L1 concatenation 1L= (L{0,1,01}

T
{01,11,011,000,100,0100}. {b, of of of {ε} intersection, = Note 2 {b, 1Lall
 all individual ba, That if 1. over of 2)Lcontains ba, and of strings strings are strings 0 bb,

U
that 3 Lbab} any strings is of is, 1Lbab, may and sets, only aa

0 2 for of alphabet. language and = over over a can pair bbb, complement, numbers, L=

simply we if string, strings all 2 {xy (Lin {ε}, ε = babb, Lbe can of {0,1} {a, |L1Llanguages ∈

2 L{1,00}, | 1L= extended languages L2)L1Lbecause x be b, namely apply over 2.is baabb,

W
2|≤|L{ε, ∈ 2 c} i.e. 3 that associative, written is L= b, having
 difference any 1 then Lalways bb, various babbb, L∧ start the ε. 1(L1||Lto 1,LLabb},

alphabet. y Also 1, as 2Llanguages 2|. language ac 2 ∈ bababb}. with LL3). and less Lwell

2 so as on we 1Lit 2}. is is is 2La languages. L0. have than known substring. evident 3, the

o
Similarly, 3. 0 as does concatenation or follows. set that equal not The

r ld
operations {ε} |0| contain notion to is = also the
of 0;

7 Downloaded From JNTU World (http://www.alljntuworld.in)

www.alljntuworld.in JNTU World

Proof. The “if part” is straightforward; for instance, if ε ∈ L2, then for any x ∈ L1, we have x

= xε ∈ L1L2. On the other hand, suppose ε /∈ L2. Now, note that a string x ∈ L1 of

shortest length in L1 cannot be in L1L2. This is because, if x = yz for some y ∈ L1 and a

nonempty string z ∈ L2, then |y| < |x|. A contradiction to our assumption that x is of
shortest length in L1. Hence L1 ⊆ L1L2.

4. Similarly, ε ∈ L1 if and only if L2 ⊆ L1L2.

We write Ln to denote the language which is obtained by concatenating n copies of L. More
formally,
L0 = {ε} and Ln = Ln−1L, for n ≥ 1. In the context of formal languages, another important
operation is Kleene star. Kleene star or Kleene closure of a language L, denoted by L∗ , is
defined as
⋃ Ln
L∗ = n≥0Downloaded From JNTU World (http://www.alljntuworld.in) .
Example 2.2.5.
1. Kleene star of the language {01} is
{ε,01,0101,010101,...} = {(01)n | n ≥ 0}.
2. If L = {0,10}, then L∗ = {ε,0,10,00,010,100,1010,000,...}
⋃
L∗ = Since an arbitrary string in Ln is of the form x1x2 ···xn, for xi ∈ L and
 J N
n≥0 Thus, Remark the Thus, alphabet a the typical 2.2.6.

Ln
T
earlier L, ∗ one Σ = Note = string {xLcan introduced {0,1} ∗ 1xthat, = = =
 U
= 2 easily in ···x is

L{ε}∪ {0,1}∪ {00,01,10,11}∪ ··· {ε,0,1,00,01,10,11,···} the L0 ∗ the n ∪ observe is set | notation

L n a Kleene ∪ ≥ of concatenation L0 all 2 that ∪ ··· and strings star

W
∗
Σ xi ∈ L, of of the over is consistent for finitely language Σ.
orld
1 ≤ i ≤ n}
many strings of L. L = {0,1} over
with the notation of Kleene star by considering Σ as a language over Σ.
8
www.alljntuworld.in JNTU World
⋃
The positive closure of a language L is denoted by L+ is defined as L+ = n≥1Downloaded
 J
From JNTU World (http://www.alljntuworld.in) Thus, ing guages. properties is each

N
can Examples desired. 1. 2. 3. 4. We Consider the be such The written

This stating occurrences The Equivalently, The and The Lrepresented often property ∗ It = b
string set set set set of can is s Lcan the not can that languages + as of of of of
 T
also ∪ all all can all easily set all that only {ε}. be of the by be strings

palindromes strings substring written strings of be {x set is for written describe all better,

U
seen to ∈ of elegant {x Σover strings be {x over over {xacy all

as∗ {0x as ∈ {x | ac ∈ as satisfied {x describing strings |x|Σsome 0x various over some {a,

∈ | {a, is ∗ representation a ∈ x over | Σ| for at = b, x, ∈ Σ|x|∗ b, an alphabet ∗ c}2n, | least

 W
∗
alphabet {0,1}y c} some over a by {0,1} |x|formal | ∈ alphabet ≡

L
x that | the a nfor {a, the 0 = |x|. 1. {a, = ∗ x }. xac some b, that languages |x|∈ mod

languages strings Rhave Σ b, Σ c}}, ≥ but {0,1}b}. c} with Σ ∗ with 1}, }. start n 2}. in can ac

o
also ∈ in ∗ even which . as equal be in with Thus the in to }. substring set

written number English understand respective the number 0. the builder number Note
 r
language as by of can of a form stat-

ld
that lan- s the

a be of
is
s
where xR is the string obtained by reversing x.
9
www.alljntuworld.in JNTU World
5. The set of all strings over some alphabet Σ that have an a in the 5th
position from the right can be written as
{xay | x, y ∈ Σ∗ and |y| = 4}.

N
J 2.3 The ment, certain ations L, P1 P2 P3 P4 P5 L 6. 7.

1,LRecall Since L{ε} L0 Distributive usual The be The before Note ba in Proof. being

element difference, concatenation, 2, properties 1. = general. Properties as written =

Lconcatenation set set set 0L (Lthat that, a 3 emptyset {ε}L an Let and 1 substring. theoretic
 T
of of x ∪ = occurrence concatenation ∈ all Lthis all as x Properties: etc. 0.

L= 2)LL0 of ∈ 4 strings strings L. are L0; is languages 3 hold cannot Kleene so properties =

U
the of languages. that Lthen even over strings of 1Lset over

m
hold closure, 3 a L0 {x of of x ∪ {asome can in with {a, = Llanguages all with ∈ is = the any
 2LxbΣb} be not n strings 1x0. alphabet 3.respect ∗ and context | respect 2 in written element.

W
| m, commutative, Similarly, for |x|which positive n aa is some

over ≥ to = to associative. of Σ as 0}.

0}. every the union, Hence {a, languages. with x0L 1 closure. b} ∈ newly no we occurrence

o
= L which intersection, there and 0 consecutive have introduced as In
 r
Now xdo cannot well. L2 what 1L∈ not we of 0. 2 b a is s can not

ld
contain
comple- observe oper- follows,

= L2L1,
But 0 be any

10 Downloaded From JNTU World (http://www.alljntuworld.in)

www.alljntuworld.in JNTU World

Proof. Suppose x ∈ (L1 ∪ L2)L3

=⇒ x = x1x2, for some x1 ∈ L1 ∪ L2), and some x2 ∈ L3 =⇒ x = x1x2, for some x1 ∈ L1 or

x1 ∈ L2, and x2 ∈ L3 =⇒ x = x1x2, for some x1 ∈ L1 and x2 ∈ L3,

or x1 ∈ L2 and x2 ∈ L3 =⇒ x ∈ L1L3 or x ∈ L2L3 =⇒ x ∈ L1L3 ∪ L2L3.

Conversely, suppose x ∈ L1L3 ∪ L2L3 =⇒ x ∈ L1L3 or x ∈ L2L3. Without loos of generality,

assume x ∈ L1L3. Then x ∈ L2L3.

=⇒ x = x3x4, for some x3 ∈ L2 and x4 ∈ L3 =⇒ x = x3x4, for some x3 ∈ L1 ∪ L2, and some

x4 ∈ L3 =⇒ x ∈ (L1 ∪ L2)L3.
Hence, (L1 ∪ L2)L3 = L1L3 ∪ L2L3.

2. L1(L2 ∪ L3) = L1L2 ∪ L1L3.

Proof. Similar to the above.
From these properties it is clear that the concatenation is distributive over finite unions.
Moreover, we can observe that concatenation is also distributive over countably infinite
unions. That is,
(
LDownloaded From JNTU World (http://www.alljntuworld.in) ⋃i≥1Li)
 ⋃ LL
J N
= i≥1 i and (⋃i≥1Li)L = ⋃i≥1 P6 P7 P8 P9 If 0{ε}If ∗ Lε =

∗
1∈ = ⊆ {ε}.

T U
L, {ε}. Lthen 2 and LL∗ 3 = ⊆ L L+4, .
W
LiL

then L1L3 ⊆ L2L4.

orld
P10 L∗ L = LL∗ = L+.
11
www.alljntuworld.in JNTU World

J
Proof. Suppose x ∈ L∗ L. Then x = yz for some y ∈ L∗ and z ∈ L. P11 P12

N
P13 P14 (LL(L(LBut Converse Further, Land Here, x Proof. yvx LProof.

and LFor Thus, But, that 1 i ∗ +1(L1 ∈ ∗ L1L1 ···y= ∈ . ∪ )∪ ∗

converse, ∗ Ly P6, xL2)2LLLOn
L
yz by = ∗ = Li note 2. ∈ ∗
1∗ L. 2 n Let Observe 2)1) L∈ LL⊆ ∈ Lproperty = we Note ∗
2 when 1
 T ⊆
∗∗ the ∗ ∗ is Hence, ∗ . L . . (L= L= that x (yConverse implies similar.

(L .
∗ 1have for L1L x L(Lother 1 observe ∈ that 1(L∗ 2···y= x 1 2)∗ 1 that x (Lall L(L∪ ∈

Consequently,
U )
L ∗ yz L2L∗ 2P12, ∗ 1 ∈ + with L n)z 1L1 vLy hand,

L ) L
i. ∗ Hence, 1)L= iu2). = L= ∗ L∗ 2= is 2)that L, ∗ 1 ∗ ∗ i+1 1
∗
Now (y∗ . L. = we ; ∗ Lsimilar.
 ⊆
yy⊆ L∗ 2 ⊆ ∗ 1 Hence, 1 as particularly, i 1{ε} L. ∈ 1.
···yx ···y(u∈ LLhave ((LLabove,
(L ⊆ (L (L
Lwrite ∗ 1 ∗ 1 1v∈ L∗ Then 2L 1Land L 1 ⊆ n n)z 1 1 L∪ ···u 1, Hence, with (L∪ = 2. +

W
LLx = 1 Lfor ∗ 11 {ε} 1 LLimplies Now we 2)L∪ x ∪ L2)nv∪ y=

∗ . Similarly,
y1(yL∗ when ∗ all )= n)z Li have (L⊆ . ∗ 2)2)(Lx∈ 2)
2∗ each = 2 1 ∗ 1 i ∗ yz,
. Hence,
L∗ ···y1LL . ···x∪ = ⊆ with (Lx ∗ 2(LSimilarly, x m for 2)L(Ly1 = 1 where u = nz)

o L )
2)∗ i = ∪ m−1 1(v∪ L= ∗ 1all 1 x∗ Ly1 LL. 1 1 1 1u≤ ∈ u∗ 2= 2)2)···x···yi. then
 ∗
LL∗ ∗ i z L. i, .
ivso 22

by properties L
···v Hence, ⊆ ≤ L= 1(Lthat ∈ m for nz ∗ ∗ 2 . n x L (L⊆ Ln−1uwith 2L∗ 1− is u =

r . Hence,
∗
1 1 (Lx i 1) 1. ∪ clearly ∈ and ε. 1 = ∗ nvL. m ∪ LLHence,
2 nz) Thus,

ld P3
2)x 1 y ≥ ∗ and x2) m.
so in

∈ ∗1 .
12 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

2.4 Finite Representation J Proficiency of to programming

programming Thus, giving enumerated/validated. Given and finite all nontrivial may sidered
Kleene guages. languages {a}, over and {xbasis language. such 2.4.1 We catenation,

N
These representations Definition 1,...,x the come the Now, For While To

In now 0 concatenate be for the aspects elements languages we languages this a an can
language; construct strings. star example, as helpful. all finite basis consider we up
 Regular n} are operations alphabet one There interesting the have section, a operation
and in 2.4.1 look can with will ∈ interested languages, language may elements. Kleene

T
amount to a Σ, are Thus, can finite Kleene are be are {x}, {a}{b}{a}

language at be rather the represent the (Regular all as first known also Σ, obtained we the
known considered many are Expressions basis problem. infinite possible we
representation, star giving for class of to - look look languages in star be
U
with under a For with can information, x start as a of elements.

other compiler does given as Expression). a of ∈ at to finite for at finite example, have by
the language. regular language some regular a sentences consideration, languages Σthe In
get in with, the finite considering not ∗ finitely aspects a , language the for this finite
representation finite indivisible representation we {aba}. limited validates aspects expect
expressions. say languages which later the set can all context, if {ε,

W
This representation many representation; We to of x x obtained
of the languages ab, {ab}, use = Any and chapters. give information the finite the one define
instructions of to is languages, a abab, aba strings times the one the considering 0, program
give and language. finite finite union to that of representation for then respectively. by a
ababab, operation operations aspect a the know finite regular with on of infinite language is

o
representations; language applying {xfor choose say, corresponding a one

the {ab}namely - 1}∪ ···∪ {xincorporated representation language some all a single . of Even
. operations by expression sentence basis should .} ∗ languages representing concatenation
. the on {a} enumerating - can Thus, In infinite over union, 0,{ε}, is that string in
 r
languages sentences

elements. this possible. and shall be be case Σ, n}. in is, using

finite some in way,
con-
con- over
over able
{b}; lan-
and {x} is the
 ld
say

for by be it. of
a
a
an alphabet Σ recursively as follows.13 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

J
1. 0,ε, and a, for each a ∈ Σ, are regular expressions representing the are
 simply Definition by is Remark Example all Example expression Example instance, ···

N
Example substring a 2. 1. 2. finite r + In required regular is alanguages

If respectively, A from tions The 0,{ε}, and a (b) (a) n)(c) write denoted r regular regular

2.4.3. ∗ sets . if and is Kleene 2.4.6. (r (rs) (r2.4.4. smallest a2.4.5. the 2.4.7. of Σ expression

T
2.4.2. ∗ regular. ∗ r . + to are ) and union, s = + emptyset, representing
 representing s) language expression by are 0,{ε}, avoid st {aregular. star ΣAs representing
{a{a} The then = = If L(r). ∗ 1,ain regular class , n For concatenation we r the case is {x {yabz

U
{a, 2,...,aambiguity | r is and set and so observed n the such

instance, a Further, over set ∈ {ε}, of b}are we ≥ of regular of expressions {a, is ∗ the {a}, the

class languages {ab}{a, of | (r 0} n}, that an keep all y,z closed and b}the all + language

language is respectively. alphabet ∗ earlier then strings in of a (st)). ∈ strings the

expression, | L {a}, language a and regular language ab all {a, the b}= minimum with set ∗
 W
Σover representing L(r). regular b}for Kleene is Similarly, that ∗

expression. over over RRS, can ∗ a Σ can respect } ∗ a as substring . R an is ∈ the L then

be an and it {a, be ∪ the number languages star. Σ, is alphabet S, can written languages

alphabet b} represented said r by to one the + the which be For finitely union, of s to

o
language that of + languages x} represented as over be Σ example,
parenthesis t Σ, 0,{ε}, for contain can which regular concatenation, many is as Σ. ((r regular.

r
be represented (a + R obtained {a}, 1 contains we applica- ab if s) + and by which

there + aas may and

ld
For 2 the t). S,
+
a
Hence, the corresponding regular expression is (a + b)∗ ab(a + b)∗ .
14 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Example 2.4.8. The language L over {0,1} that contains 01 or 10 as sub-

J
string Since point, is Example as language Thus, regular. Example of writing

postpone a regular Example of set Writing earlier yet Definition regular a a a a

 N
{x is: another regular s s substring. L Σis and a is ∈ one example.

∗
languages. a regular regular. a , {a, regular. = = = is the grammar {01}, regular regular
even can 2.4.10. 2.4.11. 2.4.9. as expression b}tool 2.4.12. Σ{x {y01z argument ∗ ∗ follows.

T
easily {01}ΣBy and number | | expression to Although 01 {x |x|This

expression The expression (0 analyzing | The The for represent a {10} ∈ y,z Two is + notice
 U
∗
= {a, ∪ set will representing the a to 1)2n set set of ∈

Σsubstring are ∗ regular b}Chapter 01(0 of ∗ b Σlanguage. + of the be {10}Σof of that ∗ s ∗ for

{bthe regular for all 1, }∪ {u10v regular the | is strings strings handled set n+ |x|aregular. for

the strings the language m

1)language expressions ∗ a can 3 of = ∗
| some L. (see language

language we + m, languages. Regular x}∪ {x over over 2n be (0 in | have over

W
n Example As + u, n represented + ≥ one Chapter {a, {a, is 1, v
 and 1)above, 0} {a, L b∈ rgrammar | b} is b} is for ∗ ∗ can 1 10(0 ato 10 Σ|x|and b} ∗ even
little which which ∗ some be and 3.3.6), } observe b is a which 4 + = rregular. set using a

o
∗
more 2 in tricky 1)2m, hence n}, substring are contain contain is set

builder where do a that said for trickier finite tool builder job. the not In some we precisely

r
odd odd to fact, form to language of contain Hence, automata, construct be than
 generate form x} number
number

m}. at of equiv- this

the
the

ld
the

we as ab
is
alent if they represent the same language; in which case, we write r1 ≈ r2.
15 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

Example 2.4.13. The regular expressions (10+1)∗ and ((10)∗ 1∗ )∗ are equiv- alent.Since

L((10)∗ ) = {(10)n | n ≥ 0} and L(1∗ ) = {1m | m ≥ 0}, we have L((10)∗ 1∗ ) = {(10)n1m | m, n ≥

0}. This implies
L(((10)∗ 1∗ )∗ ) = {(10)n11m1(10)n21m2 ···(10)nl1ml | mi,ni ≥ 0 and 0 ≤ i ≤ l}

= {x1x2 ···xk | xi =10 or 1}, where k = ∑li=0Conversely, Hence, L((10+1)From that

 J N
Since 10 from the Since those erties expressions 1. 2.

3. 4. 5. Let rε rrr0 0to 1r1(rr, ∗ Downloaded From JNTU World (http://www.alljntuworld.in) ⊆ L((10 +
1)∗ ).

suppose x ∈ L((10 + x = x1x2 ···xp =⇒ x = (10)p11q1(10)=⇒ x ∈ L(((10)∗ 1∗ ∗ ) =

L(((10)∗ 1∗ property P14, by choosing and 1 represent regular ≈ above r1,rεr properties we 2,

T
≈ get equation and languages r. the hold following
 U
({10}∪ {1}) we the and (10 good get regular + in r3 be any

regular 2 ≈ r2r1, in general.

2r3) ≈ (r1r2)r3.
≈ 0r ≈ 0.
≈ ε.
1)∗ ). Then,

where xi ))∗ ∗ ). ) p∗ L2and 1= 1 qlanguages 2 =

 W
({10}···(10) consequently, {10} =10 or pr1qr 1

o
for (10+1) pi,qj ∗ ≥ ≈ 0
 r
(m((10) i+ ni )

ld
∗ ∗ ∗
1 ) .

and L2 = {1}, one may notice

∗
{1}∗ )∗ .
{10} and {1}, respectively,
1)∗ ≈ ((10)∗ 1∗ )∗ .
for all languages, by specializing those prop- turn replacing by the corresponding regular
identities for regular expressions.

expressions
6. ε∗ ≈ ε.
16
www.alljntuworld.in JNTU World

J
7. If ε ∈ L(r), then r∗ ≈ r+. 8. 9. 10. 11. 12. 13. Example 1. 2. Notation then a
 N
equivalent. consequence, rr∗ ≈ r∗ r ≈ r+. (r1 + r2)r3 ≈ r1r3 + r2r3.

r(r(r(rbProof. Similarly, (0Proof.+1(r1r1 ∗ +(a)+ (01)∗ 2 2)

∗
2.4.14. (0+ ≈ br∗ ∗ r2)+∗ r1 + rb0+0∗ 3)

T )
(01)∗ ≈ +. ≈ ε)b one (a≈ r(r1(r∗ ∗ ∗ r≈ b0+0can 1(10)∗ 1r∗ r2r+ b(b22 ∗ 1)+ ∗ ε)b
 U
∗ ∗
observe ∗ . ∗ )(10)a. r∗ ∗
1r≈ + 3. ≈ ≈ ≈ ≈ ∗ (0 )ε)b∗ that +

(bbbb+ +++≈ ≈ ≈ ≈ +10)aaa≈ a∗ ∗ ∗ ∗ bbbb(b(0((0(0(0 b∗ b∗ + ++. ∗ b ,

W
∗
+ + ∗ a+ + + +(10)a0(10)since ∗ 0+0∗ bb10)bb+++ ++b .

∗
ε)b b
 o
)∗ ε)b∗ ∗ . L(b∗ , + )(10)+ since 0+≈ ∗ b) (10)∗ b)⊆ +∗ L(0a ∗ L(b
∗
)b∗ ++
0) +. a⊆

r ld
∗ + ∗
b L(0). )

2.4.15. If L is represented by a regular expression r, i.e. L(r) = L, we may simply use r

instead of L(r) to indicated the language L. As for two regular expressions r and r , r ≈ r and
r = r are
17 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

J
Chapter Grammars In mar in the derivation as is rules

been in to formalize standing attribute it. Noun-phrase Further, Object” by is depicted

N
structure presented a this tool understanding a look plugging In In

various For grammatically (CFG) formal pointed which the order chapter, to into of instance,
study of in certain the as generate context trees. the as formal properties are learning to
 T
Figure in shown the in and out, notion a English Chapter observe we the

used language is general A rules similarly how of in The the a introduce to languages. in

correct above 3.1. special natural the in Verb. of to 3 regular Figure Article of grammar.

U
the of students the that a construct/validate 7. introduction

features The derivations generator. the language. words strings the present English case
Now, languages, the the languages. 3.2. English derivation Consider the Noun of sentence
notion one of As study choose are CFG, followed context sentence. the Now The Subject
automata using of may grammar generated the of Chapter the grammars

W
A automata notion the can viz. is we grammar conclude

sentences more a grammar which English grammatically by or graphical draw Sentential

also This regular Object to the theory of 2, general in facilitate the derivation be (of the that
verification/derivation called a theory. Noun sentence that of of grammar. grammar,

o
represented natural sentence can attention representation a the form this
 form notion language the context-free students be correct, for language. is a is given a
“Subject the languages) better Noun-phrase. instrumental

r
Noun-phrase of and is We of grammars third by is discussed one sentence a

validate explain
a form under- reader a gram- It called set Verb may step

ld
tree has
to of
is a
18 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Sentence ⇒ Subject Verb Object

J
The appearing, arrive to then Let respectively, set 3.1 We

N
1. 2. say of • • • • In Thus, now us main one The The A A A As
 distinguish tence rules this at some call set set set Context-Free understand the a
should a words words process, difference which then the grammar stage of of of – more as

T
grammar from nonterminal terminal rules. Figure type per you say like like

attribute where a about we their which symbol that ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ (1) which the, Article,

U
should need is, 3.1: observe is symbols. you and if the features.

Noun-phrase Article The The The The The The a to study, various not Derivation some you
symbols. grammar article in include find construct/validate word. type Noun, Noun students
students students students students that say the Grammars arrive information Noun a
students. (2) need sentences anything set word two For terminals Verb Verb. should of

W
words at Verb Verb of types example, to Verb an study study

study study of Object a nonterminals be stage English type Object have Object more
regarding as of Object of and chosen terminals Object Noun-phrase Noun sentences the
automata words (2), if where the nonterminals about the Sentence language among then

o
following nonterminal are word to type them. and of in theory you
 represent a a, the Article can (1) nonterminals, language, components. are along an In

r
discussion. words be and symbols. case assumed comes,

with a gener- the.

ld
sen- you are

we a
ated/validated.
19 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Sentence

J N
Definition where It grammar, Definition is 1. 2. 3. 4. 1.

With To convenient N Σ S P V We define ∈ is = is is this, α define N Article a we a N a The ⇒G

T
3.1.1. 3.1.2. finite finite Figure finite is ∪ require a we β the Σ. Noun−phrase to
formal a Subject if formally set binary subset set write start A Let and 3.2: the students of grammar

U
of G notion Noun only Derivation terminals, symbol, A

nonterminals, of relation following = define → N (N,Σ, if G α, × of is α = V for and the ⇒G

validating = a (N,Σ, ∗ P, concepts. Tree quadruple called αthe on study S) Verb notion 1AαV

W
production be of P, ∗ 2,β the by an a S) of or grammar = English
set grammar deriving α1γαof automata rule production 2 Sentence Noun−phrase with

o
and Object (A, Noun as a theory sentence below. α) V A → = ∈ rules. N P. γ

r
∈ ∪ using P, Σ.
 ld
Here,

a
for all α, β ∈ V ∗ .
20 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
2. The relation α yields β in Downloaded From JNTU World (http://www.alljntuworld.in) ⇒G one is
called step in one G.
step relation on G. If α ⇒G β, then we call
3. The reflexive-transitive α, β ∈ V ∗ ,
J N
A form can independent is, the type. free discuss 10. is

4. 5. 6. 7. 8. 9. X Note context grammar, be ia Xs For β. If of In simply If A from In sentence.

The tences Thus, α 1 will nonterminal more obtained α α string the ···Xa Further, particular,
∗ ∗ β
that ⇒ G α, = ⇒ given language the not of derivation β αgenerated of β the write general

T if
kAX0 a ∈ α simply X start is the ⇒G In play production context, ∈ iV type
 and ∗
s a in α αk+1 ∗ which V ⇒, neighboring and derivation, , 1 ⇒ G generated if symbol. one
only β
symbol ∗ if any ⇒G types CFG. ···Xis of in α by α is hence ··· said

U is ∗ if called
step grammar case, ⇒stead role G if n ∈ G. n, of

β,
⇒we G and L(G) In rule ΣS to then That in the grammars. closure ∗ If αby the we by of
then as
then { deal , symbols of n−1 be it of the the then G. = replacing ∃ n α ⇒rules G G,
we a
say the later may a that is, a ⇒G = {x with we sentential That replacement. .
derivation
nonterminal ≥ denoted grammar of α ααsentential the ∈ be say 0 A n chapters,
 say
W
0 of is is ⇒G only Σ= → and ⇒G is, A written defined

β is ∗
generated sentential ∗ ββ A is | in α αS is is S by one 1 denoted with αform Xis are ⇒
derived ∗ in
the 0,αa ⇒ form ⇒G 1 we L(G), of derivation, A α.
G.
···Xgrammar here as One x}. said 1,...,αyield ··· α. the in relax appears by form α XG,

o from β.
by kAXmay is ⇒1 to G is This n G. form ⇒G ···Xof if known the the
 ∗ α .
be ⇒ Gn α αα k+1 the G, call ∈ n−1 then in replacement is A of can constraint kαXset V

or That
r
then ···Xderivation. → known context-free a ∗ A as ⇒G be of the k+1

α derives
sentential such α, is context- αn. we all derived
is,
within n ···X length where

That = as may
sen-
 ld for
and that

β.
is a
n
21
www.alljntuworld.in JNTU World

J
Example 3.1.3. Let P = {S → ab, S → bb, S → aba, S → aab} with Σ Since
 N
right In Hence, Notation Example {xNow, ({S},Σ, Example (N,Σ, = 1,x 1.

2. 3. 4. 1. 2. 3. 1. 2. 3. fact, {a, hand S S S S A Normally specified. To tion Σ 2,...,xS S S left

as P, the ⇒ ⇒ ⇒ ⇒ → → → we → of b} P, give discussed S), 3.1.4. hand rules 3.1.5. the ab
bb
aba
aab
0S
1S
ε S) αand 3.1.6. sides precisely language 1, where n}. a generates grammar A
T
grammar N we side only are Then → Suppose Let = use in P αof terminal

have {S}. generated since 2 Example has Σ S each consider can the G

U
as G = L(G) the precisely Then L one by = be the language

{0,1} production is strings, following (N,Σ, looking written may a = by start 3.1.3, the G finite
{ab, G, = and the easily finite P, (N,Σ, symbol L. bb, every at one language as S), following

W
N derivation rule the aba, A set find can = it P, → derivation is

rules. of is aab}. {S}. P S) the αeasily the sufficient a over = 1 production grammar, is | in {S

other start αConsider a an 2. G. observe context-free → in alphabet

o
symbol components to xG 1 give unless is | rules. xthe that of 2 the S |
 r
length Σ, CFG grammar.

ld
··· otherwise and the say produc- N | CFG their G xone. L and

n}. =
=
22 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
We now observe that the CFG G generates Σ∗ . As every string generated

J
by hand, rule as Hence, Example by Method-I. ({S},Σ, Method-II. terminal

generated Example rulesLet generated and If nonterminal terminated we

N
1. 2. shown a G us then S CFG. is S S use let → S x look → → a P,
 symbol ∈ rule below, ε. sequence x in the in ⇒ ⇒ ⇒ ⇒ If = aS ε 3.1.7. S) 3.1.8. ...L(G).

T
Consider by ∈ Otherwise, at one S G the does (2) Σrule aaaax. so using in

the 1S 1a1a1a∗ x . step on set we Thus, The 2S 2 2 that Consider the can If (1), not of

···a···astrings its of a get x rule by 0 resulting language CFG be L(G) generate = s

U
productions nS nε right then let L(G)=Σusing the and derived ε,
 (2). x that G (if (as (as (by = G S then string one = hand 1 = the in 0. ⇒ as, aabove)

above) Thus, sentential rule any 1 0 can ({S},{a}, 1awhich may clearly ∗ aS = in x rule . 2
(over side. a can P ···a0, G. string 3) be in ⇒ for notice is then S

W
two each generated aε be n, any Clearly, → we empty, any form.

where P, and = generated by ε. steps have production alphabet a S) that Further,

derivation rule hence then where ano A L(G) as by i there 1; = derivation follows: terminal
 o
L(G) clearly G. in else 0 Σ) ⊆ P if or rule will one we Clearly, Σof can has

by 1 = ∗ . choose length for has step always the 0. rule string On the be can all some CFG

r
generated using the 2)

following ε only i. rule k, can can be other Now,

non-
that G the

ld
the

(1) be
be
be =
23 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
derives some string x, we would have used rule (1) for k − 1 times and rule (2) once at the
end. Precisely, the derivation will be of the form
S ⇒ aS ⇒ ...Downloaded From JNTU World (http://www.alljntuworld.in) aaS ⇒ k−1 Hence, it is clear
that In the following, we Example 3.1.9. Consider rules: One may notice that the than ε, and
 J
the derivation typical derivation is of Hence, Example generates aSa left or

N
example, S and and → L(G) right S ε the the 3.1.10. will → =
 T
palindrome set bSb sides. {aproduce of nwill bThe n all While | { aa···a k−1

}} { S
⇒
{ aa···a }} { ε = ak−1
L(G) = {ak | k ≥ 0}

U
give some more examples the grammar having rule the n grammar
≥ S S → shall form S ⇒ ⇒ ...⇒ ⇒ 0}.

W
always → aSb aSb aaSbb aSb should be | ε be terminated anSbn

anεbn = anbn

o
used of the typical to following by derive S CFGs.
 r ld
→ strings ε. production Thus, other

a
S → aSa | bSb | a | b | ε
palindromes over {a, b}. For instance, the rules S → produce same terminals at the same
positions towards terminating the derivation the rules S → a | b odd or even length
palindromes, respectively. For
abbabba can be derived as follows.
S ⇒ aSa
⇒ abSba ⇒ abbSbba ⇒ abbabba
24
www.alljntuworld.in JNTU World
 J
Example 3.1.11. Consider the language L = {ambncm+n | m, n ≥ 0}. We now

3.1.9, can right rule can aany b say to and to can lowing Now, Example in ms the

N
cproduce handover must mA, be be be a c give . extremes one s the

after similar Note and production used introduced, are used be production production can
 T
3.1.12. to define b a different that, to the s to b. lines easily be and of

produce terminate Thus, job equal, a b the rules c string. For of s which observe s rules of

U
in from rule Example rule on the a producing a equal choose of

either nonterminal string of terminate In the S. a language a that CFG, case, S number
Hence, B CFG A S derivation the 3.1.11 A sides. → may A S L(G) → → → → S b A S there
say aSc rule → → which s → {a→ the → bAc have we and to of Eventually, AB aAb bBc
 symbol aSc bAc
G. = m| A ε

W
ε is ba A A. derivation. choose L. | and m+ngenerates produce

leading s no ε | | | and ε ε Again, ε cb that produce n in a | c m, the the s, a new a may s; L.

o
since respectively, Thus, n CFG string, rule but, ≥ nonterminal As a be

string 0}, the as given there used we the one given number have of in production to will in
 r
may the Example below. produce symbol, left the not think of form and

ld
fol- b be s

25 Downloaded From JNTU World (http://www.alljntuworld.in)

www.alljntuworld.in JNTU World
 J
S ⇒S ∗ S S ⇒S ∗ S S ⇒S + S 3.2 Let three rules. A derivations In For

substring substring of derivation Definition A is iteratively ∈ a nonterminal

N
1. 2. contrast a Figure The us example, N derivation string, derivations

A If nodes node Nevertheless, consider and construction is the Derivation b a; the 3.3
tree, defined (1) ⇒ ⇒ ⇒ ⇒ B ∗ to derives α with we rule 3.2.1. whereas, a. from ∈ the root
 T
gives that, Figure in S S a a that the which introduce V In are labels B + +

∗ + ∗ second G. as , left order of a the S b Let CFG the three S → suppose the different,
appears of ∗ follows. ∗ the 3.3: A ∗ will S the a to a same XXthe a derivations G

U
derivations derivation → to whose 1,X1XS tree. derivations right

a = Derivations be second Trees derivation S in distinguish 2 graphical (N,Σ,

 2,...,Xsubstring at ···X∗ a because step in S useful production (2) ⇒ ⇒ ⇒ ⇒ a | that S A k
∗
particular S (2) tree 2 P, (1) is in ⇒ S a a a + k for of tool tree S) of for representation + + +

W
are order. and + applied of S this α step and or derivations

application the S b b S be | the a ∗ ∗ created for of ∗ (S) a (3) ∗ rules + feature S a (2) 2

S string a S parse a common string b several of are CFG | derivation in ∗ share a are: a

derivation the | and not a tree in between b of (1) a and + other of (3) + the ⇒ ⇒ ⇒ ⇒ both
 o
derivation, different position sharing made b and of b a ∗ V ∗ is following

a. a a a a derivation the a purposes the illustrated = + + + + (3) the (2) children Note S S b
b such derivation N sequences in derivations. ∗ ∗ derives derives derivations ∗

r
∪ S a then S both that feature.

feature.
Σ. also. to called

with new For the

the
the the

ld
the

of
is
the following examples.
26 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Example 3.2.2. Consider the following derivation in the CFG given in Ex-
J
ample The Example ample The derivation Example

N
Note derivation derivation 3.1.9. 3.1.12. that tree 3.2.3. 3.2.4. the
 T
by tree tree Consider Recall yield juxtaposing of of the the a a α

U ÐÐÐÐÐ Ð aa
ÐÐthe of above above the A A A derivations S the

aap aa pp b p p
p the S following aa a a ⇒⇒⇒⇒⇒⇒ b = derivation derivation derivation ÑÑ⇒ ⇒
⇒ labels ÑÑ= pÑÑp Ñ
Ñ
AB aAbB aaAbbB aaAbbB aaAbbbBc aaAbbbεc aaAbbbc
SS
S
Sε
aSb aaSbb aaεbb aabb
a

x aa
W xaa x xb b xx ÐxÐ Ð ∗ ∗
given derivation aaof b S S the ÐA x ⇒⇒
 BB ∗ c
o
in ⇒ ε leaf aabb aaAbbbc b Figure bα bbin nodes can is the shown

r
be 3.3. is CFG from identified shown The below. left given derivation below. to in

in right. Ex-
 ld
the

trees corresponding to these derivations are in Figure 3.4.

27 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

J
derivations, the are application rules example, (1) several yield leftmost

Definition to the derivation Similarly, rightmost rightmost derivation tion, properties leftmost
 N
Theorem be Now Because and S a section. same. leftmost the in is a

equivalent (2) leftmost a a + we S derivation derivations. properties as terminal derivation

g {g {g
derivation Thus, for nonterminal is is { for 3.2.6. of of of derivation are which Two 3.2.5.

{g { ∗
T
nonterminal denoted denoted gFigure (1) A the same rightmost S S b

g gg g
in Figure derivation equivalent ∈ derivations similarity For precisely a derivations.
 S
gstring, (or For N of production 3.3 a position can if by by the trees A and rightmost

U
symbol 3.4: are the A A A ∈ derivations. be symbol leftmost ∈

∗∗
there N ⇒⇒ equivalent. captures (1) if x derivations between production Derivation L R are
x. x.
permuted S a to N the and ∈ and rules. However, of formalize and said Σ is
S∗ g {g
derivation). of production + x the derivations , (2) a { ∈ leftmost the the to x the
{g {g { S ∗
unique That Now, Σ gof sentential (2) Thus, to ∈ are Trees be S rule
 W g g
∗
b feature sentential , Figure derivation for Σthe get A

g g ∗ S
equivalent precisely ∗ is, we g, applied derivation special ⇒a a rule for a notion an the
can the derivation given establish proposed x 3.4 Figure equivalent form. if applied
S ∗
derivation be application form. are A and differed type of at if derivation imitated a⇒

o { { { {
same, their and equivalence each {3.3 only In some in In tree of at x (3)
 +S
rightmost S the which b which derivation. derivation is derivation, by each A the step if
g g{ g{ g{ ∗ { S
may {of to properties said beginning A⇒ the g tree, production derivations get ∗

r ∗ x.
step ⇒is represent case, case, x L c between order to ccsimilar on cis deriva-

whose
S
a
is trees be said viz. For
the
 ld
the the

on of
of
of a
28 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Proof. “Only if” part is straightforward, as every leftmost derivation is, any-

J
way, be Otherwise, αsubstitutions leftmost derivationin in derivation extend
 N
for But, step, γfollows. 1 k A to which ∈ ⇒a For Since some = A a V

since say a derivation. L A = αderivation. ∗ derivation αthe “if” 0 substitution using k+1. =
αpth y αthere ⇒0 k is the ∈ αgiven there part, L ⇒⇒ 0 step Σof Then, in αL

T
⇒ the ∗ derivation 1 αare A , αsame the L ⇒k+1 Ais derivation let 1 (for If =
αrule 1,AL ⇒leftmost an 1 we ααfirst but ···⇒to ⇒L i 0 p>k), length 2 i ···⇒A⇒ ⇒have L ∈ (k

U
such α1 k ···⇒L eventually N k α+ L → steps. 1 to

⇒αsubstitutions ααα1)th L and α⇒ of Ai+1, that γk+1 k L i a k α1 1 L ⇒⇒αthe = k αleftmost

would ∈ αβk+1, = step. 2 L for L αk We yA1,βP. ⇒ ⇒ ⇒ ⇒ ⇒ ⇒···⇒ = α αi yA......⇒ original.
yields k+1 ⇒i+1, 1βall 2 we Thus now 1βhave αThat yAααααα∈ L

W
1A k+1 k+1 k+2 p−1 p p+1 ⇒ 0 1γderivation have for αV in 1β2β= i+1.
2β≤ the ∗ demonstrate α been ⇒···⇒ , the 1A= α2, = = = the yγall is, k+2 2. and n−1 i Hence,

yAyAyAyA2β1ξterminal Let we < i<k, original first ⇒···⇒ p−k−1 2 substituted ⇒ 1ξ1β1ξ1ξAn,

∗
o
show k p−k−1 1, 2,( A 2 1γα→ be α(k by then 2βn ⇒ with i.e. n−1 here L =2

x.
+ γstring derivation the how how induction 2α x we 1) ⇒ ∈ we ξn−1 ξleast 1 by 1 P to to

r
steps αhave = are ⇒ x, n ⇒ such some convert extend β= ξat 1γsuch α 2)
 through.

leftmost

looks x one and n 2βa that string = 2 later that

can the the
x

ld
the

as

⇒ αn = x
29 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
J
We step substitution, As Proposition Proof. Note cisely tree tions of applied

N
D2 application stated α α α α α α α Now Now are now is so k+1 k+2 k+3

p−1 p p+1 n are that represented = = A same Let identical. that ...

... to we = = = = = yγwe demonstrate α= same. earlier, n the the yγαyγyγyγ1ξT αhave p+1 for
 T
we are 0 p−k−1 1ξas 1β1β1ξbe 3.2.7. ⇒of production leftmost p−k−2 2 1A1γget

Ddesired. Moreover, ready L the the production 2βwe 1 2βby α= and a 2 1 2 following

derivation have Two its α= desired ⇒a p to nonterminal yγDL mechanism

U
children 2, ···⇒1ξequivalent the establish rules as the 1 rules
derivation. Dderivation theorem L 1 tree production applied in and αare k the of the of
symbol. leftmost ⇒Dalso ⇒ ⇒ ⇒ ⇒ ⇒ ⇒ = using two by ......derivation 2

W
L at correspondence in Set are induction. same; each which yAα

α α α α α α leftmost rules k+1 k+2 k+3 p−1 p p+1 n the Hence, leftmost derivations 1β= = 1A= = =

= = nonterminal yγαrule applied that (k+1)th n tree. yγαyγyγyγ2β1ξ= p+1 derivations the p−k−1

o
1ξ2 1β1β1ξAderivations, is, x p−k−2 2 1 1A1γ Since between derivations in →
are each 2β2β= step both 2 2 γidentical. αsymbol = 1 the production p in has yγDthe
derivation

r
derivation 1 1ξ(k the leftmost and 1

Dderiva- + is 1 order 1)th

pre-

ld
and D 2.
is
trees and leftmost derivations.
30 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Theorem 3.2.8. Every derivation tree, whose yield is a terminal string,

J
represents Proof. A A that Theorem For where Proof. rule Hence, given

Hence, 3.2.1 Let two identified there symbol, of to to Definition two grammar Remark two

∗∗
N x.
compiler ⇒⇒ be an L G x different of different or is x. are for
ambiguous. ∈ ambiguity h be G, For Since represented |x| T more L(G), one 3.2.11. is By
Hence,
binary multiple Ambiguity each is a is by ≤ a A the 3.2.9. which context-free said
a 3.2.10. unique may Theorem κκ rightmost ∈ inequivalent their leftmost κ-ary hinternal if

T by
height is . N One trees, to T in the have is and Let possibilities by

Proposition
different is be parsing. leftmost constructed tree. can Formally, of maximum a
G one x T. 3.2.6, unambiguous. derivations a node derivations κ derivation the = ∈

U
equivalently grammar. difficulty = Now, can Σderivations (N,Σ,
 3.2.7,
tree ∗ max{|α| of derivation. derivation we Thus, , of suppose easily T a in length T.
based can application is P, CFG |x| in the for tree a or a It S) prove find say parent ≤
we
choosing | grammar derivation may some for similar on A T be for of G κtrees.

W have
that h is → an a is a righthand a x, that the be grammar,

CFG α of string said string of equivalent a then ∈ lines a at a While derivation production
a unique
CFG with T P}. correct case trees most to and has in x of be side G such ∈ that
 o
deriving this L(G). Theorem at for κ is ambiguous, leftmost rule. L(G).

leftmost
number most ambiguous, of tree a a difficulty rules the string each property
Otherwise, In of κCFG the This h 1.2.3 on a the of derivation production leaf derivation

derivation
r
in string, the children. will if context if G L(G). can that is nodes. G G

same gives
lead said
has

ld
has the

be is
if
31 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Example 3.2.12. Recall the CFG which generates arithmetic expressions
J
with As leftmost Example expressions as is there a Example is [1979]. 3.3

Definition production side. Example clearly Remark leftmost exactly A CFL inherently

N
desirable follows. → shown In the That are α the is linear. one ∈

Regular derivations, derivation 3.3.3. production some known in context P 3.2.13.

3.2.14. 3.3.2. is, rule (the that nonterminal ambiguous. 3.3.1. Figure = ⇒ {aWhereas,
 T
CFLs If mof language as the bThe G of mα An The G inherently as A 3.3,

crules ∈ is constructing viz. for nunderlying has dunambiguous well S CFG Grammars

U
ΣCFGs n a context-free the the which ∗ For → symbol | (2)

linear at generated m, or as S arithmetic CFG proof, G most R T S and n given ∗ rightmost

ambiguous α there = S ≥ grammar, → → → grammar = in (3). | given a 1}∪ {a(N,Σ, one one
xBy, S the in grammar compiler by language is S T (S) + Hence, Examples may + no
 W
nonterminal ∗ expression the sentential S in derivation. R P, | T

language. m| CFG for a Example be b(S) then CFG | S) refer | n| R T cor which some the b
unambiguous. nis d| which similar m to a every given 3.1.8, said grammar form a | | the +
symbol generates x, b m, 3.1.12 This is b y to in Hopcroft n derivation of ∗ 3.1.9 such

o
unambiguous. ∈ ≥ a Example is be each Σis has is 1} because in ∗

applications, not linear Unfortunately, and ambiguous. the and its internal two and linear.
 r
arithmetic 3.1.11 righthand in 3.2.12) different B if there Ullman G ∈ every Such

ld
step is N. are is

it
is a
of the derivation.
32 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

J
Definition 3.3.4. A linear grammar G = (N,Σ, P, S) is said to be right linear if

rule symbol for rules for linear a equivalent mean, linear Example by Example We

N
properties derivation tion rule hence nonterminal the parallel any, the

Similarly, Because For Since some some language, understand is so will in grammar,
grammar if at if of following occurs the far – the the L x x each have we the as result they
3.3.5. 3.3.6. right of generated. ∈ ∈ language is nonterminal of following shown symbol. are

T
∗ ∗
ΣΣa form the we generated at the internal L at left determine that that

linear and and every for production = looking need the The We strings similarity most – {x
linear below. the {agenerates a B B right the form. While, give CFG not ∈ result step

U
grammar terminal k ∈ ∈ one other. symbol {a, by | for that

nonterminal grammar N. N. the keep k a end. given of A A a b}in ≥ rules.right nonterminal a

which we properties right ∗ → → a the 0}, they right L; track In | in desired string S are That

(see x x |x|in linear and definitions an the fact, → is linear is a or or Example generate

generating linear of = Exercise equivalent Sa true defined righthand is, vice-versa. symbols

W
followed the A A the 2n derivation, grammar of | symbol

righthand → → grammar, ε for + the grammar number notion xB Bx of 1, 3.1.8 or by one

??). partial left a in by left side whenever for considering on sequence for can a is at of

linear we of Here, side linear some of then grammar a for its the left most b string be right
 o
will each s righthand L, of that grammar language imitated by linear n}.

there grammar they of have one each each linear production that the equivalence a are
maintain s nonterminal appear exists grammar exactly production production

r
production the and generated, grammar. to and side is deriva- obtain

b a given right s rule, in and one left

 ld
the

for we is
a
so far. Whereas, we need to keep track the number of a s; here, it need not be
33 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
the actual number, rather the parity (even or odd) of the number of a s that

J
are two beginning – symbol the symbol as switch O production Since,
terminate production Hence, has L(G) in in the Theorem ular. grammar hence to Definition

N
mars. Remark equivalent, in on Chapter Chapter support. the Recall An

generated language. terminal nonterminal the general, generating = postponed Moreover,

our number to elegant we E E. L. above 3.3.9. that E to of that have a criteria 3.3.7.
Whereas, 1 rules. rule 4. left on 3.3.8. any Here, be derivation even symbol (refer so In

T
generates In defined proof the of Since generating the the linear any
derivation, symbols, far. fact, view to for a The number we language is right Example Right
start s later number of b, if generated So to every left we could of grammars three language

U
one this the while L. generate to linear symbol the have

chapters. say linear linear of an a keep derivation we theorem regular under productions.
identify of theorem, 2.4.10). a is O a continuing the would E O grammar s. b generated so
with and generated of grammars s. track grammars → also → Thus, a O following
discussion far the Precisely, For language string E, bE bO would → a the have Whereas,

W
precisely we will can of desired right respectively proof ε | | it G
 symbol the aO aE in have Now, then generated by is with continue = be require are and
result. O. linear expected we ({E,O},{a, parity is a of L, odd grammar. the we also we right
stated generate odd one the have right That O there did from change following some
grammar and for to information, theorem, called can zero number linear obtained as that not

o
linear is, odd be exists continue even. easily more number While a regular

b}, with we to supply as regular and the grammar definition. P, that the of grammars a one
introduce regular concepts Similarly, the observe E), nonterminal nonterminal even. E right

r
a to we of symbol languages. s, any may generates generates
following
language where symbols be we require is In gram- linear proof
refer with
that
and reg- can the
the

ld
are we O,

P
Hence, left linear grammars are also called as regular grammars.
34 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Example 3.3.10. The language {x ∈ {a, b}∗ | ab is a substring of x} can be generated by the
following regular grammar.
S → aS | bS | abA
A → aA | bA | ε
Example 3.3.11. Consider the regular grammar with the following produc- tion rules.
S → aA | bS | ε
A → aS | bA
Note that the grammar generates the set of all strings over {a, b} having even number of a
s.
Example 3.3.12. Consider the language represented by the regular expres- sion a∗ b+ over
{a, b}, i.e.
{ambn ∈ {a, b}∗ | m ≥ 0,n ≥ 1}
It can be easily observe that the following regular grammar generates the language.
S → aS | B B → bB | b
Example 3.3.13. The grammar with the following production rules is clearly regular.
S → bS | aA A → bA | aB B → bB | aS | ε
It can be observed that the language {x ∈ {a, b}∗ | |x|a ≡ 2 mod 3} is generated by the
grammar.
Example 3.3.14. Consider the language
L=

J
Downloaded From JNTU World (http://www.alljntuworld.in) {x ∈ (0 + 1)∗ It
 N T ∣
However, is little using tedious a ∣ ∣ |x|0 is even ⇔

U
|x|1 is odd
 World
}.
to construct a regular grammar to show that L is regular. better tool, we show that L is
regular later (See Example 5.1.3).
35
www.alljntuworld.in JNTU World
3.4 Digraph Representation
We could achieve in writing a right linear grammar for some languages. How- ever, we face
difficulties in constructing a right linear grammar for some lan- guages that are known to be
regular. We are now going to represent a right linear grammar by a digraph which shall give
a better approach in writ- ing/constructing right linear grammar for languages. In fact, this
digraph representation motivates one to think about the notion of finite automaton
J
which regular Definition digraph the In Example is Remark linear Example is

N
Remark its conversely. in The digraph as as Example 1. 2. which

digraph, Consider edge derivation follows. follows. (A, (A,$) will grammar. languages. (V,E),
(refer 3.4.5. 3.4.3. set B) case, be 3.4.2. 3.4.4. We ∈ 3.4.1. 3.3.12. by E ∈ the shown, E to
 T
the E A is From illustrate a can where ⇐⇒ following Example ⇐⇒

derivation formed path The The arc Given be in a A A the digraph digraph from S the from

U
digraph traced → → ⇒ GFED@ABC GFED@ABC this as a

derivation S vertex S next 3.4.4) x right xB aS A follows. in the ∈ through to a by for for P,
⇒ ∈ chapter, one right starting linear as set B P, a the the aaS for is shown path can V for
 W
for some linear grammar grammar labeled the ⇒ grammar = the

as some easily node from N aaB following. below. an x a,b

∗
b string grammar ∪ ∈ ultimate by x {$} ε b ⇒ S give S T presented presented ∈ G x.

to aab to T aab with = ∗ ?>=<89:; ?>=<89:; the the $ $ $ (N,T,P,S), can in tool in

o
a corresponding special the new the in in be in Example understanding
 r
symbol define 3.3.10 $ Downloaded From JNTU World (http://www.alljntuworld.in) and

ld
the

a,b

ab GFED@ABC A
right
Example 3.3.12
a

ε GFED@ABC B
represented, in node $; and
grammar given
corresponding
S aS aS εB b$
36
www.alljntuworld.in JNTU World
One may notice that the concatenation of the labels on the path, called label

JN
of label the of path, any path gives
T U
from the desired S to $ can string. be derived

W
Conversely, in G.
 or
it is easy to see that the

ld
37 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
 J
Chapter Finite Regular regular expressions. tools ular

Recall representation Let E. so node being of nodes some state languages with between

N
finite state a far Thus, We us s; language can O, transition finite to

information state at holds we rather the traverse notice languages grammars, then
understand the the be in have having grammar transition number considered some a node
 T
states Finite once so digraph - that, of the encountered system,

Automata the far the finite $ it information - we digraph on automata, we as

has set at the of can for the E 4
GFED@ABC

grammar reach systems. language symbols that have as a representation, states it the of

U
this class be regular b given a automatically all memory via
 same models considered to traversed even language strings of only. as about $, is point a
of a a As generating languages languages sequence then effect given language number the
the a creating In of the system over through alphabet. as we we as as transitions below:

W
time, such changes GFED@ABC given O traversal. will a restrict

that of of {a, devices, accepting better. that state unit. a which a b a if b} not odd s. s in of
system we and states Thus, are having node of Example Whereas, ourselves As have
number are Let are are understands As ε the b represented we devices, s predefined based

o
O, we each intended at any us we starting system are odd regarding the
 may consider of 3.3.6. to have further if interested node ?>=<89:; on number a $ are we

r
those node s. call and the at a to transitions by A are important Of in is language,

the generate
move.
them symbols the E, systems digraph
number
hence holding a regular course, at of in finite node then reg- a the

ld
the
as s.
a
given as input. Thus a finite state transition system can also be called as a
38 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
finite state automaton or simply a finite automaton – a device that works

J
automatically. they automata, them 4.1 Deterministic transitions sition

wherefunction. assigns Example the Clearly, states Transition Instead may table arrow
N
In a Q Σ qF δ Note We following 0 simply deterministic : model of are is

⊆ is ∈ this from to Q of normally a of a Q, a Q, s transition Deterministic × that, a

point unique to finite finite chapter, explicitly regular 4.1.1. DFA. Σ are called = called a

T
point the represent Table −→ state table: (Q,Σ, finite for deterministic, The
 the set set class use next Q the every the Let out finite grammars function, initial on we

called called plural δ, giving is automaton symbols initial/start set state. of the regular p, an

U
Q introduce a state automaton F) function = regular input of

state the the initial form all {p,q,r},Σ= is final/accept called in and and p, input set

languages. the a and symbol. the q, of DFA. Finite is the state languages. called of

regular an r, components p δ q r state, automaton a transition sense (DFA) we alphabet, .

 W
states, notion . type input a q r r . and encircle with the Formally,

states, p p r b that expressions {a, of is the symbol, Automata of transition or a In finite

b}, table. finite is there quintuple of final without all and fact, automata. F the the automaton
the = automata states will For quintuple are we {r} function final transition subscripts

o
be s instance, observe equivalent; of and exactly = states. the (Q,Σ, and of
 r
in δ or DFA is a that function which we show next-state to one Thus, DFA, given

δ, each denote use qin finite tran-

0,F), that
the

ld
the
we
we by
an of
δ
can have an alternative representation of a DFA, as all the components of
39 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
the DFA now can be interpreted from this representation. For example, the DFA in Example
4.1.1 can be denoted by the following transition table.
δab→pqp

J
Transition Normally, concepts tion transition a arc Extended Recall symbol.
 N
state and 1. 2. 3. 4. 5. The Note from for for Every If If another There

Final b. that δ(p, there transition a This that each r better. As DFA, we diagram to the states
Transition a) state is Diagram indicated associate are r there naturally state, state an

T
= transition labeled (Q,Σ, q, In multiple arrow in are diagram which then

are and then the Q indicated δ, in some is ?>=<89:; a, two can with an Function present
U
p qthere function we represented 0,F), b. the can arcs for input

transitions be b simply graphical no point be is the a b from extended called by context

source constructed an string. δ DFA double assigns q r put 3 ?>=<89:; arc labeled q by

W
above, a representation r r from into state only from given a also

to p r
 circle. node. a all the astate the one these transition we as 1,...ap in strings to initial

follows: state have Example arc for q are k−1, labeled labeled each to a, in a r state indicated

o
diagram understand b and to digraph Σstate 4.1.1 ∗ itself , a. qaai.e. 0.

r
1,...,ak, and is one or on representa- assigning by as simply an abstract
 symbols a state k−1,abelow: to k. a
Downloaded From JNTU World (http://www.alljntuworld.in)

ld
single
input a 40 a ?>=<89:;/.-,()*+r
www.alljntuworld.in JNTU World
ˆ
The extended transition function δ : Q × Σ∗ −→ Q is defined recursively as follows: For all q
∈ Q, x ∈ Σ∗ and a ∈ Σ,
δ(q,ε) ˆ= q and δ(q, ˆxa) = δ(δ(q,x),a). ˆFor example, in the DFA given in Example 4.1.1,
ˆ
δ(p, aba) is q because

δ(p, ˆaba) = δ(δ(p, ˆab),a)

ˆ ˆ
= δ(δ(δ(p, a),b),a) = δ(δ(δ(δ(p, ε),a),b),a) = δ(δ(δ(p, a),b),a) = δ(δ(q,b),a) = δ(p, a) = q

Given p ∈ Q and x = a1a2 ···ak ∈ Σ∗ , δ(p, ˆx) can be evaluated easily using the transition
diagram by identifying the state that can be reached by traversing from p via the sequence of
arcs labeled a1,a2,...,ak.
For instance, the above case can easily be seen by the traversing through the path labeled
aba from p to reach to q as shown below:
?>=<89:; p a ?>=<89:; q b ?>=<89:; p a ?>=<89:; q
Language of a DFA
Now, we are in a position to define the notion of acceptance of a string, and consequently
acceptance of a language, by a DFA. δ(qˆA string x ∈ Σ∗ is said to be accepted by a DFA s

= (Q,Σ, δ, q0,F) if 0,x) ∈ F. That is, when you apply the string x in the initial state the
DFA will reach to a final state.
The set of all strings accepted by the DFA s is said to be the language accepted by s and is
denoted by L(s ). That is,
ˆ
L(s ) = {x ∈ Σ∗ | δ(q 0,x) ∈ F}.
Example 4.1.2. Consider the following DFA
GFED@ABC q0
a c ccccc cc
b GFED@ABC q1 a cb
a

GFED@ABC?>=<89:; q b
2

Downloaded From JNTU World (http://www.alljntuworld.in)

JNTU
 Wo kkkkkkkk kkkkkkkk
?>=<89:; t kkkkk a,b

GFED@ABC?>=<89:; q
3

rld
a,b
41
www.alljntuworld.in JNTU World
 J
The the language Example DFA Hence, having Description Note Figure

figure, and to such connected a function called reading δ(p, state time.

N
accommodate 1. 2. At string a) finite only that given that from One from

after If and the a there = 4.1 aa the The the a given along way accepted q, each q symbol,
control. current ab may as a to 4.1.3. p the reaching shall language in but then input finite
 T
DFA are to the and substring, to Example of point initial cell with notice q

never facilitate mainly reach input a an at (now it As is control state, does It say by
accommodate DFA is to an input a the accepted of shown is state the that pointer through
reach from tape a, r the abstract ?>=<89:; 4.1.1. assumed time, not i.e.three next pointed p

U
we has from DFA one of {xaay pointer if p from the contain

below, continue b the any to there point the the components that by to abb a b the isinitial the
 final (computing) by that finite length. {ab, states the | understand a DFA x, will to is points

let input single of final the aa, ?>=<89:; y aa DFA q to state reach abb}. a time state us

W
control, ∈ will point DFA pointer and then be in state The recall

{a, tape input to namely is the r. at the be another qa the b}exactly 0 the to has we device. its
input r to r. ∗ in called input, which the DFA and symbol. }. information q) on behavior. will

set the Since ?>=<89:;/.-,()*+a some r and input transition left-justified any tape the final of
 o
one final will the can be The then a, the r all internal subsequent reading b

The shuffling tape, state. is is state read current change state depiction strings the reading

also divided As of reading diagram one reading the DFA qshown qa 3. state, infinite head 2

r
its symbol. trap over between is symbol transition Thus, head into input. given
 through leads internal head will in say of {a, state, head, tape cells
will the
the

ld
the

be us
b}
at in
p, is
If p
move one cell to the right.
42 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
 J
the placed By state, the Configurations A tion from a and figurations.

N
Definition δ(p, one In simply be configuration configuration a denoted

Initializing Observe The Clearly, the input DFA. a) step a about given and then final = on
time use notion and q tape on the context, the and configuration |−− the by that For 4.1.4.
 T
the |−−to is first from |−−* a current of instead input x is denoted the or

which, A Figure input DFA for = . an computation an cell That Let if the ay, reading is a
element x there instantaneous with is given a state first and of C left then 4.1: is

U
as exhausted, binary is, of accepted = |−−C most an is a C by

head, we Depiction input and (p, we Aof DFA |−−only |−−* input . setting define in x) Q say
relation A (first) the The C i.e. a × string and C is one by that if DFA description portion Σif
 W
string . of reflexive one the the ∗ of the the and cell C . DFA the

on the x Finite s current step portion = DFA. initial of the only x form the of DFA (q,y) under
can the ∈ transitive initial relation the Automaton Σof set if Otherwise, tape (p, be ∗ state
state s yet there a be input we discussion, of DFA ε). described moves configuration two

o
with to mean configurations as of as exist closure be string gives the the

follows. configurations. the from x read. x configurations DFA current is through then be
 r
reading the that rejected of C placed Formally, is informa- is |−− to we is a (qof

state. C right head

final
con-

ld
may may 0,x)

s on by
in If
.
43 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

C0,C1,...,Cn such that

C = C0 |−− C1 |−− C2 |−− ··· |−− Cn = C

Definition 4.1.5. A the computation of s on the input x is of the form
C |−−* C
where C = (q0,x) and C = (p, ε), for some p. Remark 4.1.6. Given a DFA s (q0,x) |−−* (p,

ε) for some p ∈ F.
Downloaded From JNTU World (http://www.alljntuworld.in)

= (Q,Σ, δ, q0,F), x ∈ L(s ) if and only if

Example 4.1.7. Consider the following DFA
GFED@ABC q0
b
a
b
a, b

a GFED@ABC q1
b GFED@ABC?>=<89:; q2
a GFED@ABC?>=<89:; q3

J N
As of Thus, which the 1. 2. 3. 4. 5. states It the On qof
 Further, subsequent of Since one Subsequently, which also But, not role the DFA have 0 is

qan to 1 the initial of a occurrence of be clear language from in qab. final qexactly under a 1.

T
is 2 qaccepted. other the 4 DFA is a the On is that, state then, state, final a

b DFA to consideration final any s. DFA are hand, one accepted if remember of if qThus,

U
state, via we all 0 is memory the subsequent ab. occurrence state,
 only. goes to {b those if have x input the the understand and q∈ by 2 the from {a, the

recognizes DFA a strings creating input by the remains contains number DFA b}a second
∣
of explaining q∗ DFA s, goes 1 ab. has ∣ ∣ will to it |x|accepts

W
that units, there; remains That to is only an qthat ab of

occurrence 2 not the = the the a via a, the we s, 1b be is, the all then so set s, trap input

a the demonstrate in accepted. roles then that those input b of qthe and state DFA of 1 all

has only. of the all ab strings DFA has strings remains each at qin will such DFA 4 Here,

Thus, least an and the transits the of reach which strings occurrence over remains

input. its since note language one at the states. to {a, qfrom have 2 a.
that it role will qon
b} in

3,
 o
is a b }GFED@ABC q4

rld
.
44
www.alljntuworld.in JNTU World
Example 4.1.8. Consider the following DFA
GFED@ABC?>=<89:; q0

eeeeeeeee
1. First, observe that the number of occurrences of c s in the input at any state is simply
ignored by the state by remaining in the same state.
2. Whereas, on input a or b, every state will lead the DFA to its next
state as q0 to q1, q1 to q2 and q2 to q0.
3. It can be clearly visualized that, if the total number of a s and b s in the input is a multiple
of 3, then the DFA will be brought back to the initial state q0. Since q0 is the final state those

strings will be accepted.

4. On the other hand, if any string violates the above stated condition, then the DFA will either
be in q1 or be in q2 and hence they will not be accepted. More precisely, if the total number
of a s and b s in the input leaves the remainder 1 or 2, when it is divided by 3, then the DFA
will be in the state q1 or q2, respectively.
Hence the language of the DFA is
∣
{x ∈ {a, b, c}∗ ∣ ∣ |x|a + |x|b ≡ 0 mod 3Downloaded From JNTU World
(http://www.alljntuworld.in) c

c a,b GFED@ABC q2

JN
}. From 1. 2. the above discussion, further we ascertain
the following:
Instead of q0, if q1 is only the final state (as shown in (i), below), then the language will
be

TU ∣
{x ∈ {a, b, c}∗ ∣ ∣ |x|a + |x|b ≡ 1 } mod

3Similarly, instead of q0, if q2 is only the final state (as shown in (ii), below), then the
language will be

∣
W o
{x ∈ {a, b, c}∗ ∣ ∣ |x|a + |x|b ≡ 2 }
 rld }}}} }}}
mod 3 45 a,b }} a,b

GFED@ABC q1
c
www.alljntuworld.in JNTU World
c
c

}}}} }}}
JN
}} a,b We role 1. construct is First, which Clearly, to
 T
{x ∈ {a, b}∗ Downloaded From JNTU World (http://www.alljntuworld.in) a DFA

U W ∣
accepting L. ∣ ∣ |x| ∈ P }. Here,

we need to c GFED@ABC q0
ea,b eeeeeeee GFED@ABC a,b q2

GFED@ABC?>=<89:; q1
GFED@ABC q
0

ea,b eeeeeeee

or
GFED@ABC?>=<89:; a,b q2 c

ld
consider states whose count the number of symbols of the input.
we need to recognize the length 2. That is, first two symbols; for we may consider the
following state transitions.
GFED@ABC q0 a,b GFED@ABC q1 a,b GFED@ABC q2
on any input over {a, b}, we are in the state q2 means that, so far, we have read the portion
of length 2.
}}}} }}}
46 }} a,b GFED@ABC q1
c
c
(i) (ii)
∣
3. In the similar lines, {x ∈ one may {a, b, c}∗ observe ∣ ∣ that the |x|a + |x|b ≡ 1
language }

mod 3=
∣
{x ∈ {a, b, c}∗ ∣ ∣ |x|a + |x|b ≡ 0 or 2 } mod 3can be accepted by the DFA shown below,

by making both q0 and q2 final states.

GFED@ABC?>=<89:; q0
c

c a,b eeeeeeeee GFED@ABC?>=<89:; q2

}}}} }}}
}} a,b
c

GFED@ABC q1

4. Likewise, other combinations of the states, viz. q0 and q1, or q1 and q2, can be made
final states and the languages be observed appropriately.
Example 4.1.9. Consider the language L over {a, b} which contains the strings whose
lengths are from the arithmetic progression
P = {2,5,8,11,...} = {2+3n | n ≥ 0}.
That is,
L=
a,b
www.alljntuworld.in JNTU World
2. Then, the length of rest of the string need to be a multiple of 3. Here, we borrow the idea
from the Example 4.1.8 and consider the following depicted state transitions, further.
GFED@ABC q3GFED@ABC q0 a,b GFED@ABC q1 a,b GFED@ABC?>=<89:; q2 a,b Clearly, this DFA
accepts L.
In general, for any arithmetic progression P = {k k,k ∈ , if we consider the language
 J N
L= Example strings We 1. 2. observe If the state On q1,

T
that we clearly subsequent input to 4.1.10. assume the end some need
 U
following it with is a other, Consider a to ending state a. s the

W
language over Σ Σ

{a, Downloaded From JNTU World (http://www.alljntuworld.in)

 }
o r
} a,b }}}}}}} ee+ eee ekn eee GFED@ABC q| 4 n ≥ 0} with

ld
$ q_^]\ XYZ[ k +k−1 j t Ñ b} consisting of those That is,
∗
{xa | x ∈ {a, b} }.
to construct a DFA for the language.
 q0 as the initial state, then an occurrence of a in be distinguished. This can be done by

changing the say q1. Whereas, we continue to be in q0 on b s.

at q1 let us remain at q1. If a string ends on reaching with an a. By making q1 a final

state, all such strings can be accepted.

∣
47 a,b {x ∈ Σ∗ ∣ ∣ |x| ∈ P}
over an alphabet Σ, then the following DFA can be suggested for L.
qONMLHIJK k +1 u b Q D GFED@ABC q0 Σ GFED@ABC q1 Σ ... Σ GFED@ABC?>=<89:; qk
9
www.alljntuworld.in JNTU World

3. If we encounter a b at q1, then we should go out of q1, as it is a final

state.
4. Since again the possibilities of further occurrences of a s need to cross- checked and q0 is

already taking care of that, we may assign the tran- sition out of q1 on b to q0.
Thus, we have the following DFA which accepts the given language.
a GFED@ABC q0
b
Example 4.1.11. Let us consider the following DFA

J N
Note sibly a next abbaba string states that, zero) is is
 T
given given in number for this as the as type input input, string. of a,

Downloaded From JNTU World (http://www.alljntuworld.in) b

/.-,()*+

U
a a GFED@ABC?>=<89:; q1
World
b

b ?>=<89:; q a, b ?>=<89:;/.-,()*+r
of finite automaton we are considering multiple (pos- transitions for an input symbol in a
state. Thus, if then one may observe that there can be multiple For example, in the above
finite automaton, if then the following two traces can be identified.
?>=<89:; p a ?>=<89:; p b ?>=<89:; p b ?>=<89:; p a ?>=<89:; p b ?>=<89:; p a ?>=<89:; p 48 a b /.-,()*+ a
b
/.-,()*+
b
/.-,()*+
b
a
Unlike the above examples, it is little tricky to ascertain the language ac- cepted by the DFA.
By spending some amount of time, one may possibly report that the language is the set of all
strings over {a, b} with last but one symbol as b.
But for this language, if we consider the following type of finite automa- ton one can easily be
convinced (with an appropriate notion of language acceptance) that the language is so.
?>=<89:; p
www.alljntuworld.in JNTU World
?>=<89:; p a ?>=<89:; p b Clearly, p and r are the next it is reaching to a final state, say that the

string is accepted. acceptance, the language accepted reported as the set of all {strings

xb(a ∣ ∣ ∣ x ∈ (a + b)∗ Thus, the corresponding regular This type of automaton with
deterministic finite automaton. the following section.
4.2 Nondeterministic In contrast to a DFA, where we a state on an input symbol,

J
now terministic (possibly put. finite may (Q,Σ, function is assigns Remark

N
Example be a given Formally, function be A automaton δ, transition a

nondeterministic. q4.2.1. δ by 0,F), zero) set is 4.2.2. transitions. the as of a so

T
next nondeterministic Clearly, where next below: following that, is without

U
Let defined states states, Q,Σ,qfor Q every A δ = a transition :

qqqqinput from δ transition 1 0 2 3 in Q {qgiven possibly 0 Downloaded From JNTU World

(http://www.alljntuworld.in) states the ?>=<89:; + have a p viz. This is with we expression So, b)
state some similar called after by b consider a by is r, concept the unique Finite on
 W
?>=<89:; the additional nondeterministic p in considering as

processing lines an last one finite ε-transition. is a input a next will (a but of finite ?>=<89:; of p
}
+ a automaton Automata features formally one state the symbol . DFA b)the b this

o
automaton ∗ b(a symbol possibilities, ?>=<89:; for string q in A if notion + or

which is a nondeterministic there be b). a without transition can known as abbaba.

 r
introduced ?>=<89:; with r of b, are transitions be language i.e. we as quickly

any nonde- several Since

ld
from non- may

in- in
finite automaton (NFA) is a quintuple J = and F are as in a DFA; whereas, the transition
× (Σ ∪ {ε}) −→ ℘(Q)
state and an input symbol (possibly ε), δ
empty set. DFA can be treated as an NFA. 0,q1,q2,q3,q4},Σ= {a, b}, F = {q1,q3} and δ

table. a b ε {q1} 0 {q4} 0 {q1} {q2} {q2,q3} {q3} 0 0 0 0 q4 {q4} {q3} 0

49
www.alljntuworld.in JNTU World

J
The an present Consider four Note the possible in εab, that, states
 N
Definition x computed (iii) (iv) (ii) = (i) trace 1. 2. 3. NFA Note string

GFED@ABC GFED@ABC GFED@ABC

aquintuple as are 1athat There There There if
GFED@ABC qqqq
is it 2 0 0 0 0 NFA we (ii) insertion the can {qthe ···aGFED@ABC the is qusing
v
ab. three 1,q0 process a a a ε 4.2.3. defined. we is are is possible be following traces k can

v v
T v
2,q a no That J GFED@ABC GFED@ABC GFED@ABC GFED@ABC and have
 v v v v v
qqqqrepresented multiple transition a distinct 1 4 1 1 3}. be transition of = tree Let a the
v v v v
for ε ε means, included represented (Q,Σ, Whereas, a ε b b a traces. state in few J
v
structure, the input GFED@ABC GFED@ABC GFED@ABC GFED@ABC

v
U v v v
ab, qqqq (two) states, 1 4 2 1 = p nondeterministic from δ,

v v
string wherever by while from of (Q,Σ, qvan GFED@ABC?>=<89:; GFED@ABC ε string b b 0,F)

in qqJ transitions a 1 4 qviz. GFED@ABC GFED@ABC GFED@ABC as ε-transition state 0

trace qab called hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh qqq, tracing 0 3 3

2 to b a the δ, is follows: on ab from qqε-transitions qan 0,F) 1,q4 transition set (iii) input at
W
a without NFA. 2 ε the a computation of the from and be we path

transitions next from symbol state an state In consider qq3 any 2 NFA. diagram. from the

states qGFED@ABC are on are qq0 qb 0. 2 to input, 0, b. similar input reachable defined.

o
Clearly, qGiven tree in a then qab 0 δ(p, ˆ4, for this as For considering of
 ˆ
i.e. symbol x) lines the ab an aεb. a,b δ(p, NFA. For the instance, can ε-transition. we

r
input from set of It x), following example, be a. consider a of is qwhich string

easily DFA,

ld
ab GFED@ABC?>=<89:; 0 clear next qthe
via 3

as
is defined in the following way:
50 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
1. p is the root node
2. Children of the root are precisely those nodes which are having transi-
tions from p via ε or a1.

3. For any node, whose branch (from the root) is labeled a1a2 ···ai (as a resultant string by

possible insertions of ε), its children are precisely those nodes having transitions via ε or ai+1.
4. If there is a final state whose branch from the root is labeled x (as a
resultant string), then mark the node by a tick mark /.
5. If the label of the branch of a leaf node is not the full string x, i.e. some proper prefix of x,
then it is marked by a cross X – indicating that the branch has reached to a dead-end before
completely processing the string x.
ˆ
Example 4.2.4. The computation tree of δ(q 0, ab) in the NFA given in Example 4.2.2 is
shown in Figure 4.2
q

J N
q
q Example Example qfurther processing end 0 − of q4
 T
the − transitions q4.2.2 4 branch. the 4.2.5. − q string is 3 Downloaded From

JNTU World (http://www.alljntuworld.in)

U
q q q qq q Figure The shown has at 4.2: Computation

computation in Figure the label ab, q3, the branch abb. Thus, it a
World
ˆ
Tree of δ(q 0, ab)
ˆ
tree of δ(q 0, abb) in the NFA given in 4.3. In which, notice that the branch as a resultant

string, and as there are no has got terminated without completely is indicated by
marking a cross X at the 51 0 ε
1 4b ε a1 2 4ε bb 2 3 3
www.alljntuworld.in JNTU World
 J
is possibly the q4 cannot at εap, an Definition the Example the E(qas

N
processed 1εaand we qNFA, As Thus, Further, 0) only 0 set NFA

2ε···εais find = the then of be empty. {qpossible empty. we given all given the processed
 T
automaton 4.2.7. 0,qfrom at 4.2.6. for first nε states 4};E(qset a in a and

For ε Figure a state, q q way qintroduce set 2 In Example 1 of 4 string An to that by example,

1) the next further. A to b given qthen = ε-closure 3 looking of 4.3: process

U
following are via {qx states states, q 1
the 4.2.2. 1,qthere in = Computation reachable b. Hence, if 2};E(qExample As b at notion

awe the ε for 1aof ε-closure may the we there 2 apply q q a q first p ···a2 31 b the 2) enlist state

W
via possible called from be = are 4.2.2 n b a set the x. multiple ε

is {qTree and of p, the no p going of 2};E(qTo ε-closure q q q

A, string via is denoted 2 3 0

bcomplete transitions next a of ε-closures nondeterministic, introduce denoted zero state

 ˆ
o
δ(qvia next 3) ε bba states 0, ε-transition = or of by abb) qqq states p, at

branches 4{q4ab 3 a more by from E(p) of the 3};E(qthe for by state. E(A) all (unlike the

r
notion treating state ε-transitions. qis the 3, 4) starting defined from if string the

is states = qa defined 0, of DFA), string

 ˆ
ld
string {qqx then δ 0 4}. bba

to

as at
as in
of
⋃E(p).
E(A) = p∈ A52 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Now we are ready to formally define the set of next states for a state via a string.
Definition 4.2.8. Define the function

δ ˆ: Q × Σ∗ −→ ℘(Q)
by1. δ(q,ε) ˆ= E(q) and
ˆ
2. δ(q, xa) = EDownloaded From JNTU World (http://www.alljntuworld.in)
(⋃

ˆ) δ(p, a)
p∈ δ(q,x) Definition 4.2.9. A string x ∈ Σ∗ is said to be accepted by an NFA J = (Q,Σ, δ,

q0,F), if δ(qˆ0,x) ∩ F = 0. That is, in the computation tree of (q0,x) there should be final

state among the nodes marked with /. Thus, the language accepted by J is
L(J ) =
 JN
Example in Example 1. 2. The of The (a) strings

possible are 4.2.10. Via from strings of 4.2.2.

T
string two the represented q0, of possible ways Note state in then a∗ this
 U
(a that of qusing + 1: case reaching ways b) by {With qx 1 will

∣
the the can ∈ and of Σthe lead regular reaching ε-transition ∗ be qq ∣ ∣ 1 3 δ(qˆstrings

W
from are represented us 0,x) from expression the the q3 ∩ of

final from F state we initial ab= ∗ by states can qwe 00 qabab2 }state as
 o
∗
reach can . to ∗ . adiscussed for ∗ q(a 3. qclearly 0 the + qThus, is 2.

r ld
b). NFA via Then reach below. the the given the

set

set q1
(b) Via the state q4: Initially, we use ε-transition to reach q4 from q0, then clearly the

strings of a∗ b will precisely be useful to reach from q4 to q3. And hence ab∗ itself

represent the set of strings in this case.

Thus, the language accepted by the NFA can be represented by the following regular
expression:
ab∗ + a∗ b + ab∗ a∗ (a + b)
53
www.alljntuworld.in JNTU World
Example 4.2.11. Consider the following NFA.

J
Hence, 4.3 Two same appears accept converse, through Lemma exists
 N
Proof. some given and automaton 1. 2. 3. Since F finite From from the

qAlso, to Thus, from ε-transitions. language, by an 0 the Let the = to the more

Equivalence the 4.3.1. equivalent above every given automata same F aεbthe

T
qlanguage J without note the 0. any final following ∪ general ∗ set b, initial

= {q DFA two i.e. an Given that string class state i.e. (Q,Σ, (a δ ∈ Set NFA ε-transitions.
 NFA L(s sets. (q,a) accepted + s can abthe Q state of two with qan accepted GFED@ABC

U
abJ +2. qand languages. | δ, ) , 0 without +That strings there be

ˆ
= E(q) lemmas. NFA or q= )qa 0,F) = ∗ 0 δ(q,a) a s of treated L(s via lot followed one by

(Q,Σ,δ (a is, ∩ a exists in are by of of a the be NFA ε-transitions. + F can the ). which

string flexibility, ababthe said a = GFED@ABC for NFA as In ∗ qreach strings +,qby b an

W
finite 1 )will 0}. 0,F NFA an ∗ all the to there aba which equivalent
 and can string ∗ a NFA, lead be back present ), automaton It ε of ∈ can we where be
are equivalent Σ, is (a is us to prove from DFA represented one be clear a
+
GFED@ABC?>=<89:; + some q qfrom qmixture context, 2 ∈ ab0 DFA, δ of side via Q the :

o
∗
b that that the )in ε-transitions, Q the if strings will set × is which is they

form NFA of J initial although Σ obvious. by being ablead strings −→ ∗ accept from – . is

r
and there a state us ℘(Q) a proved string
finite there aDFA NFA from from

ld
The ∗ the

are or
qis 0

54 Downloaded From JNTU World (http://www.alljntuworld.in)

www.alljntuworld.in JNTU World
We claim that L(J ) = L(J ). First note that
ˆ
ε ∈ L(J ) ⇐⇒ δ(q 0,ε) ∩ F = 0

⇐⇒ E(q0) ∩ F = 0 ⇐⇒ q0 ∈ F ⇐⇒ ε ∈ L(J ).
Now, L(J Downloaded From JNTU World (http://www.alljntuworld.in) for any x ∈ ). This is because,
ˆ ˆ
Σ+, we if δ prove (q0,x) that = δ(qˆδ (q0,x), 0,x) then

= δ(qˆ0,x) so that L(J ) =

ˆ ˆ ˆ
x ∈ L(J ) ⇐⇒ δ(q 0,x) ∩ F = 0 ⇐⇒ δ (q0,x) ∩ F = 0 =⇒ δ (q0,x) ∩ F = 0 ⇐⇒ x ∈ L(J ).

Thus, we This δ(qˆare Conversely, implies L(J through. ) that ⊆ let L(J Otherwise, q x ∈ ∈
δ(q).
ˆ ˆ ˆ
L(J 0,x) there ), and i.e. exists E(q)∩F δ (q0,x)∩F q ∈ = δ (q0. = 0,x) Which 0. such If

δ ˆ(qin that 0,x)∩F turn E(q)∩F implies = 0 = then that 0. 0,x) ∩ F So, it is = enough 0.
 ˆ
That to prove is, x ∈ that L(J δ ). (q0,x) Hence = L(J δ(qˆ) = L(J ).

0,x) for each x ∈ Σ+. We prove this by induction on |x|. If x ∈ Σ, then by definition of δ we
have

δ ˆ(q0,x) = δ (q0,x) = δ(qˆ0,x).

Assume the result for all strings of length less than or equal to m. For a ∈ Σ, let |xa| = m + 1.
Since |x| = m, by inductive hypothesis,

δ ˆ(q0,x) = δ(qˆ0,x).
Now
⋃
δ ˆ(q0, xa) = = δ (

JN
δ ˆ(q0,x),a) p∈ δ ˆ(q0,x) Hence by induction
TU
we have δ (q0,x) = = δ (p, a)

W ˆ
ˆ
p∈ δ(q 0,x) δ(p, ˆδ(q 0, xa). = δ(qˆ0,x)
orld
a)

∀ x ∈ Σ+. This completes the proof.

55
www.alljntuworld.in JNTU World
Lemma 4.3.2. For every NFA J without ε-transitions, there exists a DFA s such that L(J ) =
L(s ).
Proof. Let J = (Q,Σ,δ ,q0,F ) be an NFA without ε-transitions. Con- struct s = (P,Σ, μ,

p0,E), where
P=
}
{ p{i1,...,ik} ∈ P | {qi1,...,qik} ∩ F = 0, and

μ : P × Σ −→ P defined by μ(p{i1,...,ik},a) = p{j1,...,jm} if and only if ⋃ il∈ {i1,...,ik}Downloaded From

JNTU World (http://www.alljntuworld.in)
δ (q
il,a) = {qj1,...,qjm}.
Clearly, s is a DFA. To show L(J ) = L(s ), we prove that, for all x ∈ Σ∗ ,
ˆ
ˆμ(p0,x) = p{i1,...,ik} if and only if δ (q0,x) = {qi1,...,qik}. (⋆ )
This suffices the result, because
ˆ
x ∈ L(J ) ⇐⇒ δ (q0,x) ∩ F = 0
 ˆ
⇐⇒ ˆμ(p0,x) ∈ E ⇐⇒ x ∈ L(s ). Now, we If |x| = 0 prove then the δ (qstatement 0,x) {p{i1,...,ik}

| {qi1,...,qp0 = p{0}, E =

J N
statement the than By Now μ(p Assume {iinductive

statement 1,...,iby or ˆμ equal definition k},a) (pin 0,x) that (⋆ ) hypothesis, = to directly

T
= pholds n. the {jof p1,...,jLet {iμ, 1,...,istatement in follows m} x
U
kˆμ(pthis } ∈ if = in (⋆ ) by induction on the length {q0}, also

}
W
ˆμ(p0,x) = p0 = p{0} ik} ⊆ Q, case. (In case x = 1 also, from the

definition of is true for the strings Σ∗ with |x| = n and a ∈ 0, xa) = μ(ˆμ(p0,x),a).
 ˆ δ (q
or
if and only if δ (q0,x) and only if ⋃ μ.) Σ. = {q il of x. so that

one may notice whose length is Then

ld
i1,...,qik}. ,a) = {qj1,...,q the that

less
jm}. il∈ {i1,...,ik}56
www.alljntuworld.in JNTU World
Thus,
ˆμ(p0, xa) = p{j1,...,jm} if and only if δ ˆ(q0, xa) = {qj1,...,qjm}.
Hence, by induction, the statement in (⋆ ) is true.
Thus, we have the following theorem.
Theorem 4.3.3. For every NFA there exists an equivalent DFA.
We illustrate the constructions for Lemma 4.3.1 and Lemma 4.3.2 through the following
example.
Example 4.3.4. Consider the following NFA
GFED@ABC q0

J
Downloaded From JNTU World (http://www.alljntuworld.in) a, That In we is Thus,
 N
there consider μ given order need is, (Q in the to to = the calculate

T ˆ
remove transition {q following 0,q1,qε-transitions δ(q,a), 2},{a, function,
U d d d ˆ dd
table. qqqδ 0 1 2 δ b},δ qqqfor = {q 012 00a bδ 1
} all say

d dd d d d dd
,q ε and {q{q0,{q states {q{q0 a δ, 1} 1} 0,q1,qobtain 0 dGFED@ABC?>=<89:; b can

W ~ ~ ~ ~ ~
0,qε, q2 {q1} 2} bq ~2}) {q 0,qbe and 1,q {q0 an b 1,qis

~~
displayed 1,q2} b
 ~ ~ ~~ ~~
o
0 0 ε for an equivalent 2} 2} all equivalent input as b the finite

r
symbols following NFA automaton, in a. which table
 ld
That

are no ε-transitions. Now, to convert this to an equivalent DFA, we each subset of Q as a

state in the DFA and its transition function assigns the union of respective transitions at
each state of the above NFA 57 GFED@ABC q1
www.alljntuworld.in JNTU World

J
which are in the subset under consideration. That is, for any input symbol a
 Thus wherethe J that, are them. not n 4.3.1 We to transitions symbol. and states

N
. its P E the It In either alter demonstrate number In among the is = =

the a equivalent If transition fact, observed subset {to That the there Heuristics resultant
pfollowing inaccessible Xan is of ∣ ∣ ∣ if these language, ∣ ∣ ∣ clearly X equivalent J X

T
is, states X is ∩ certain that ⊆ map DFA. a of for has {0,2} 2DFA we
 {0,1,2}n procedure {0,1,2} because of a states, from while n provide μ then state

U
Nondeterminism to s states, is heuristics is = DFA μ(pthe given

0phas }(P,{a, converting Convert we ppp{0,1,2} pppsome (the }, {0,1} {1,2} {0,2} q pof X,a) {0} {1}

{2} μ certain ∅ to ; with initial may and s an in multiple in remove index b}, fact will of to =

exponential the ppppppnumber an get pp{1} {1} {1} {1} {1} {1} a state the i∈ X ∅ ∅ convert μ,

W
heuristics ⋃an have there input following a set pNFA δ {0},E)
 transitions states ppppsome in NFA DFA pp{0,1,2} {0,1,2} {0,1,2}

{0,1,2} (qor {1,2} {1,2} ppof b of 2∅ ∅ i,a). a are no n symbol an the states finite J with states. of

growth to to are final six NFA table: the states) convert to DFA dead states lesser at

o
automaton state less an a, dead without It compared a if equivalent – may

than state a number is δ(q,a) in the states given accessible E, also 2ε-transitions states for

r
n
and without . = to NFA which of be an DFA P that states. which noted
input from
with

ld
with

s do of
ε- ,
|P| = 0 or |P| > 1, then such a situation need to be handled to avoid
58 Downloaded From JNTU World (http://www.alljntuworld.in) {pX
www.alljntuworld.in JNTU World
nondeterminism at q. To do this, we propose the following techniques and illustrate them
through examples.
Case 1: |P| = 0. In this case, there is no transition from q on a. We create a new (trap) state t
and give transition from q to t via a. For all input symbols, the transitions from t will be assigned
to itself. For all such nondeterministic transitions in the finite automaton, creating only one
new trap state will be sufficient.
Case 2: |P| > 1. Let P = {p1,p2,...,pk}. If q /∈ P, then choose a new state p and assign a

transition from q to p via a. Now all the transitions from p1,p2,...,pk are assigned to p. This
avoids nondeterminism at q; but, there may be an occurrence of nondeter- minism on the
new state p. One may successively apply this heuristic to avoid nondeterminism further.
If q ∈ P, then the heuristic mentioned above can be applied for all the transitions except for
the one reaching to q, i.e. first remove q from P and work as mentioned above. When there
is no other loop at q, the resultant scenario with the transition from q to q is depicted as under:
 JN T
a ?>=<89:; qa This may be replaced by

U
the ?>=<89:; following q a a,b

Downloaded From JNTU World (http://www.alljntuworld.in)

 W
type ?>=<89:; p

?>=<89:; p
of transition:

orld
59 a In case there is another loop at q, say with the input symbol b, then scenario will be as
under:
a,b

?>=<89:; q a
?>=<89:; p
And in which case, to avoid the nondeterminism at q, we suggest the equiv- alent transitions
as shown below:
b
a ?>=<89:; q
a ?>=<89:; p
b We illustrate these heuristics in the following examples. Example 4.3.5. For the language
over {a, b} which contains all those strings starting with ba, it is easy to construct an NFA as
given below.
?>=<89:; p b ?>=<89:; q a ?>=<89:;/.-,()*+r
www.alljntuworld.in JNTU World
Clearly, the language accepted by the above NFA is {bax | x ∈ a, b∗ }. Now, by applying the
heuristics one may propose the following DFA for language.
a,b
?>=<89:; p
a aa aaaa
a aa?>=<89:; t
ÑÑÑÑ ÑÑÑ
b ÑÑ b

?>=<89:; q

a ?>=<89:;/.-,()*+ r
a,b Example 4.3.6. One can construct the following {anxbm | x = baa, n ≥ 1 and m ≥ 0}.
a

/.-,()*+ a /.-,()*+ b /.-,()*+ a By applying the heuristics, /.-,()*+ a

 JNT U
a the /.-,()*+

W
following DFA can /.-,()*+ be NFA constructed a
o
for /.-,()*+ the b

r ld
b the language same

easily.
rrrr r rrrrrr
b /.-,()*+ /.-,()*+ b riiiiiiiiiiiiiiiiiiiiiii b a /.-,()*+ a a,b Example 4.3.7. We consider the following
∗
NFA, which accepts the language {x ∈ {a, b} | bb is a substring of x}.
?>=<89:; p
a,b
60 Downloaded From JNTU World (http://www.alljntuworld.in) a /.-,()*+
a,b
a,b

b ?>=<89:; q b ?>=<89:;/.-,()*+r
By applying a heuristic discussed in Case 2, as shown in the following finite automaton, we
can remove nondeterminism at p, whereas we get nondeter- minism at q, as a result.a
b
a,b

?>=<89:; p

b ?>=<89:; q
a To eliminate the nondeterminism at q, we further apply the same technique and get the
following DFA.
?>=<89:; p

b ?>=<89:;/.-,()*+ r
a

b ?>=<89:; q
a

b ?>=<89:;/.-,()*+ r
www.alljntuworld.in JNTU World
Example 4.3.8. Consider the language L over {a, b} containing those strings x with the
property that either x starts with aa and ends with b, or x starts with ab and ends with a. That
is,
L = {aaxb | x ∈ {a, b}∗ }∪ {abya | y ∈ {a, b}∗ }.
An NFA shown below can easily be constructed for the language L.
 J N
a,b 4.4 In to tion characterization 4.4.1 We this an

start is equivalent section obtained Minimization with Myhill-Nerode the

T v
we of through DFA provide following the /.-,()*+ with languages r
U vv v v v vv
r r well-known r an r a a r minimum basic r r algorithmic

v v
r Theorem r rv of rv/.-,()*+ /.-,()*+ accepted concepts. DFA Myhill-Nerode number a b

W o
procedure by /.-,()*+ DFA. of b states. b /.-,()*+

to convert In theorem Downloaded From JNTU World (http://www.alljntuworld.in)

rld
a given DFA fact, this asser- which gives a 61 /.-,()*+
a /.-,()*+
a,b

By applying the heuristics on this NFA, the following DFA can be obtained, which accepts L.
/.-,()*+
b
a
a /.-,()*+
b
a

b /.-,()*+

a /.-,()*+
v vvvv vvvvv r
r r r r r b r r r r r rv va,b /.-,()*+
/.-,()*+
/.-,()*+
a
b
a
www.alljntuworld.in JNTU World
Definition 4.4.1. An equivalence relation ∼ on Σ∗ is said to be right in- variant Example by
 J
It For That write xzw Example on Clearly, δ(qˆso Theorem following Proof.

N
∗
First, index. 1. 2. 3. is that 0,y). Σx, ∈ straightforward L There ΣThe is,

u we y by L For (1) ∗ xz if, is ∼∈ = Now, we such ⇐⇒ observe three s equivalence accepted

∗
for 4.4.3. 4.4.2. ∼ 4.4.4 Σ⇒ x zw. have exists is s∈ yzw (2): x, that assume x for an
T
yz. statements Σ∼ y ∗ (Myhill-Nerode Now, x to equivalence that Let , Let

ˆ
any L ∈ a ∈ L Hence, Assume if ∼ by y show right ΣL. s is δ(q to s L relation ∗ z x a the if ,

U
since y the ∈ Hence be 0,x) DFA. ∼ observe δ(qand =

ˆinvariant that x if Σright L ∼ regarding a (Q,Σ, union L 0, ∗ ∼ and s y. , = language x only

 relation xz) is y ∼ is ∼ (∀ w)p, Let ∼ invariant L =⇒ accepted only Theorem). L that a L δ, of
(
then if is is right = = = qequivalence z y, L some 0,F) ∀ z(xz of a ∀ z(xz xzw if on ∈

ˆˆ
W
∼ over δ(δ(δ(qare ˆ we right the finite L Σinvariant

ˆ
δ(qˆΣδ(qδ(qˆ equivalence 0,yz) ∗ be ∈ by is ∗ the have equivalent: equivalence ∼ . 0,x) Σ.

∈ be 0,x),z) 0,y),z) Let L invariant an Suppose a index. the yz). L equivalence ⇐⇒

Define arbitrary. DFA. relation L ⇐⇒ equivalence xu = DFA equivalence be δ(qˆyzw ∈
 o
a yz Define relation 0,y). x the equivalence language L s class ∼ ∈ ∼∈

)
s ⇐⇒ Claim: relation classes L). = of Ly, the relation containing (Q,Σ, finite ∼ . relation.

r
i.e. yu s For over relation xz of is on ∼ δ(qˆ∈ index δ, w L of ∼ . Σ. ∼ on 0,x) ΣL,

qon ∈ 0,F). L finite ∗ x .

 ld
The ∼ ΣΣ yz.

i.e. Σon = s ∗ ∗ ∗ .
,
ˆ
[x]∼A = {y ∈ Σ∗ | δ(q 0,y) = p}.
62 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
That is, given q ∈ Q, the set
Cq = {x ∈ Σ∗ | δ(qˆ0,x) = q}

is an equivalence class (possibly empty, whenever q is not reachable from q0) of ∼s. Thus,

the equivalence classes of ∼ s are completely determined by the states of s ; moreover,

the number of equivalence classes of ∼ s is less than or equal to the number of states of s .

Hence, ∼ s is of finite index. Now,

⋃ ∗ ˆ
L = = {x ∈ Σ | δ(q 0,x) ∈ F} p∈ Fas desired. (2) ⇒ We show classes of ∼ . For x, ∀ z(xz ∈ L
 JN
z, i.e. xz some of the Thus, ∼ L by Q setting (3) = Σ⇒

∗
/Downloaded From JNTU World (http://www.alljntuworld.in) (1): that is ∼ (3): y and ⇐⇒ L

T
equivalence ∈ of is Assume Σyz finite Suppose ∼ yz ∗ less , is are ∈

suppose a index.
 U
than L). in refinement ∼∼ classes L= same Since ∀ z(xz or is is

⋃ {x ∈
x sp∈ F of an equal L ∼ equivalence ∼ = of finite C∈ equivalence y. is p. (Q,Σ, of ∼, L

Σ
W
to To right ⇐⇒ ∼ we index. L ∗ the show δ, | have so invariant,

ˆ
yz δ(q qnumber class 0,F) that Construct ∈ with 0,x) x L). ∼ of the L = the ∼ . y, of we p}
 o
number we criterion equivalence As have have L ∼L =

∣ ∣ ∣ x ∈ L}
and

rld
given in (2). of equivalence classes of to show that xz ∼ yz, for all is the union of
 }
∣ ∣ ∣ { [x]

x ∈ Σ∗ , the set of all equivalence classes of Σ∗ with respect to ∼ L,

q0 = [ε], {F =

[x] ∈ Q
δ : Q × Σ −→ Q is defined by δ([x],a)=[xa], for all [x] ∈ Q and a ∈ Σ.
63
www.alljntuworld.in JNTU World

J
Since so fact, this induction by This Remark states and equal Example We
 N
a Thus, say will and that 1. 2. 3. definition For – – calculate [ε],[a] be

the serves we completes The Any stance, Also, In If ∼ to ab of the in inductive L δ ab – show

proof case 4.4.5. the any are is is one on string 4.4.6. string strings For and is a of the well-

defined. index [x]=[y] not not of εb |w|. ab the and DFA finite δ(qˆthat of of n

T
Note [ab], the purpose δ, = is b ≥ these 0, equivalent a which (3) step,
 Consider equivalence ab distinguishes Induction ε, we b a of xa) substring 1, accepting

index, proof. /∈ respectively. substring that, are a ⇒ ∼ =⇒ have x L, equivalence consider

U
and L. = does (1) = = = not because whereas Hence δ(qˆx

ˆ
Hence, aQ the the δ(q nab provides δ(δ([x],a) [xa]. to ∼ 0,w)=[w], : basis equivalent is of
not classes L L 0,a) δ(qˆIn language of proof will each a the x, x y sis finite 0,x),a) this x,

contain w =⇒ s∈ L abb Now, is then greater = classes. pair be L clearly is Σother, ∈ (by of

clear, of us δ([ε],a)=[εa]=[a], is case, ∗ ∈ xa a set; in L and (2) ∼ we because, L ε a L. we

 W
DFA. the inductive ∼ L. three and ∀ w ⇐⇒ ab minimum = than

further, because because discuss L ⇒ x x show a First DFA {x distinguishes ya will ∈ will ∈
a: We (3) [w] Σdifferent ∈ Σ. or =⇒ εb aa ∗ that be be {a, observe s; shows claim
ˆ
hypothesis) in for equal of ∈ Now = δ(q L /∈ state [xa]=[ya] in in b}the b the with F. [x],[y]

o
L, any 0,ε) [a]. ∗ /∈ [ab]. that equivalence that | to whereas following L,
DFA following. ab that We for ε other = number the whereas and ∈ is L(sqthe all prove 0

r
the Q accepting a index = a ab. x substring and L) aba number [ε]. ∈ strings

subcases. ∈ of = ab this classes, Σ. For {a, a ∈ of states L. Also, ∈ ∈ L.

ld
b} ∼ L.
in- by Σ,

L. In
of

ε, L
of ∗ x}.
– In case x = bn, for some n ≥ 1, x will be in [ε].
64 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
– If x has some a’s and some b’s, then x must be of the form bnam,

J
Thus, By Example {a, theorem, {a, bThus, Hence, 4.4.2 Given that said

final in only number and a minimum. Definition denoted either two all in technique Definition
 N
k-equivalent, n DFA. language ∈ the strings b}. b}Clearly, Myhill-Nerode

states to present {a, one their states ∗ ∼for , final a following, have We the for L b}states

DFA, In by state there Algorithmic each has to ∗ 4.4.7. in roles for p show m index ,

states fact, for ≡ 4.4.8. p same acceptance. 4.4.9. and an we test Σdenoted = exactly n, ≡

T
there n, is can without ∗ every exists . algorithmic have in n. m that q, q, we
we there an Consider of the role, This or theorem, the Two be ≥ For They to if ∼ may
introduce equivalence non-final obtain equivalence the input 1. three L no for by considered

U
test aif is has language k affecting nis states In it Among bp

DFA are ≥ practically be index all n not the will whether ≡ to Procedure this kequivalence

∈ 0, string; there procedure an certain not x q, be L, finite. two states. language p accepting
lead a ∈ of case, equivalent if and one acceptance such the notion equivalent relation of
and Σwhereas for exists ∼ states so ∗ us p L states states q difficult, equivalence language. x
 W
both ≡ all group is others that to of to will classes L q called not

a x either a L. p on we = minimize DFA for ∈ via which DFA the and DFA they abe with

finite. {aof are For mΣcan need the since b∗ k-equivalence. and nk-equivalence in states n
states, both Minimization q Now, accepting bwith s same. contribute n instance, classes

/∈ whose respect be set of are [a]. to | hence Hence, L. are Σn a the final discarded of

o
check ∗ redundant |x| we ≥ δ(p, DFA whose said is Here, states to number
1} number ≤ to formulate an it states x) L. by consider accommodate over k s the is to ∼ in

infinite and both and roles L, Myhill-Nerode of two be are same of to condition the or finite

r
because, in of of equivalent, s reduce build δ(q,x) said states both the are the

alphabet this states astates . set. manner n,aindex.

Given

ld
states same, to sense up non- idea m the are
are
So, afor
for
be of n∈
is
a.
δ(p, x) and δ(q,x) are either final states or non-final states.
65 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

J
there easily of Remark Also, provides Theorem Proof. k both that either both
 N
p Remark equivalent Theorem Proof. it ≡ and is 0Q Clearly, Given

Conversely, q enough for under are are the for we test final a If Suppose x ∈ 4.4.10. p us
4.4.12. only either any p have a states ∈ k+1the if Σ 4.4.11. k+14.4.13. ≡ k-equivalence states

T
the ≡ ≡ a kΣto δ(p, be k criterion ∗ finitely q is k-equivalence q p prove with

∏ =
for ≥ relation final For then also k+1δ(p, Two arbitrary. if p a) ≡ 1 or k ≡ k and For If ≡ and
 ∏ ∏
q. any k|x| states y) non-final an ≥ q that man p k-equivalent δ(q,a) to ≡ p 0, only ≤ any

U =
k
and if ≡ k equivalence p, k+1p, relation calculate q k+1and

. ∏ To ∏
suppose k strings q ≡ by p q or Then holds and k ∈ ∈ if δ(q,y) between k+1∀ a ≡
prove ,
non-final ≥ q Q, states, k+1only Q, p , a ∈ 0 =⇒ whereas (cf. ≡ of over since q if 0∈
for
and Σ, p the states if p are length q =⇒ relation Σ, ≡ 0p the ≡ i.e. Remark i.e. and kthe p

some that,
W
n
p, (k p q δ(δ(p, states, ≡ final q, ≡ p kq k+1and states.
 for k
for from ≡ set it + p then q up ∈ q δ(p, k+2≡ is 1)-equivalence on and q, all Q, for of or
≥∏ ∏ p, 0,
a),x) δ(p, ∀ n to 4.4.10). so a) q. states, δ(δ(p, the p y non-final k all k Let ≥ kq
k−1 q kunder we then ∈ Q, can
that a) ≡ ∈ ≡ over and 0 will set Σδ(q,a) ≡ k us kq. a),x) ∗

o ∏the
Let δ(p, ≥ the an of δ(q,a) δ(δ(q,a),x) and denote further 0. states

obtain = relation ∏
alphabet, states. following x a) k relation. ∀ a and 1 ∈ ≡ k≤ ∀ a Σ∈ the
δ(q,a). of ∗ be |y| δ(δ(q,a),x) Σ.
 ∏
r .
.∈ with But s partition ≤ both (k one Σ. theorem k+1. ≡. kk + Since |x| since

ld
Note may + are

1)- ≤
1,
66 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Now,
p k+1≡ q =⇒ δ(p, a) ≡ kδ(q,a) ∀ a ∈ Σ
=⇒ δ(p, a) k+1≡ δ(q,a) ∀ a ∈ Σ =⇒ p k+2≡ q
Hence the result follows by induction.
∏
Using the above results, we illustrate calculating the partition for the following DFA.
Example 4.4.14. Consider the DFA given in following transition table.
δ a b → q0 q3 q2 q1 q6 q2 q2 q8 q5 07162534 q3 q0 q1 07162534 q4 q2 q5 q5 q4 q3 07162534 q6 q1 q0

q7 q4 q6 07162534 q8 q2 q7 q9 q7 q10 q10 q5 q9

From δ(q,x) δ(p, ˆˆDownloaded From JNTU World (http://www.alljntuworld.in) the definition, ε) and

J N
are either δ(q,ε) ˆ and all classes and non-final Thus,

∏From q q, 0 are will =

 T
in the {under the either {qfurther states 0,qTheorem partition the 1,qfinal

final are are be 2,qequivalence two states 1-equivalent states either 5,qequivalent.

∏
U as given
4.4.11, 7,qstates 0 δ(p, or 9,qor final a) we non-final

below:
10},{qnon-final relation p ≡ 0states and Hence, q ≡, or states. are states, 0there
 non-final all 0-equivalent final are for precisely all states states. |x| if = are both 0. two
ˆ
That equivalent That equivalence δ(p, is, is, x) both both and and p

W
} 3,q4,q6,q8}know that any two if

δ(q,a) ∀ a ∈ Σ.

orld
0-equivalent states, p
67
www.alljntuworld.in JNTU World
Using states Downloaded From JNTU World (http://www.alljntuworld.in) this whether condition they
∏ by checking every two 0-equivalent
are we can further evaluate 1-equivalent 1 or not. If
they are 1-equivalent they continue to be in the same equivalence class. Otherwise, they
∏:
will be put in of different 1

equivalence classes. The following shall illustrate the computation

1. Consider the 0-equivalent states q0 and q1 and observe that

(i) δ(q∏00,a) ; = q3 and also and δ(q1,a) = q6 are in the (ii) δ(q∏00,b) . = q2 and δ(q1,b) =

JN ∏
q2 are in the 2. Thus, in In observe (i) contrast 1

also.
δ(qsame q
0
 T
2,a) that ≡ 1equivalence qto 1 and so the that δ(qabove,

U
5,a) they class consider are, will of respectively, continue
∏.
W
0 the 0-equivalent to be same equivalence same in same

o r
states equivalence equivalence q2 { class class class
 ld
of of and q5 and

} {q0,q1,q2},{q5,q7},{q9,q10},{q3,q6},{q4,q8}68 q8 and q4; which are in the (ii) Whereas,

∏ .
lences δ(q2,b) classes of =0

q5 and δ(q5,b) = q3 are in different equiva-

∏ .
Hence, q2 equivalence and q5 classes are of not 1

1-equivalent. So, they will be in different

3. Further, as illustrated above, one may verify whether are not q2

≡ 1q7 and realize that q2 and q7 are not 1-equivalent. While putting q7 in a different class
that of q2, we check for q5

≡ 1q7 to decide to put q5 and q7 in the same equivalence class or not. they will be put in
∏ .
the same equivalence As of q5 1and

q7 are 1-equivalent,
Since, we are any two states which are not k-equivalent cannot be check for those pairs
belonging to same equivalence of further 1-equivalent. Thus, we obtain
∏ whether they
(k+1)-equivalent, 0

∏1 =
{} {q0,q1,q2},{q5,q7},{q9,q10},{q3,q4,q6,q8}Similarly, ∏2 =
∏ , ∏ , etc.
we continue to compute 2 3

www.alljntuworld.in JNTU World

∏{∏3 4 Downloaded From JNTU World (http://www.alljntuworld.in) =
=
} {{q0,q1},{q2},{q5,q7},{q9,q10},{q3,q6},{q4,q8}}
∏ = ∏
{q0,q1},{q2},{q5,q7},{q9,q10},{q3,q6},{q4,q8}and of Note get states that and k the in the
, for some k. This is because, there
k+1process worst for a DFA will always terminate at a
are finite number
case equivalences may end up with finite stage singletons. Thereafter In
∏ =
to ≡. no the present Now we further construct context, refinement a DFA 3 with is
∏
possible.
. Thus it is partition ∏
4 these equivalence corresponding classes as states (by renaming
them, for simplicity) and with the induced transitions. Thus we have an equivalent DFA with
fewer number of states that of the given DFA. The DFA with the equivalences classes as
states is constructed below: Let P = {p1,...,p6}, where p1 = {q0,q1}, p2 = {q2}, p3 = {q5,q7},

p4 = {q9,q10}, p5 = {q3,q6}, p6 = {q4,q8}. As p1 contains the initial state q0 of the given

DFA, p1 will be the initial state. Since p5 and p6 contain the final states of the given
DFA, these two will form the set of final states. The induced transition function δ is given in
the following table.
δab
J N
Here, also with in Theorem fact, The be minimum note

T
is removed following having that 4.4.15. number the and minimum
 U
theorem For state the a,b every of pfollowing GFED@ABC

GFED@ABC?>=<89:; confirms 4 states. ppnumber is 1 5 a DFA inaccessible → 07162534

W
07162534 ppb pppps 5 6 that further 1 2 3 4 of , ppppp5 6 6 3 1 ppppp2

5
4

1 p2 p3

from the initial state p1. This will simplified DFA can be produced
b
a

orld
GFED@ABC p3 the states. there

GFED@ABC b
DFA obtained in this procedure,
is an equivalent minimum state DFA s .
}}}}}b
69 }
} }}}}}}}
a

GFED@ABC?>=<89:; a pp2 6
www.alljntuworld.in JNTU World
J
Proof. defined For x non-final is x We because a as the sRecall where∈ L∈

N
∈ well-defined desired. Claim Proof Claim Proof are number Σ. Σ[p],[q]

ˆ
prove ΣQ with q F δ ∗ ∗ 0 . the , Let Now, the in : = This δ both = = Q states, of of δ ˆ([q1: 2:

the our [qproof respect ∈ {[q] {[q] s ([qequivalence × of 0], Claim 0],ε)=[qClaim L(s s Q
 ˆ
T
suffices δ(δ(p, 0], = Definition Σ states and assertion ∈ | , as is xa) (Q,Σ,

−→ (2) q suppose Q the ) to a 2: s = p is 1: a),x) ⇒ | minimal Q of ≡ because ≡ index

U
accessible L(s 0]=[δ q = = = = ˆWe is δ, In (3) ([qq. classes ∈ sthat is

ˆ
by 4.4.8. qa L, δ δ [δ([F} [p]=[q], prove 0,F) 0],x) = fact, δ(qThus, defined s of DFA. ).
 ˆ ˆ ˆ
δ(qˆ(([of δ a induction δ(qˆ δ(p, δ(q contain 0, Myhill and state ([qminimal 0,ε)]. = of xa)]

0,x),a)] Construct be ∈ we ∼ 0,x)],a) from that 0],x),a) δ(p, ax) (Q ∼ L F by a DFA L, show =

i.e. ,Σ,δ For DFA ⇐⇒ Nerode a) the and the qδ it 0}, the on DFA ([q],a)=[δ(q,a)]. and (by

W
is inductive p (by accepting states that number ,q δ(δ(q,a),x)

ˆ
δ(q ˆthe and |x|. ≡ sufficient index 0definition δ(q,a) accepting ,F inductive 0,x) theorem
ˆ
q. set ≡ δ Basis accessible ) ([qNow of be of ∈ of step, 0],x) L. are F. equivalence to the

states ∼ and for = given of L. hypothesis) s prove equivalent. consider

 o ˆ
state δ(q, = δ induction . Since from observe ) of [a δ(qˆax) that s

r
equivalence ∈ 0,x)], qthe classes 0, Σ, x are is that ∈ Hence, states equal for

is final Σfor ∗ clear, of each

 ld
and

all as
or
to of Q
δ
the index of ∼ L ≤ the index of ∼ s .
70 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
On the other hand, suppose there are more number of equivalence classes for s then that
of ∼ L does. That is, there exist x, y but not x ∼ s y.
ˆ ˆ ˆ
That is, δ ([q0],x) = δ ˆ([q0],y). That is, [δ(q 0,x)] = [δ(qˆ0,y)]. That is, one among δ(q 0,x)

and δ(qˆ0,y) is a final a non-final state.

That is, x ∈ L ⇐⇒ y /∈ L. But this contradicts x ∼ L y. Hence, index of ∼L = index of ∼ s .
Example 4.4.16. Consider the DFA given in following δ → 07162534 q0 q1 07162534 q2
 JN
07162534 q3 We ∏∏∏compute 0 1 2 =

=
=
Downloaded From JNTU World (http://www.alljntuworld.in) {{{q{qthe

T U ∏
0,q0},{q 2,qpartition 2,q3,q3,q4},{q 4},{q
1,qthrough 1,q5,q5,q6}07162534 qqq4 }

W
6}5 6 the qqqqqqqa 1 0 4 4 2 0 3 following: qqqqqqqb 0

4
}
 o r
∈ Σstate ∗ the transition such and hypothesis that the table. x

ld
other ∼ that L y,

is
{}
∏∏3 4 = =
{{q0},{q2,q3,q4},{q1,q5},{q6}}

a 71 {{q0},{q2,q3},{q4},{q1,q5},{q6}} {q0},{q2,q3},{q4},{q1,q5},{q6}as
∏ = ∏ , we have ∏ = ∏
Since 3 4 4 . By renaming the equivalence classes

p0 = {q0};p1 = {q1,q5};p2 = {q2,q3};p3 = {q4};p4 = {q6} we construct an equivalent minimal

DFA as shown in the following.
GFED@ABC?>=<89:; p0 a GFED@ABC p1 b
a

GFED@ABC?>=<89:; p2 a
GFED@ABC?>=<89:; p3 b
b
a

GFED@ABC p4
b
www.alljntuworld.in JNTU World
4.5 Regular Languages
Language represented by a regular expression is defined as a regular language. Now, we
are in a position to provide alternative definitions for regular lan- guages via finite automata
(DFA or NFA) and also via regular grammars. That is the class of regular languages is
precisely the class of languages ac- cepted by finite automata and also it is the class of
languages generated by regular grammars. These results are given in the following
subsections. We also provide an algebraic method for converting a DFA to an equivalent
regular expression.
4.5.1 Equivalence of Finite Automata and Regular Lan-
guages
A regular expressions r is said to be equivalent to a finite automaton s , if the language
represented by r is precisely accepted by the finite automaton s , i.e. L(r) = L(s ). In order to
establish the equivalence, we prove the following.
1. Given a regular expression, we construct an equivalent finite automa-
 J N
pressions. sthis Lemma Proof. Then 2 2. To Q F δ =

hypothesis, : ton. Given = = clearly, Q (Qprove Construct QF× 2,Σ,δ4.5.1. 1 1 Suppose (Σ ∪

T
∪ a F(1), Qs ∪ DFA 2 2,qδ(q,a) 2 {ε}) we There and ∪ is s 2,Fwe {qa s
 U
prove there = finite 0} −→ 2) need = , exists (Q,Σ, we with which

乡(Q) the exist show automaton the δδ{q1(q,a), 2(q,a), a a 1,qδ, following accept

new following. finite qfinite defined that 2}, 0,F), state automaton L(s automata L(rwhere
three by q1) ) Let 0, is and lemmas. regular.

r1 saccepting L(rand 1 r2 be two regular ex- = (Q1,Σ,δ1,q1,F1) and 2), respectively.

Under
L(r1 + r2).
Downloaded From JNTU World (http://www.alljntuworld.in)
Wo
if q ∈ Q1,a ∈ Σ ∪ {ε}; if q ∈ Q2,a ∈ Σ ∪ {ε}; if

q = q0,a = ε.
as depicted in Figure 4.4.

rld
72
www.alljntuworld.in JNTU World

JNT
A εq1 A1 ε q
2

U
2
 World
δ1(q,a), if q ∈ Q1,a ∈ Σ ∪ {ε}; δ2(q,a), if q ∈ Q2,a ∈ Σ ∪ {ε}; {q2}, if q ∈ F1,a = ε.
Then s is a finite automaton as shown in Figure 4.5.
73 Downloaded From JNTU World (http://www.alljntuworld.in)

A FF1q0 2

Figure 4.4: Parallel Composition of Finite Automata

Now, for x ∈ Σ∗ ,
ˆ
x ∈ L(s ) ⇐⇒ (δ(q 0,x) ∩ F) = 0
ˆ ˆ ˆ ˆ
⇐⇒ (δ(q 0, εx) ∩ F) = 0 ⇐⇒ (δ( δ(q 0,ε),x) ∩ F) = 0 ⇐⇒ (δ({q 1,q2},x) ∩ F) = 0 ⇐⇒
ˆ ˆ ˆ
((δ(q 1,x) ∪ δ(qˆ2,x)) ∩ F) = 0 ⇐⇒ ((δ(q 1,x) ∩ F) ∪ (δ(qˆ2,x) ∩ F)) = 0 ⇐⇒ (δ(q 1,x) ∩

F1) = 0 or (δ(qˆ2,x) ∩ F2) = 0 ⇐⇒ x ∈ L(s1) or x ∈ L(s2) ⇐⇒ x ∈ L(s1) ∪ L(s2).

Hence, L(s ) = L(s1) ∪ L(s2).

Lemma 4.5.2. There exists a finite automaton accepting L(r1r2).

Proof. Construct
s = (Q,Σ, δ, q1,F2), where Q = Q1 ∪ Q2 and δ is defined by
δ(q,a) =
www.alljntuworld.in JNTU World

J
i.e. way ε-transitions from Then so L(sNow, Hence, Lemma

N ˆ A ˆ
that We Conversely, δ(q 1) to q1 and 1,x) δ(qclaim x reach to

ˆ
x4.5.3. p 1 = 1,x) some = ∈ some ∩ xFigure from qδ(q a1xthat F1 from
 T
1a ∩ 2 δˆ2 suppose state 1,aThere 1(q2 xF= ∈ (q...a2 2 L(s the 1,x)

1,xL(s1a4.5: A
0. q ∈ = 1 2 of L(sk 1 1) 0 to states ...aexists It ) 1)L(s∈ FSeries

U
x ∩ |−− so = |−−* |−−* 2, any = = is L(s2). ∈ Fk) there L(sthat

clear 1 a L(sof F2). That = (q(p, (p, (q(p state 1 1) and Composition finite 1,x2,xF1)L(s0 ,ε),
x xεxexist 1 1)L(sand from 2), ∈ 1x2), to 2) is, and δ(qˆof automaton L(s ε 2) for q2). 2,afor

W
p Fxthe 2. since 2). 22∈ δˆsome = k+1a). 2(qSuppose some

Thus, is Fconstruction Then of 1 a2,xqvia δ(p, k+1a2 and k+2 Finite 2) p accepting p qwhile

ε) ...ak+2 2. x a ∩ ∈ ∈ x A= number F= FFFurther, Automata ...a= 2 n) 2 2 1 {qtraversing

o
x= a∩ 1x2} of 1an 0. L(rF2, s ∈ 22k F...afor L(s2 = 1)≤ we that ∗ 0. . n n
 r
some through 2) have such ∈ the L(s xonly only

ld
that 1 ∈ ),

x
74 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World
Proof. Construct
s = (Q,Σ, δ, q0,F), where Q = Q1 ∪ {q0,p} with new states q0 and p, F = {p} and define δ

by
δ(q,a) =
Downloaded From JNTU World (http://www.alljntuworld.in)

{ {q1,p}, if q ∈ F1 ∪ {q0} and a = δ1(q,a), if q ∈ Q1 and a ∈ Σ ∪ {ε}

Then s is a finite automaton as given in Figure 4.6.

J N
If such with for Otherwise, x We Conversely, all = x that
 T
ε i = prove then and x1xwe x 2 for that trivially ∈ ...xFigure have psuppose

AL(s 1 some ∈ L(s k. pδ(qˆ1,p) Thus, δˆ4.6: x 1(ql 1,x) 2,...,p=⇒ =⇒ x ∈

U ˆ
≥ = 1,xKleene ∈ L(s1),p0. L(sfor qi) L(s1 δ(q either 2 If ∩ k 1)all

1)∈ 0,x) ∈ ∗ Fl 1)∗ . Star 1 1 δ(q. ˆF= A Otherwise, ε = . ≤ For

∗ 1 x ε = 1,x0, 1 Then 0 i and
 W
= of {p} ≤ then x 2),...,pε a for ∈ k, Finite or xx ΣFx1 1,x1 x ∗ = i

ˆ
δ(q there ≤ , ∈ = 2,...,xk xi 0,x) L(s1xAutomaton ∈ ε ≤ 2 and δ(qexist ˆl.

o rld
···x∩ 1) 1,xk Fso clearly, 1 l ε

ε
q0 ε p
= 0.

k) that x ∈ L(s1)∗ . with xi ∈ L(s1) x ∈ L(s ).

75
www.alljntuworld.in JNTU World
Now, consider the following computation of s on x:
(q0,x) = (q0, εx)

|−− (q1,x)

= (q1,x1x2 ···xl) |−−* (p 1,x2x3 ···xl), for some p 1 ∈ F1 = (p 1, εx2x3 ...xl) |−− ...Downloaded

since q1 ∈ δ(p 1,ε)

From JNTU World (http://www.alljntuworld.in) (q1,x2x3 ...xl),
ˆ
|−−* (p l,ε), for some p l ∈ F1 |−− (p, ε), since p ∈ δ(p l,ε). As δ(q 0,x) ∩ F = 0 we have x ∈

L(s ).
Theorem 4.5.4. The language denoted by a regular expression can be ac- cepted by a finite
automaton.
Proof. We prove the result by induction on the number of operators of a regular expression r.
Suppose r has zero operators, then r must be ε,0 or a for some a ∈ Σ.
If r = ε, then the finite automaton as depicted below serves the pur- pose.
?>=<89:;76540123 q
If r = 0, then (i) any finite automaton with no final state will do; or (ii) one may consider a

JN
finite automaton in which final states are not automata
 serve In case accessible the r purpose.are given from ?>=<89:; p
the initial state. For instance, the following two for each one of the two types indicated

T U
above and ∀ a∈ Σ = a, for ∀ a∈ Σ (i) some a ∈

Wo
Σ,?>=<89:; p ?>=<89:; p

∀ a∈ Σ
?>=<89:;76540123 q (ii)
a ?>=<89:;76540123 q

rld
is a finite automaton which accepts r.
76
www.alljntuworld.in JNTU World
Suppose the result is true for regular expressions with k or fewer operators and assume r
has k + 1 operators. There are three cases according to the operators involved. (1) r
expressions r1 and r2. In Downloaded From JNTU World (http://www.alljntuworld.in) = r1+r2, (2) r

any case, note = that r1r2, both or (3) the r regular = r1∗ , for expressions some regular

r1 and r2 must have k or fewer operators. Thus by inductive hypothesis, there exist
finite automata s1 and s2 which accept L(r1) and L(r2), respectively. Then, for each case
we have a finite automaton accepting L(r), by Lemmas 4.5.1, 4.5.2, or 4.5.3, case wise.
Example 4.5.5. Here, we demonstrate the construction of an NFA for the regular expression
a∗ b + a. First, we list the corresponding NFA for each subexpression of a∗ b + a.
/.-,()*+ a
a: /.-,()*+
ε
/.-,()*+ ε
a∗ :
/.-,()*+ b
/.-,()*+ a ε b : /.-,()*+
J N
Theorem Proof. base are two acase, ∗ F b We

cc c c c c
T /.-,()*+
possibilities = :ε ε let 0: prove 4.5.6. cc/.-,()*+ s In = this the If
 U
(Q,Σ, a for s result case ε is the /.-,()*+ δ, L(s a by qset DFA,

W
ε
0,F) induction ) of = be final then ε 0 /.-,()*+ /.-,()*+
o
L(s ) is regular.

on the number of states a DFA with only one state. states F.

and is regular.

rld
ε

/.-,()*+ a /.-,()*+ ε
/.-,()*+ ε /.-,()*+ b /.-,()*+
Now, finally an NFA for a∗ b + a is:
ε

/.-,()*+ ε
/.-,()*+ a /.-,()*+ ε
/.-,()*+ ε /.-,()*+ b /.-,()*+
/.-,()*+
ε

of DFA. For Then there

F = Q: In this case L(s )=Σ∗ which is already shown to be regular.
77
www.alljntuworld.in JNTU World
L
1
L
3
q0

Figure Assume that the result less than n. Now, let that the language L whereL1 is the set

J
of L2 is the set of include ε in L2 that q0 will not justified because, Using
 N
Since nation Ldenote That 2, The formally, that portion is, regular the it

T
the following if follows inductive revisits x set = and will languages of a1

that states ···ashow notation be q0 = hypothesis, 4.7: strings in s strings if at L L(s be the
 U
qLis is are the = 0 2. Depiction is true revisited regular. (Q,Σ,

portion shall ) closed last that also that can for we be time L δ, a start start be all with

final qof = q of while useful prove 0,F) 0 written does La will those the in and ∗ 1string

W L
respect state. not qbe 2 traversing that Language 0 be in appear
end and DFA a as defining part from DFA Further, both on in to end these whose the of

o
Kleene the with of in Lthose paths Lthe initial 1 1 initial a some we and

number and |Q| DFA languages star add strings. = Lstate final the position 2 n. and a

r
are of rest restriction First state. qconcate- states 0
 regular. This Lof 1 q0 note and We

ld
the

till is

is

that they are regular. For q ∈ Q and x ∈ Σ∗ , let us on the path of x from q that come
after q by P(q,x). n,

P(q,x) =
ˆ
⋃n{δ(q,a 1 ···ai)}. i=1Define
L1 L2 = =

{x ∈ Σ∗ | δ(qˆ{ L3, 0,x) = q0}; and

if q0 /∈ F; L3 ∪ {ε}, if q0 ∈ F,
78 Downloaded From JNTU World (http://www.alljntuworld.in)
www.alljntuworld.in JNTU World

where L3 = {x ∈ Σ∗ | δ(qˆClaim 1: L1 is regular.

0,x) ∈ F, q0 /∈ P(q0,x)}. Clearly, L = L∗ 1L2.

Proof of Claim 1: Consider the following set
A=
Downloaded From JNTU World (http://www.alljntuworld.in)

and for (a, b) ∈ A, define

L(a,b) = {x ∈ Σ∗ | δ(qˆ0, axb) = q0 and q0 /∈ P(qa,x), where qa = δ(q0,a)}.

Note that L(a,b) is the language accepted by the DFA

s(a,b) = (Q ,Σ,δ ,qa,F )

where Q = Q \ {q0}, qa = δ(q0,a), F = {q ∈ Q | δ(q,b) = q0}\{q0}, and δ is the restriction of

δ to Q ×Σ, i.e. δ = δ ∣ (a, b) ∈ Σ × Σ then, since q0 /∈ Q , q0 /∈ P(qa,x) and δ ˆ(qa,x)

∣
∣ ∣ Q ×Σ∈ . F For . instance, if x ∈ L(s(a,b))

This implies,

δ(qˆ0, axb) = δ(δ(qˆ0,a), xb)

ˆ
= δ(q a, xb)

J N
so |Q then Hence that | Claim Proof = clearly, n Lx 1 −
 T
of is 2: ∈ 1, Claim regular. LLby (a,b). 3 is inductive regular. 2: Converse

B===∣ ∣ ∣ ∣ ∣

δ(qˆ0, axb) = q0, for some x ∈ Σ∗ ; δ(q0,a) = q0; q0 /∈ P(qa,x), where qa = δ(q0,a).

U ˆ
hypothesis, δ(δ(p, q0, δ(q is b), a,x),b) similar. where L(a,b)
W o ∣
Thus p ∈ is F regular. L, (a,b) as = δ =δ ∣ ∣ Q

rld
×Σ L(s(a,b)). Now if we

Hence, as write
= {a ∈ Σ | δ(q0,a) = q0}∪ {ε}
L1 = B ∪ ⋃
aL
(a,b)b. (a,b)∈ AConsider the following set

C = {a ∈ Σ | δ(q0,a) = q0}
79