Regular Languages: outline

 Regular grammars
 Automata
 Finite State Automata (FSA)
 Regular expressions
 Minimization of DFSA
 Identification of non-regular languages
 Pumping Lemma for Regular languages

Formal Language Theory 1

Regular Grammars

 Definition: a PSG G = (N, T, P, S) is regular

provided that:
i. If there exists a λ-production, then it is of the form S  λ and
S does not appear on the right hand side of any production.
ii. All other productions are of the form:
 α  β, α Є N, β Є T, OR
 α  βγ, α, γ Є N, β Є T
 A language generated from a regular grammar is called a
Regular Language.
 Ex1. G1:
S  aS | aB
B  bB | b
Is G1 a regular grammar?
Formal Language Theory 2
Regular Grammars: cont’d

 Ex2. Write a grammar G2 such that L(G2) = L(G1) U

{λ}
 Theorem: Given a λ-free regular grammar G = (N,
T, P, S) such that L = L(G), we can construct a λ-
free grammar G+ = (N, T, P+, S) such that L(G+) =
L+
 Theorem: If L1 and L2 are two regular languages,
then:
a. L1 U L2 is also a regular language
b. L1L2 is also a regular language
c. L1* is also a regular language

Formal Language Theory 3

Transition diagrams

 A regular grammar G=(N, T, P, S) can be

represented by a transition diagram (a directed
graph with labeled arcs as follows:
 The nodes of the graph are to contain non-terminals
 The arcs are labeled with terminals
 One of the nodes is an initial node which is designated
with a pointer
 One (or more) of the nodes is designated as final node
which is either a square or a double circle
 If AaB is in P, then the arc from A to B is labeled with a
 If Aa is in P, then the arc from A to a final state is labeled
with a

Formal Language Theory 4

Transition diagrams: cont’d

 Example:
Let G=(N, T, P, S) be a regular grammar with
P: SaA|bB
AaA|a
BbB|b
Draw a transition diagram that represents G

Formal Language Theory 5

Automata

 Abstract machines
Characteristics
 Input: input values (from an input alphabet ∑) are applied
to the machine
 Output: outputs of the machine
 States: at any instant, the automation can be in one of the
several states
 State relation: the next state of the automation at any
instant is determined by the present state and the present
input
 Output relation: output is related to either state only or to
both the input and the state

Formal Language Theory 6

Automata: cont’d

 Types of automata
 Final State Automata (FSA)
 Deterministic FSA (DFSA)
 Nondeterministic FSA (NFSA)
 Push Down Automata (PDA)
 Deterministic PDA (DPDA)
 Nondeterministic PDA (NPDA)
 Turing Machine (TM)

Formal Language Theory 7

Deterministic FSA (DFSA)

 Definition
A DFSA is a 5-tuple M=(Q, ∑, t, qo, F)
where:
i. Q is a finite set of states
ii. ∑ is an input alphabet
iii. t is a, possibly partial, function
t: QX ∑  Q
iv. qo Є Q is the initial state
v. FC Q is a finite set of final states
Formal Language Theory 8
DFSA: cont’d

 Example: M=(Q, ∑, t, qo, F)

Q={S, A, F}
S b ∑={a, b}
Qo=S
F F={F}CQ
a

A a

State Input Next state

S a A
S b F
A a F

Formal Language Theory 9

DFSA: cont’d

 Acceptance of strings by DFSA

 A string w in ∑* is accepted by a DFSA M if

• There exists a path which originates from some initial

state, goes along the arrows, and terminates at some
final state, and
• The path value obtained by concatenation of all edge-
labels of the path is equal to w.

Formal Language Theory 10

DFSA: cont’d
 Example:
a Q = {S, A, B, C, D}
S a A ∑ = {a, b}
qo = S
b b a F = {C, D}

B C b D
a
b
State Input Next state Check whether the following
S a A strings are accepted or not:
S b B
A a A • ab
A b C • ba
B b B • bbaba
B a C • aa
C b D • aaabbaaa
D a D

Formal Language Theory 11

DFSA: cont’d

 Extensions of t
t needs to be extended as:
t: Q X Σ*  Q
let x ε Σ*, then
i) x = λ
ii) x = ay, a ε Σ, y ε Σ*
Then i) t(q, λ) = q
ii) t(q, x) = t(q, ay)
= t(t(q, a), y)
Eg. a) t(S, ab)
b) t(S, bbba)
c) t(S, aaa)

Formal Language Theory 12

DFSA: cont’d
 Given DFSA M, the set of strings accepted by
M is given by L(M)
L(M) = {xεΣ* | t(qo,x) ε F}

Formal Language Theory 13

Nondeterministic FSA (NFSA)
 Definition
An NFSA is a 5-tuple M=(Q, ∑, t, qo, F) where:
i. Q is a finite set of states
ii. ∑ is an input alphabet
iii. t is a, total, function
t: QX ∑  2Q
iv. qo Є Q is the initial state
v. FC Q is a finite set of final states

Formal Language Theory 14

 NFSA: cont’d
Example:
a State Input Next state(s)
a S a {A}
S A S b {B}
A a {A, C}
b a A b {}
B a {}
B b {B, C}
B C
S C a {}
b C b {}
b

The strings aa, bbb are both accepted by the NFSA.

Formal Language Theory 15

NFSA: cont’d
String Acceptance by NFSA

 Extensions of t:
1. t: Q X Σ  2Q to t: 2Q X Σ  2Q by defining
t(Q’, a) = Ut(q, a), qЄQ’, Q’CQ, a Є Σ
1. t: 2Q X Σ  2Q to t: 2Q X Σ*  2Q
let x Є Σ*, then
i) x = λ  t(Q’,x) = Q’
ii) x = ay, a Є Σ, y Є Σ*
 t(Q’, x) = t(Q’, ay) = t(t(Q’, a), y)
Example: Evaluate the following using the NFSA in the previous
slide
a) t(S, aaa)
b) t(S, aaba)

Formal Language Theory 16

NFSA: cont’d

 Let M be an NFSA,
L(M) = set of strings accepted by M
= {x Є Σ* | t(qo, x) n F ≠ Ø}

Formal Language Theory 17

 NFSA: cont’d
Example:
a,b State Input Next state(s)
a S a {A}
S A S b {B}
A a {A, C}
b a A b {A }
B a {B,C}
a B b {}
B C
S C a {C}
a C b {}
a

Consider the above NDFSA, find

i) t({A,C},abba)
ii) Let x=aab

Formal Language Theory 18

Equivalence of DFSA and NFSA
 Theorem: Let L be a language. L is accepted by a
DFSA iff L is accepted by NFSA.
proof:
i) (=>): L is accepted by DFSA=>L is accepted by
NDFSA
ii) (<=): L is accepted by NFSA=>L is accepted by DFSA

Any DFSA can have a total function by introducing

a dummy state such that all undefined transitions
are defined to that state

Formal Language Theory 19

 i) Given a DFSA with a partial function,it is
possible to convert it to a total function as
follows:
 i) set t(q,a)=Δ, a dummy state,where t(q,a) is
undefined
 ii) t(Δ,a)= Δ, for each a ε Σ

 Now assume that M=(Q, Σ,t,q0,F) with a total

function and construct NFSA
M’(Q, Σ,t’,q0,F) such that L(M)=L(M’)

Formal Language Theory 20

 Define
t’(q,x)={t(q,x)}

ii) (<=) L is accepted by NFSA => L is accepted

by DFSA.

Formal Language Theory 21

Equivalence: cont’d
Let M = (Q, ∑, t, qo, F) be NFSA, We construct DFSA M’
such that L(M)=L(M’)
1. Start {qo} and calculate t({qo},a), for all aЄ∑.
ie. Obtain possible states that are reachable from qo, say K.
1. Calculate t(K,a) for all aЄ∑
2. Repeat this process until no new subsets of Q are constructed
Thus, M’ = (Q’, ∑, t’, qo’, F’) where
Q’ = all subsets of Q reachable from qo
qo’ = {qo}
F’ = K’ C Q such that K’ n F ≠ Ø
t’ is an extension of t such that t: 2Q X Σ  2Q
L(M) = L(M’)
Illustration:

Formal Language Theory 22

 Example:
Given the following NFSA, Construct its
equivalent DFSA.

Formal Language Theory 23

 a
a
qo q1

b a

q2 q3
S
b
b

Formal Language Theory 24

 Solution:
 Find reachable states from qo.
t(q,a) t(q,b)
State a b
{qo} {q1} {q2}
{q1} {q1,q3} {}
{q2} {} {q2,q3}
{q1,q3} {q1,q3} {}
{q2,q3} {} {q2,q3}

Formal Language Theory 25

 Hence M’=(Q’, Σ,t’,qo’,F’)

Where Q’={{qo}, {q1}, {q2},{q1,q3},{q2.q3}}

qo={q0}
F’ ={{q1,q3},{q2,q3}} and t is given by:
aa a aa
{qo} {q1} {q1,q3
b
{q2,q3}
{q2,q3}
{q2} bb
b

Formal Language Theory 26

Equivalence: cont’d
 Theorem: The following statements are equivalent:
i. L is accepted by NFSA
ii. L is accepted by DFSA
iii. L is generated by a regular grammar
Proof: (i) => (ii) => (iii) => (i)
(i) => (ii) proved in the previous theorem.
(ii) => (iii)
Let L be a language accepted by DFSA M. Construct a regular grammar G such
that L(M) = L(G)
Let M = (Q, ∑, t, qo, F)
Construct of G = (N, T, P, S) as follows:
1. N = Q, T = ∑, S = qo
2. P:
qi  aqj, if t(qi, a) = qj
qi  a, if t(qi, a) Є F
L(M) = L(G)

Formal Language Theory 30

Equivalence: cont’d

(iii) => (i)

Let L be a language generated by regular grammar G.
We want to construct NFSA M such that L = L(M)
= L(G)
Let G = (N, T, P, S)
Construct M = (Q, ∑, t, qo, F) as follows:
1. Q = N, ∑ = T, qo= S, F = {xЄN| x  a Є P, a Є T}
Q = N U {Ff}, Ff not in N
2. t is given by:
if qi  aqj, then t({qi}, a) n {qj} ≠Ø
qi  a, then t({qi}, a) n F ≠Ø
L(M) = L(G)
Illustration:

Formal Language Theory 31

Equivalence: cont’d

 Theorem: If L is a regular language, then so

is L bar (L’).
proof:
L is regular  there exists a DFSA M = (Q,
∑, t, qo, F) such that L = L(M)
xЄL  t(qo, x) Є F
x ЄL’  x is not in L  t(qo, x) is not in F
Hence, M’ = (Q, ∑, t, qo, Q\F) such that L’ =
L(M’)
Formal Language Theory 32
Equivalence: cont’d

 Theorem: If L1 and L2 are regular languages,

then so is L1 n L2.
proof:
L1 is regular  L1’ is regular
L2 is regular  L2’ is regular
 L1’ U L2’ is regular
 (L1’ U L2’)’ is regular
 L1 n L2 is regular

Formal Language Theory 33

FSA with λ moves

 Definition: Let M = (Q, ∑, t, qo, F) be a FSA,

M is said to be with λ-moves if
t:QX(∑U{λ})Q
Example y
λ
qo q1 R(q) = the set of λ-reachable states
x For ex. R(qo) = {qo, q1, q2, q3}
λ y λ
If t(qi, λ) = qj, then qj is λ-reachable
q3 q2 from qi
y
For Q’ C Q, R(Q’) = UR(q’), q’ЄQ’

Formal Language Theory 34

FSA with λ moves:
b
cont’d
λ
qo a qf Q = {q0, q1, q2, qf}
λ a a ∑ = {a, b, λ}
b b

q1 q2
b
b
a

Let q, q’ Є Q. If q’ Є t(q, λ), then q’ is λ-

reachable denoted by q  *
λ q’
Let R(q) be the set of states that are reachable,
R(q) = {q’| q  q’}
If Q’ C Q then R(Q’) = U R(q), q Є Q’
Formal Language Theory 35
FSA with λ moves: cont’d

 Example: consider the previous NFSA

R(qo) = ?
R(q1) = ? R(q2) = ? R(q3) = ? R(qf) = ?
R({qo, q1, q2, qf}) = ?

Formal Language Theory 36

String acceptance by FSA with λ moves

 Extend t to t’ such that

t’: Q X (∑U{λ})  2Q defined as
t’(q, λ) = R(q)
t’(q, a) = UR(t(q’, a)), q’ЄR(q), aЄ ∑U{λ}

Ex. consider the previous NFSA

t’(qo, λ) = ?
t’(qo, a) = ?
t’(qo, b) = ?
 Extend t’ such that t’: 2Q X (∑U{λ})  2Q defined as
t’(Q’, λ) = R(Q’), Q’ C Q
t’(Q’, a) = Ut’(q’, a), q’ЄQ’, a Є ∑

Formal Language Theory 37

String acceptance: cont’d

 Extend t’ such that t’: 2Q X ∑*  2Q defined

as
t’(Q’, ax) = t’(t’(Q’, a), x), a Є ∑, x Є ∑*

Thus, L(M) = {x Є ∑*|t’(qo, x) n F ≠Ø}

= set of strings accepted by
NFSA with λ-moves

Formal Language Theory 38

Cont’d

 Theorem: If L is accepted by NFSA with λ-moves,

then L is a regular language.
proof: It suffices to construct an equivalent NFSA
without λ-moves
Let M = (Q, ∑, t, qo, F) be NFSA with λ-moves
To construct M’ = (Q, ∑, t’, qo, F’), define
t’(q, a) = t(q, a), for all aЄ∑ and t is the 3rd extension
F’ = F if R(qi) n F = Ø
= F U {qi} otherwise
L(M) = L(M’)
Formal Language Theory 39
Cont’d

 Example: Construct an equivalent NFSA

without λ-moves for the NFSA in the previous
example.
 For every state q, first check R(q) and calculate
t(R(q), a) for aЄ∑
 Then check R(q’) for the second time where q’ is
the result of t(R(q), a) for aЄ∑

Formal Language Theory 40

Regular Expressions

 Definition: A regular expression is a string

over ∑ if the following conditions hold:
1. λ, Ø, and a Є ∑ are regular expressions
2. If α and β are regular expressions, so is αβ
3. If α and β are regular expressions, so is α+β
4. If α is a regular expression, so is α*
5. Nothing else is a regular expression if it doesn’t
follow from (1) to (4)
 Let α be a regular expression, the language
represented by α is denoted by L(α).
Formal Language Theory 41
Regular Expressions: cont’d
 L satisfies:
1. L(Ø) = Ø, L(λ) = {λ}, L(a) = {a}, aЄ∑
2. If α and β are regular expressions, then:
 L(αβ) = L(α)L(β)
 L(α+β) = L(α)+L(β)
 L(α*) = L(α)*

 Example:
α = a*(b+c)
 L(α) = L(a*(b+c))
= L(a*)L(b+c)
= L(a)*(L(b) U L(c))
= {a}*({b} U {c})
= {a}*({b,c})
Note: In the absence of parentheses, the hierarchy of operations is as
follows: iteration, concatenation, and union.

Formal Language Theory 42

Regular Expressions: cont’d
 Two regular expression P and Q are equivalent (P=Q) if P and Q
represent the same set of strings.
 Identities for regular expressions
 Ø+R = R

 ØR = RØ = R

 λ* = λ, Ø*λ

 R+R = R

 R*R* = R*

 RR* = R*R

 (R*)* = R*

 λ + RR* = R* = λ + R*R

 (PQ)*P = P(QP)*

 (P+Q)* = (P*Q*)* = (P*+Q*)*

 (P+Q)R = PR + QR, R(P+Q) = RP + RQ

Formal Language Theory 43

Regular Expressions: cont’d

 Example: Give a regular expression for representing the set L

of strings in which every 0 is immediately followed by at least
two 1’s.

 Theorem: If r is a regular expression, then L(r) is a regular

language.
proof: construct NFSA with λ-moves that accepts L(r).
i. r = Ø, r = λ, r = a
ii. r1 + r2
iii. r1r2
iv. r1*
Let r be a regular expression, M(r) is a NFSA with λ-moves that
accepts L(r)

Formal Language Theory 44

Regular Expressions: cont’d

 Example: Construct NFSA that accepts

r=(a+b)*ba(ba)*

 Exercise: Construct NFSAs equivalent to

the following regular expressions:
1. (1+0)*(00+11)(0+1)*
2. 10+(0+11)0*1

Formal Language Theory 45

Regular Expressions: cont’d

 Theorem (Arden’s Theorem)

Let P and Q be two regular expressions over
∑. If P does not contain λ, then the following
equation in R,
R = Q + RP
has a unique solution given by R = QP*

Formal Language Theory 46

Regular Expressions: cont’d
 Algebraic method for finding the regular expression recognized
by a FSA
Assumptions
1. No λ-moves
2. There is only one initial state, say v1
3. Vertices are v1, … , vn
4. Vi is the regular expression representing the set of strings
accepted by the system
5. αij denotes the regular expression representing the set of labels
of edges from vi to vj
Consequently, we can get the following set of equations in v1, …, vn
v1 = v1α11 + v2α21 + … + vnαn1 + λ
v2 = v1α12 + v2α22 + … + vnαn2
…
vn = v1α1n + v2α2n + … + vnαnn

Formal Language Theory 47

Regular Expressions: cont’d

 By repeatedly applying substitution and

Arden’s Theorem, we can express vi in terms
of αij’s
 The set of strings recognized by the system
is found by taking the ‘union’ of all vi’s
corresponding to the final states.
 Example:
a b
a a Find the regular expression
equivalent to the given
q1 q2 q3 NFSA
b a

Formal Language Theory 48

Regular Expressions: cont’d

 Exercise: Find the regular expressions

equivalent to the following NFSAs

Formal Language Theory 49

Minimization of DFSA
 A DFSA with possible minimum states is called a minimal DFSA.
 Given M, DFSA that generates a language L, then we denote its minimal
DFSA by ML.
Construction of Minimal DFSA
Let M = (Q, ∑, t, qo, F) be DFSA such that L = L(M)
To construct ML, we proceed as follows:
I. Find all disjoint indistinguishable states of M
Define a number of relations Do, D1, …
- Given states q and q’, q is distinguishable from q’, by a string of length 0, denoted
by
qDoq’ iff either:
qЄF and q’ not ЄF OR
q not ЄF and q’ЄF
- If i>0, q is distinguishable from q’ by a string of length ≤ i, denoted by
q Di q’ iff
qDi-1q’ OR
if there exists aЄ∑ such that t(q, a)Di-1t(q’, a)

Formal Language Theory 50

Minimization of DFSA: cont’d

II. ML = (QL, ∑, tL, qoL, FL) where

QL= indistinguishable states
qoL= indistinguishable states containing qo
FL = Final states of M
tL is given by the following:
Let Q’CQ, where Q’ is indistinguishable
states
tL(Q’, a) = Q’’, indistinguishable states
containing t(q, a), qЄQ’
Formal Language Theory 51
Minimization of DFSA: cont’d

 Illustration: Construct a minimal DFSA for the

following DFSA
a
a
1 2

a b
b b a b

b
3 4 5
a

Formal Language Theory 52

Minimization of DFSA: cont’d

 Exercise: Minimize the following DFSA

a
a 3 5
a

1 b
b
b

a
2 4

a, b

Formal Language Theory 53

Identification of non-regular languages

 Lemma (Pumping lemma for regular languages)

Let L be a regular language and w Є L.
Then there exist substrings x, y, and z of w
with:
a. w = xyz, |w| ≥ m
b. |xy| ≤ m, for some m Є Z+
c. y ≠λ
such that xynz Є L for n ≥ 0

Formal Language Theory 54

Non-regular languages: cont’d

 Example: Show that the following languages

are not regular.
1. L = {anbn | n ≥ 0}
2. L = {an: n is prime}
3. L = {wwr | w ∑*}, ∑={a, b}

Formal Language Theory 55