ページ3:

qs
(q
as
follow!
qi
-
The division satisfies each of the three condition"
①Vi, xy'z E A This is clearly true.
②lyl > 0 This is due to two different
2
(3)
③Ixyl ≤ p This first P+1 state in the sequense
P
V
must have a repeation.
Provine Non-regularlority.
J J 5
• To prove toๆ จัง งัด แข็งเราจะทำการแสดง Con tradition) ภายหลัง
♡ 25 Pumping lemma leth P.
d
9 หา String ใน J & B โดย ขนาด 1ST - P และ Show that
such string s cannot be pumping
Considerirs all possible.
B.
9 กา เกา ( above, เมื่อเรามี Contradiction และ B ไม่เป็น regular
ถ้า

ページ4:

n
E. S. 1 B = 0" 1" n≥
{ { o^ ₁" | n ≥ 0 } We show that B is not regular.
Sol - Assume that
- Let
B
is
regular to obtain a contracdition
P
be the pumping Tenth.
=
- Chose a string E - OF; PEB, and so 1s1 = 2p>p
-
- Chose a divition s =
xyz
K>○
• To satifly ①, we must take y as y=ok, k>0
จ
and
x =
and Z
ด
• The division already satifies C②CL
0 0 ... 0 0
11
11
P ตัว
Poła
The division cannot satify ①
xyz
=
=
l
of (ok); OP- (k+1) 1
= 0.0
= 0
0
P
-
ik
K tik
1+(k+1)
P
1
P + (i-1) k p
1
Note OP+ (i-1)k, P & B, when i>o
P
P
1
1.06
also OP+ B,
P+ (i-1)k, P & B also when it
0
=
น

ページ5:

ES2 C = {wlw has an equre number of Os and 1s}
Note: Since BCC, I's not regular, but we wish to show a
string in C that cannot we purpond.
P/2
9
1
P/2
Consider: S 0
0 P/2
=
and ISI
=
2P>P
1
1
P/2
E C
② 5´ = (01) P = 010101... 01 € C
E
Pump ได๋
2P>P
and 151
ap
=
P
=
0
1 P o E C
1 1
2P+2
and Is1 = 2P+2>P
Is'I
Pump
P/2
P/2
1
Sol
P/2
1) S
0
1
P/2
0
า
Z
X
y
E
P/2
0 1
P/2
P/2
0
1
P/2
S= xyz where x = 2₁ y
E C
=0%2
ง
E C and ISI = 2P>P
P/2 P/2
Z = 0
1
sati fies,, and so we can pump it
010101 01 Ed and 151 = 2P>P
2)5
2) 5´ = (01) P = 010101.
ap
x
y
Z
01 01 01. 01 =
£ 0 1 01
01
0 1 0 1 -
01
P
P
5=
xyz
where
x = Z
2 y
=
(01 )
Satifie 0,
ๆ
P/2
72-(01)8/2
=
and so we pump it

ページ6:

P
3 ) 5 " = 0³ 1 1 ³ 0 € C and 1s = 1 = 2p + 2 >p
2P+2
P
E
S" = 0³ 1 1 0 E C
47
00... 00
111
1
P
P
S² = xyz
x = 0l
where
Y = 0x
P = (k + l)
P
Z = 0
11
OK >0
#0
09
satifies ③, 1", but con not ⑥
(3
(2)
bc Vi, xy'z of cok
=
P
op -(k+1); 10
=0P+ (i-1) k 11 P0
when i> the number of Os >
the number of 15
C.
resulting string, which isn't in C

ページ7:

E. S 3
D = { 0 ² 1 j ; i >; }; Show that D is not regular.
KP-k
Sol 1 S = ok 1
P-ķ
k> P/2
E D 151
9
00...@ 11 ... 11
P
K- (P-K) = 2
P
P-k
≥ P
S' = D³ 01³ & D, Isl = 2p+22 P
ง
00. 00 11 ... 11
regular
language
M
P
P
Pumping
=> 0² ₁P & D
1
#D
•Universe of all language
non regular
n
[B,C,D, JB = {o" "In 20}
1
*lem da Calculust
Computional Pome ; Finite Automata < Push down Automata<
Turing Machine ( Regular Expression
< Context - free Grammar <Becusive language