Lemme Every G N FA has an
equivalent regular
expression R
the
Proof By induction on the number
of elates k of
UNFA G
Beneath 2 a A r
Induction hypothesis Acme that the statement in
2 I k k l
Tfa e t
Indistep To show an l state machine
has induction
an
quivalent regular expreen given
hypothesis holds
4 We pick any stali lay a except the start
and the accept etat
Remove the state n
3 Repair the damage by recovering all paths
that went via n
ri.EE
4
Vian 816283
ay
direct ru
TN 3
eg
2a.b
h
oI W aub
I a b
ago
RH
Wyd
Renee
E R
a
a
where R at b aub
MIIMgimftal man of o e and 1 s
C w w her equal no
of 01 and 10 sub strings
h W
04 011 004 U 1 100 11
Pumpinghemme For every regular language A there
is a number Cay p called the pumpinglingth
such that if SEA and IP then S
ny
z
where C EA
my z
for all i 70
y te
I myl E p
y
Greed idea to show non regularity is Aarne language
is
gular
contradiction via the pumping lemma
Ty find
Let DFA M recognize A let p be the
Proof
number elates in M
of
Then pick se A where 1515 p
s
nyt
Ominous
s nyi z e A
_gz y te
Kyle
B out I eg
n 70 is not regular
Asu me that B in regular so the pumping lemma
by
there is
p which ratifies the
a
pumping length
pumping lemma My IEP
s OPy P E B
s
Izzy my
z
et F wwl we 7 I 0,13 in Notre
s OPOP
X y
00
0000
S OP1 OP y E
F Y
cannot be pumped
N 01
S
my Z S
007501 2
my z F
B w w has gud he no
of O c and 1 s
hit B he regular
O 1 in regular
Bn o l B
I Y
