Bài giảng Lý thuyết tính toán: Chương 1

ChChàào mo mọọi ngư

i ngườời !i !

Hello Everyone! Hello Everyone! Hello Everyone!

nh toáánn Lý thuyếết tt tíính to Lý thuy Lý thuyết tính toán (Theory of Computation) (Theory of Computation) (Theory of Computation)

Bonjour Tout le Monde ! Bonjour Tout le Monde ! Bonjour Tout le Monde !

PGS.TS. Phan Huy Kháánhnh PGS.TS. Phan Huy Kh khanhph@vnn.vn khanhph@vnn.vn

他他 ﺾ ﺾ 好好 !! 他 ﺾ 好 !

аждый !! Привет KKаждый Привет Привет Kаждый !

Chương 11 Chương 1 Chương MMởở đ đầầuu Mở đầu

2/2/5656

MMụục đc đíích môn h

ch môn họọcc

KiKiếến thn thứức yêu c

c yêu cầầuu

Lý thuyếết tt tíính to

nh toáánn (Theory of Computation

(Theory of Computation) )

 Môn hMôn họọc yêu c

c yêu cầầu mu mộột st sốố kikiếến thn thứức tiên quy

c tiên quyếết :t :

c cơ bảản vn vềề ::

Môn hMôn họọc c Lý thuy cung cấấp nhp nhữững ki cung c  CCáác mô h

ng kiếến thn thứức cơ b n lý thuyếết :t : nh toáán lý thuy u nhiên y truy cậập ngp ngẫẫu nhiên

 CCáác mc mááy truy c

c mô hìình tnh tíính to

 CCáác ôtômat h

c ôtômat hữữu hu hạạn trn trạạng th

ng thááii

 Ngôn ng

i cương  Tin hTin họọc đc đạại cương  ToToáán rn rờời ri rạạcc  CCấấu tru trúúc dc dữữ liliệệu vu vàà gigiảải thu i thuậậtt

 Lý thuy

 MMááy Turing v

Sinh viên nắắm đưm đượợc :c :  Sinh viên n c mô hìình tnh tíính to  CCáác mô h  CCáác khc kháái ni i niệệm cơ b phương phááp chp chứứng minh h phương ph

 CCáác hc hààm đm đệệ quyquy

 CCóó khkhảả năng minh ho

 CCáác khc kháái ni ttíính quy

nh thứức vc vàà văn ph Ngôn ngữữ hhìình th Lý thuyếết đt độộ phphứức tc tạạp tp tíính to văn phạạmm nh toáánn nh toáán tn tổổng qu y Turing vàà khkháái ni i niệệm tm tíính đư nh đượợcc ng quáátt m cơ bảản vn vềề đ độộ phphứức tc tạạp tp tíính to nh toáán,n, ng minh hìình th nh thứứcc năng minh hoạạ hohoạạt đt độộng cng củủa ca cáác mô h c mô hìình đnh đóó i niệệm vm vềề bbàài toi toáán, thu n, thuậật tot toáán, tn, tíính gi nh giảải đưi đượợc,c, bbằằng thu ng thuậật tot toáán, n, chương tr chương trììnhnh nh... nh quyếết đt địịnh...

3/3/5656

4/4/5656

TTàài li

i liệệu tham kh

u tham khảảoo

ĐĐáánhnh gigiáá kkếếtt ququảả hhọọcc ttậậpp

 GiGiááo tro trìình PPT

nh PPT ““Lý thuy

Lý thuyếết Tt Tíính to

nh toáánn””

 Yêu c

i dung trìình bnh bààyy trêntrên llớớpp

 http://www

courses.cs.uiuc.edu/~cs375/ http://www--courses.cs.uiuc.edu/~cs375/

www.cs.berkeley.edu/~vandam/CS172/  www.cs.berkeley.edu/~vandam/CS172/

 Tinh th

năng lựực hc họọc tc tậậpp

Keywords to findout on internet (Google):  Keywords to findout on internet (Google):

Computation | Computing Theory  Computation | Computing Theory

Computability | Decidability  Computability | Decidability

Yêu cầầu :u :  HiHiểểu nu nộội dung tr  ThThựực hic hiệện cn cáácc bbààii ttậậpp vvềề nhnhàà  KhKhảả năng th năng thựực hc hàànhnh Tinh thầần thn tháái đi độộ vvàà năng l ng, ghi chéépp Nghe giảảng, ghi ch  Nghe gi t câu hỏỏii  TrTrảả llờời vi vàà đ đặặt câu h Tham khảảo to tàài li  Tham kh Tham gia họọc nhc nhóóm, tm, tậập thp thảảo luo luậận vn vàà thuy  Tham gia h  ……

Formal Language | Automata Theory  Formal Language | Automata Theory

Set | Graph Theory  Set | Graph Theory

 KiKiểểmm tratra cucuốốii kkỳỳ :: t (60 phúút)t)  ThiThi viviếết (60 ph

p internet u, truy cậập internet i liệệu, truy c thuyếết trt trìình nh

5/5/5656

6/6/5656

NNộội dung môn h

i dung môn họọcc

Đâu làà gigiớới hi hạạn cn củủa Tin h Đâu l

a Tin họọc ?c ?

 Nghiên c

Chương 11 MMởở đ đầầu : u : cơ scơ sởở ccủủa môn h Chương

a môn họọcc

n (problem) : Nghiên cứứu vu vềề bbàài toi toáán (problem) : (resolvability)  LLớớp cp cáác bc bàài toi toáán gin giảải đưi đượợcc (resolvability)

Chương 22 Ôtômat h Chương

Ôtômat hữữu hu hạạnn

 LLờời gi

i giảảii, hay

, hay thuthuậật tot toáánn, , đđểể gigiảải bi bàài toi toáán n

 LLớớp cp cáác bc bàài toi toáán không gi

n không giảải đưi đượợcc

Chương 33 Văn ph Chương

Văn phạạm vm vàà ôtômat đ

ôtômat đẩẩy xuy xuốốngng

((vvàà ssẽẽ không bao gi không bao giờờ gigiảải đưi đượợc,c, ddùù vvớới si sựự titiếến bn bộộ ccủủa công ngh

y Turing Chương 44 MMááy Turing Chương

u lý thuyếết ct cáách gi

a công nghệệ thông tin trong tương lai thông tin trong tương lai)) ch giảải ci cáác bc bàài toi toáánn

 Nghiên c

Chương 55 HHààm đm đệệ quyquy Chương

Nghiên cứứu lý thuy nh toáán ?n ?  Mô hMô hìình tnh tíính to

 ĐĐộộ phphứức tc tạạp tp tíính to

nh toáán ?n ?

y RAM Chương 66 MMááy RAM Chương

 TTíính quy

nh quyếết đt địịnhnh

Chương 77 Lý thuy Chương

Lý thuyếết đt độộ phphứức tc tạạp tp tíính to

nh toáán n

7/7/5656

8/8/5656

NhNhữững ch

ng chủủ đ đềề chchíính cnh củủa Tin h

a Tin họọc lý thuy

c lý thuyếếtt

Đâu làà gigiớới hi hạạn cn củủa Tin h Đâu l

a Tin họọc ?c ?

 Nghiên c

nh toáán :n :

Nghiên cứứu cu cáác c mô hmô hìình tnh tíính to  CCáác ngôn ng

c ngôn ngữữ hhìình th

(Formal Languages) nh thứức c (Formal Languages)

t lý :  GiGiớới hi hạạn cn củủa Va Vậật lý : i chuyểển đn độộng vng vĩĩnh cnh cửửuu vvìì ::

 CCáác ôtômat h

(Finite Automaton) c ôtômat hữữu hu hạạn n (Finite Automaton)

Không tồồn tn tạại chuy  Không t Mâu thuẫẫn vn vớới ci cáác đc địịnh lu Mâu thu

 MMááy Turing

nh luậật vt vềề nhinhiệệt đt độộng lng lựực hc họọc c

(Turing Machine) y Turing (Turing Machine)

 CCáác hc hààm đm đệệ quy

(Recursive Functions) quy (Recursive Functions)

 MMááy RAM

(Random Access Memory Machine) y RAM (Random Access Memory Machine)

 ĐĐộộ phphứức tc tạạp tp tíính to

(Computational Complexity) nh toáán n (Computational Complexity)

 MMậật mã h

(Cryptology) t mã họọc c (Cryptology)

 VVàà ccáác hưc hướớng nghiên c

ng nghiên cứứu mu mớới trong lý thuy

i trong lý thuyếết tt tíính to nh toáánn c nhau nh toáán khn kháác nhau

 MMốối quan h

i quan hệệ gigiữữa a ccáác mô h

c mô hìình tnh tíính to

chuyểển đn độộng ng

 Cơ sCơ sởở đ đểể thithiếết kt kếế MTĐT

MTĐT (ph(phầần cn cứứng)ng)

ChuyChuyểển đn độộng vng vĩĩnh cnh cửửuu ((Perpetual Motion) l Perpetual Motion) làà chuy n tiêu tốốn năng lư ng, không cầần tiêu t không ngừừng, không c không ng

n năng lượợngng

vvàà thuthuậật tot toáán (ph

n (phầần mn mềềm) trong

m) trong hihiệện tn tạại vi vàà tương lai

tương lai……

9/9/5656

10/10/5656

Chương mởở đ đầầu u : : cơ scơ sởở ccủủa môn h Chương m

a môn họọcc

MMộột st sốố kikiếến thn thứức Toc Toáán hn họọc c cơ scơ sởở

 LôgLôgíích hch họọcc

 TTậập hp hợợp, quan h

p, quan hệệ

 MMộột st sốố kikiếến thn thứức Toc Toáán hn họọc c cơ scơ sởở  BBảảng ch

ng chữữ vvàà câucâu

 ÁÁnh xnh xạạ vvàà hhààmm

 KhKháái ni

i niệệm ngôn ng

m ngôn ngữữ

 TTíính đnh đếếm đưm đượợc cc củủa ca cáác tc tậập hp hợợp vô h

p vô hạạnn

 MMááy try trừừu tưu tượợngng

 ĐĐồồ ththịị vvàà câycây

 VVấấn đn đềề bibiểểu diu diễễn ngôn ng

n ngôn ngữữ

 PhPhéép chp chứứng minh quy n

ng minh quy nạạpp

 CCáác cc cấấu tru trúúc rc rờời ri rạạcc

11/11/5656

12/12/5656

Câu trên bảảng ch Câu trên b

ng chữữ 

BBảảng ch

ng chữữ vvàà câucâu

 BBảảng ch

 Cho trư

Cho trướớc mc mộột bt bảảng ch

ng chữữ  nnàào đo đóó

c ký tựự ( (characters), hay ký

characters), hay ký tưtượợng/ng/

 MMộột t câucâu (phrase, word), hay

(string), trên  ::

u (symbol), ký hiệệu bu bởởi chi chữữ ccáái Hy l

i Hy lạạp p 

 llàà mmộột dãy h

ng chữữ llàà ssốố phphầần tn tửử ccủủa ba bảảng ch

ng chữữ đ đóó,,

(phrase, word), hay xâuxâu (string), trên t dãy hữữu hu hạạn cn cáác phc phầần tn tửử ccủủa a ,, (hay x, y, u, v...) ký hiệệu bu bởởi i ww (hay x, y, u, v...) ký hi

) (Cardinality) |, hay Card() (Cardinality)

 ĐĐộộ ddàài ci củủa ma mộột câu l

ng chữữ (alphabet) : (alphabet) :  llàà mmộột tt tậập hp hữữu hu hạạn cn cáác ký t ký hiệệu (symbol), ký hi ký hi  KKíích thư ch thướớc cc củủa ba bảảng ch ký hiệệu |u ||, hay Card( ký hi  VVíí ddụụ mmộột st sốố bbảảng ch

ng chữữ  ::

 ĐĐộộ ddàài câu l

 MMộột câu c

ng (empty word), câu rỗỗng (empty word),

Câu cóó đ độộ ddàài bi bằằng 0ng 0 đư đượợc gc gọọi li làà câu r  Câu c ký hiệệu u , ho, hoặặc e, ho ký hi

c e, hoặặc c  hohoặặc c 

| = 1 | = 1 | = 2 ||| = 2 ||| = 4 | = 4 Chữ số thập phân, ||| = 10 | = 10 Chữ số La Mã Chữ cái La tinh chữ cái Hi Lạp

{ # } { # } { 0, 1 } { 0, 1 } { { , , , , , ,  } } {0, 1, 2, ... , 9} {I, V, X, L, C, D, M} {aA, bB, cC, ... , zZ} {, , , ... , } Bảng mã ASCII Các nét viết chữ Hán

t trong câu, t câu làà ssốố ký tký tựự ccóó mmặặt trong câu, ký hiệệu lu làà ||ww| hay length( ký hi | hay length(ww)) i câu làà hhữữu hu hạạn,n, nhưng không hạạn chn chếế llàà ccóó bao nhiêu ký t nhưng không h bao nhiêu ký tựự t câu cóó ththểể ccóó ttừừ 0 0 đđếến n ký t n n ký tựự tutuỳỳ ýý

13/13/5656

14/14/5656

VVíí ddụụ vvềề câu trên b

câu trên bảảng ch

ng chữữ 

c câu PhPhéép ghp ghéép tip tiếếp cp cáác câu

 VVíí ddụụ

 Cho hai câu u v

v trên  (Concatenation) củủa u v

Cho hai câu u vàà v trên  PhPhéép p ghghéép tip tiếếpp (Concatenation) c  NghNghĩĩa la làà câu

{ 0, 1 } { 0, 1 }

 u đgl l

....z } { { aa....z }

, zt, computer aa, , abab, zt, computer

{ 0, ..., 7, , , , , , ,  } } { 0, ..., 7,

443322, 1234,

, 1234, 

 rrồồi đi đếến v l

ASCII ASCII

 TrưTrườờng hng hợợp câu w = xuy l (infix) củủa wa w

MMộột chương tr w|=n, ngưngườời ta c

t chương trìình C, Pascal, Java, VB... nh C, Pascal, Java, VB... ch ra từừ ww

 Cho mCho mộột câu w c

t câu w cóó ccóó | |w|=n,

 NgưNgườời ta còn g

mmộột ký t  VVíí ddụụ câu w=aaabbaabbba c

BBảảng ch Câu Câu trên a u vàà v lv làà câu câu ww = uv= uv ng chữữ  trên  câu ww ggồồm hai ph m hai phầần :n : , 0, 1, 00, 01, 10, 11, 100... , 0, 1, 00, 01, 10, 11, 100... (prefix) u đgl làà titiềền tn tốố (prefix) n v làà hhậậu tu tốố (postfix) c (postfix) củủa wa w p câu w = xuy làà ghghéép tip tiếếp cp củủa ba câu x, a ba câu x, u u, y, y,, trung tốố (infix) c u đgl trung t u đgl i ta còn gọọi câu r câu đơn vđơn vịị i câu rỗỗng ng  llàà câu

i ta cóó ththểể trtríích ra t t ký tựự nnàào đo đóó ccóó vvịị trtríí xxáác đc địịnh trong ph m vi 1..n nh trong phạạm vi 1..n câu w=aaabbaabbba cóó |w|=11, |w|=11, c ký tựự ::

 ww(1) =

Returning Returning

vvìì ccóó w = ww = w = w= w i w làà mmộột câu b vvớới w l t câu bấất kt kỳỳ trên trên  ccóó ththểể trtríích ra c ch ra cáác ký t (1) = aa, ..., , ..., ww(4) = (4) = bb, ..., , ..., ww(11) = (11) = aa

15/15/5656

16/16/5656

c trên xâu CCáác phc phéép top toáán khn kháác trên xâu

KhKháái ni

i niệệm ngôn ng

m ngôn ngữữ

 MMộột ngôn ng

t ngôn ngữữ hhìình th

nh thứứcc (n(nóói gi gọọn ngôn ng

n ngôn ngữữ) :) :

 Cho c

Cho cáác câu w trên

c câu w trên 

o ngượợcc (Reversion) m

(Reversion) mộột câu

t câu ww, ký hi

, ký hiệệu wu wRR ::

c câu  llàà ttậập hp hợợp cp cáác câu ng trên cùùng mng mộột bt bảảng ch

c xây dựựng trên c

đưđượợc xây d

ng chữữ đã cho

đã cho 

 VVíí ddụụ ::

c xâu trên bảảng ch

ng chữữ 

 PhPhéép p ĐĐảảo ngư  LLàà câu  Rõ rRõ rààng ng RR = =   wwRR = = w đgl câu đ

câu ww đư đượợc vic viếết theo th t theo thứứ ttựự ngư ngượợc lc lạạii

c xâu trên bảảng ch

ng chữữ 

xâu rỗỗngng

(power) xâu  PhPhéép p LLũũy thy thừừaa (power) xâu

Chú ý {}   Chú ý {}  

ngôn ngữữ trtrốống (t

ng (tậập trp trốống)ng)

 ** llàà ngôn ng ngôn ngữữ ggồồm tm tậập tp tấất ct cảả ccáác xâu trên b xâu rỗỗngng kkểể ccảả xâu r  ++ llàà ngôn ng ngôn ngữữ ggồồm tm tậập tp tấất ct cảả ccáác xâu trên b KHÔNG CÓÓ xâu r KHÔNG C  ++ = = ** --    llàà ngôn ng

w đgl câu đốối xi xứứng : OMO, akitOM Otika... ng : OMO, akitOMOtika...

 VVíí ddụụ

 wwnn = ww= ww……w (n l  ww00 = =  vvớới mi mọọi wi w

Quy ước chỉ định một câu Quy ước chỉ định một câu (denotation) (denotation)

 L1 = {a, ab, abb, bba, bbb} l

L1 = {a, ab, abb, bba, bbb} làà ngôn ng L2 = {(ab)nn | n > 0} l

ngôn ngữữ hhữữu hu hạạnn trên {a, b} trên {a, b} trên {a, b} ngôn ngữữ vô hvô hạạnn trên {a, b}

| n > 0} làà ngôn ng

 L2 = {(ab)

nh thứứcc”” ( (Fomal)

ng phéép p ““hhìình th

i ta dùùng ph

w (n lầần)n)

ChChúú ý :ý : Chú ý : nhiên (Natural) Fomal) đ đểể đ đốối li lậập vp vớới i ““ttựự nhiên (Natural) NgưNgườời ta d Người ta dùng phép “hình thức” (Fomal) để đối lập với “tự nhiên (Natural)

17/17/5656

18/18/5656

ng (machine) MMááy try trừừu tưu tượợng (machine)

ChChứức năng

n câu c năng đođoáán nhn nhậận câu

MMááy đoy đoáán nhn nhậận câu

n câu ::

Dữ liệu vào

Dữ liệu ra

 GiGiảả ssửử ddữữ liliệệu vu vàào o ww*,*,

Máy

 TTậập hp hợợp câu v

nh IPO :  Mô hMô hìình IPO :

 CCóó ba kh

nhnhậận n ddữữ liliệệu vu vààoo (data) v

(data) vàà cho

(result) cho kkếết qut quảả rara (result)

1.1. True ho

c False True hoặặc False

2.2. MMộột kt kếết qut quảả khkháácc

 Hai cHai cáách nh  CCáách nh

ch nhììn :n : ch nhììn n chchứức năng

(functional look) c năng (functional look)

3.3. Không cho k

Không cho kếết qut quảả nnàào o

(structural look) ch nhììn n ccấấu tru trúúcc (structural look)

{0, 1}, hay {False, True } kkếết qut quảả ra ra rr{0, 1}, hay {False, True } p câu vàào o ww đgl đgl ngôn ng (language) ngôn ngữữ (language) ba khảả năng cho k năng cho kếết qut quảả ::

 Hai tHai tậập hp hợợp câu v nnếếu mu mááy cho k

 CCáách nh Phân biệệt ct cáác kic kiểểu mu mááy try trừừu tưu tượợng (machine type) ng (machine type)  Phân bi theo bảản chn chấất ct củủa ka kếết qut quảả ttíính to theo b

nh toáánn

p câu vàào o ứứng vng vớới hai kh i hai khảả năng đ nhau năng đầầu lu làà bbùù nhau y cho kếết qut quảả cho mcho mọọi di dữữ liliệệu vu vààoo

19/19/5656

20/20/5656

ChChứức năng

c năng ttíính to

nh toáánn

CCáách nh

c (structural look) ch nhììn cn cấấu tru trúúc (structural look)

MMááy ty tíính to

(computation machine) nh toáánn (computation machine)

 MMááyy đư đượợc xc xáác đc địịnh bnh bởởi mi mộột t ttậập hp hữữu hu hạạn cn cáác phc phéép top toáánn

 MMỗỗi phi phéép top toáán mô t

n mô tảả mmộột pht phầần cn cấấu tru trúúc cc củủa ma mááyy

 GiGiảả ssửử ddữữ liliệệu vu vàào o ww*,*, kkếết qut quảả ra ra llàà mmộột câu

 PhPhéép top toáán sơ cn sơ cấấpp (elementary operation) l

(elementary operation) làà phphéép top toáán nhn nhỏỏ

 Khi đKhi đóó, m, mááy thy thựực hi

nhnhấấtt (không chia c

(không chia cắắt nht nhỏỏ hơn

hơn) )

ff : : * *  **

(execution) mỗỗi phi phéép top toáán trong m

n trong mộột kho

t khoảảng ng

NghNghĩĩa la làà ww  *, *, ff((ww) )  **

 MMááy y ththựực hic hiệệnn (execution) m i gian hữữu hu hạạn vn vàà xxáác đc địịnhnh

ththờời gian h

Chương tr

(program) làà ttậập hp hợợp cp cáác phc phéép top toáán sơ c

n sơ cấấp đp đểể

ng chữữ  nnàào đo đóó t câu rr trên m trên mộột bt bảảng ch c hiệện tn tíính hnh hààm m ff ttừừ * v* vàào o * :* :

Chương trììnhnh (program) l gigiảải mi mộột bt bàài toi toáán nn nàào đo đóó

 NgưNgườời ta c

 MMộột t ttíính to

(computation) làà viviệệc thc thựực hic hiệện ln lầần lưn lượợt ct cáác c

nh toáánn (computation) l n sơ cấấp theo m

phphéép top toáán sơ c

p theo mộột tht thứứ ttựự xxáác đc địịnh trư

nh trướớcc

nnếếu vu vớới mi mọọi câu v (partial function)  HHààmm ff đư đượợc gc gọọi li làà hhààm tom toààn phn phầầnn (partial function) u cho kếết qut quảả ff((ww))** i câu vàào o ww*, m*, mááy đy đềều cho k i ta cũũng nng nóói i kikiểểu mu mááy đoy đoáán nhn nhậậnn chchỉỉ llàà trư trườờng hng hợợp đp đặặc c bibiệệt ct củủa a kikiểểu mu mááy ty tíínhnh

21/21/5656

22/22/5656

Mô hMô hìình tnh tíính to

nh toáán n

MMộột st sốố thuthuậật ngt ngữữ

 LLààm sao đ

t : m sao đểể ccóó ththểể bibiếết :

 ĐĐịịnh ngh

ng nguyên lý hoạạt đt độộngng

 LLớớp ngôn ng

(recognized), p ngôn ngữữ đođoáán nhn nhậận đưn đượợcc (recognized),

nh nghĩĩa ca cáác lc lớớp mp mááy cy cóó ccùùng nguyên lý ho i chương trìình đnh đểể gigiảải bi bàài toi toáán trên c

không n trên cùùng mng mộột mt mááy my màà không

hay hay TTnhnhậận bin biếết đưt đượợc c ??

Thay đổổi chương tr  Thay đ thay đổổi mi mááy giy giảảii thay đ

(computable)  LLớớp cp cáác hc hààm m ttíính đưnh đượợcc (computable)

 Mô hMô hìình tnh tíính to

nh toáánn (computation model), ký hi

(computation model), ký hiệệu T l

u T làà ssựự mô tmô tảả ::

hay hay TTttíính đưnh đượợc c ??

 ttấất ct cảả ccáác phc phéép top toáán sơ c

n sơ cấấp p

c ngôn ngữữ liliệệt kê đư

(enumerable) t kê đượợcc (enumerable)

 nhnhữững đng đốối tưi tượợng nng nàào co cóó ththểể ttáác đc độộng ph

ng phéép top toáán n

t kê đượợcc ??

 LLớớp cp cáác ngôn ng hay hay TTliliệệt kê đư

 ccáách th

c hiệện chương tr

n chương trìình trên m

nh trên mááyy

 So sSo sáánh hai mô h

nh : T1 mmạạnh hơn

ch thựực hi  MMộột t trưtrườờng hng hợợp riêng

p riêng (instance) c

a mô hìình lnh làà mmááy cy cụụ ththểể

nh hai mô hìình : T1 NNếếu T2u T2 nhnhậận bin biếết đưt đượợc (tc (tíính đư ththìì T1T1 ccũũng ng nhnhậận bin biếết đưt đượợc (tc (tíính đư

T2 khi : nh hơn T2 khi : t kê đượợc)c) nh đượợc, lic, liệệt kê đư c, liệệt kê đư nh đượợc, li

t kê đượợc)c)

(instance) củủa mô h nh + Chương tr

Chương trìình = M

nh = Mááyy

Mô hMô hìình +

 T1 vT1 vàà T2 T2 tương đương

tương đương (equivalent) n

(equivalent) nếếu T1

u T1 mmạạnh hơn

nh hơn T2 vT2 vàà ngư ngượợc lc lạạii

 Mô hMô hìình tnh tíính to

nh toáán Tn T đưđượợc gc gọọi li làà mmộột Tt Tmmááy y

 T1 vT1 vàà T2 lT2 làà không th

không thểể so s

so sáánh vnh vớới nhau đư

i mô u không tồồn tn tạại mô

hhìình nnh nàào o íít ra đ

t ra đủủ mmạạnh hơn mô h

i nhau đượợcc nnếếu không t nh kia nh hơn mô hìình kia

23/23/5656

24/24/5656

KhKháái ni

n (problem) i niệệm bm bàài toi toáán (problem)

n (1) MMộột st sốố vvíí ddụụ bbàài toi toáán (1)

n 1 : BBàài toi toáán 1 :

nguyên viếết trong h

t trong hệệ 1010

 MMộột t bbàài toi toáánn llàà ::  Mô tMô tảả ccáách bi

Câu hỏỏii :: SSốố nguyên đã cho c

nguyên đã cho cóó llàà ssốố nguyên t

hay không ? nguyên tốố hay không ?

ch biểểu diu diễễnn (h(hữữu hu hạạn) cn) cáác phc phầần tn tửử ccủủa ma mộột tt tậập hp hợợp hp hữữu hu hạạn hay vô h n hay vô hạạn đn đếếm đưm đượợcc

 DDữữ liliệệuu:: MMộột st sốố nguyên vi  Câu h n 2 : BBàài toi toáán 2 :

nguyên viếết trong h

t trong hệệ 1010

 MMộột pht pháát bi

nguyên nàày đưy đượợc vic viếết dưt dướới di dạạng tng tổổng cng củủa 4 s

nh phương ?? a 4 sốố bbìình phương

 KKếết qut quảả ccóó ththểể đđúúngng, ho, hoặặc c sai,sai, ttùùy viy việệc chc chọọn phn phầần tn tửử

t biểểuu liên quan đ liên quan đếến cn cáác phc phầần tn tửử ccủủa ta tậập hp hợợp np nààyy

 DDữữ liliệệu :u : MMộột st sốố nguyên vi Câu hỏỏii :: SSốố nguyên n  Câu h n 3 : BBàài toi toáán 3 :

trong Tin họọc lý thuy

ch củủa ca cáác sc sốố hhạạng trong h

ng trong hệệ 1010

Câu hỏỏii :: SSốố nguyên đã cho c

nguyên viếết dưt dướới di dạạng tng tíích c nguyên đã cho cóó llàà ssốố nguyên t

hay không ? nguyên tốố hay không ?

 BBàài toi toáánn trong Tin h  KhKháác vc vớới khi kháái ni

c lý thuyếết :t : i niệệm bm bàài toi toáán thông thư

n thông thườờng trong To ng trong Toáán hn họọcc

 DDữữ liliệệu :u : MMộột st sốố nguyên vi  Câu h n 4 : BBàài toi toáán 4 :

 KhKháác vc vớới bi bàài toi toáán hin hiểểu theo ngh

 DDữữ liliệệu :u : MMộột đt đồồ ththịị hhữữu hu hạạn G đư

n G đượợc bi

c biểểu diu diễễn bn bởởi mi mộột danh s

ch cáác đc đỉỉnh nh

c biểểu diu diễễn bn bởởi mi mộột st sốố nguyên trong h

t danh sáách c nguyên trong hệệ 1010

c cung, mỗỗi đi đỉỉnh đư

nh đượợc bi

ng đi Hamilton ((đi qua h

 Câu h

đi qua hếết tt tấất ct cảả ccáác đc đỉỉnh cnh củủaa

vvàà ccáác cung, m Câu hỏỏii :: CCóó ttồồn tn tạại đưi đườờng đi Hamilton đđồồ ththịị, m, mỗỗi đi đỉỉnh đi qua đ

nh đi qua đúúng mng mộột lt lầần) n) trong đ

đã cho không ?? trong đồồ ththịị đã cho không

u theo nghĩĩa thông d a thông dụụng ng

25/25/5656

26/26/5656

BBàài toi toáán tương

ng Post n tương ứứng Post

n (2) MMộột st sốố vvíí ddụụ bbàài toi toáán (2)

BBàài toi toáán 5 :n 5 :

 DDữữ liliệệu :u : MMộột bi

nh quy (regular expression)

s correspondence problem) (Post’’s correspondence problem) (Post DDữữ liliệệu :u : MMộột dãy h

t dãy hữữu hu hạạn cn cáác cc cặặp câu

p câu (u(u11, v, v11), (u), (u22, v, v22)..., (u

egular expression) đư đượợc xây c xây c câu t biểểu thu thứức nhc nhậận đưn đượợc tc từừ ccáác câu

ng trên mộột bt bảảng ch

t biểểu thu thứức chc chíính quy (r ng chữữ  (l(làà mmộột bi

Câu h

Câu hỏỏi :i : TTồồn tn tạại hay không m

c, phéép ghp ghéép tip tiếếp, ph

p, phéép * v

p * vàà llấấy by bùù))

)..., (ukk, v, vkk)) sao cho ,...inn sao cho

t dãy chỉỉ ssốố ii11 , i, i22 ,...i

i biểểu thu thứức đã cho ch

c đã cho chỉỉ đ địịnh ngôn ng

ng (empty nh ngôn ngữữ trtrốống (empty

 Câu h

i hay không mộột dãy ch thothoảả mãnmãn uuii11 uuii22... u... uiinn = v= vii11 vvii22... v... viinn ?? * = {a, b, c

a, b, c }}

VVíí ddụụ : : chocho * = {

ng) : chưa c

câu trảả llờời vi vềề ttíính dnh dừừng ng

n 3n+1 (b(bàài toi toáán dn dừừng) :

VVàà dãy c

p câu ::

chưa cóó câu tr { recursive } integer): integer;{ recursive }

threen(n: integer): integer;

dãy cáác cc cặặp câu ab, aba), (), (abab, ba), (

{({(ab, aba

, ba), (babbab, , baba), (), (abab, , babbab) }) }

ddựựng trên m ww* b* bởởi ci cáác phc phéép hop hoặặc, ph Câu hỏỏi :i : CCóó phphảải bi language) ? language) ? BBàài toi toáán 3n+1 function threen(n: function begin begin

babababab Cho câu : babababab Cho câu :

then 11

(n = 1) then

threen(3n+1) then threen(3n+1)

TTồồn tn tạại dãy ch

i dãy chỉỉ ssốố {3 , 2, 2, 4}

{3 , 2, 2, 4} sao cho tho

sao cho thoảả mãnmãn ::

if if (n = 1) odd(n then if if odd(n else else threen(n div 2); else threen(n div 2); else

end; end;

bab.ab.ab.ab = ba.ba.ba.bab bab.ab.ab.ab = ba.ba.ba.bab

27/27/5656

28/28/5656

MMộột st sốố khkháái ni

i niệệm khm kháácc

CCáác phc phéép top toáán trên ngôn ng

n trên ngôn ngữữ

 KKếết ht hợợp bp bàài toi toáán n PP vvớới i ngôn ng

c trưng (characteristic language)

p do đóó ccóó ththểể ááp dp dụụng cng cáác phc phéép top toáán n

ngôn ngữữ đ đặặc trưng i giảải i f(w)

(characteristic language) LLPP* * = true } f(w) = true }

Ngôn ngữữ LLPP = { = { ww D D * | * |  llờời gi Ngôn ng  BBàài toi toáán ngư

  

LLPP

**

             

ch : n ngượợc Cc CPP nhnhậận đưn đượợc tc từừ PP bbằằng cng cáách : ch biểểu diu diễễn cn cáác dc dữữ liliệệuu nguyên cáách bi t ngượợc lc lạại câu h

i giảải, hay

i, hay f(w)

= false } f(w) = false }

* | Không  llờời gi

c ngôn ngữữ, c, cáác phc phéép top toáán:n:

Ngôn ngữữ llàà mmộột tt tậập hp hợợp do đ  Ngôn ng trên tậập hp hợợp :p : trên t  ĐĐốối vi vớới ci cáác phc phầần tn tửử : :  ĐĐốối vi vớới i ngôn ng ngôn ngữữ :: Cho L1, L2 vàà L lL làà ccáác ngôn ng  Cho L1, L2 v  PhPhéép hp hợợpp

nguyên viếết trong h

 L1 L1  L2 = {w | w

L1 hoặặc w L2 = {w | w  L1 ho c w  L2}L2}

 gigiữữ nguyên c  đđặặt ngư i câu hỏỏii Ngôn ngữữ LLCCPP = { = { ww D D * | Không Ngôn ng VVíí ddụụ : B: Bàài toi toáán 1n 1’’ ::  DDữữliliệệu :u : Cho mCho mộột st sốố nguyên vi  Câu h

Câu hỏỏii :: SSốố nguyên n

t trong hệệ 1010 y không phảải li làà mmộột st sốố nguyên t

nguyên tốố ??

nguyên nàày không ph (solve) bàài toi toáán n PP nnếếu vu vàà chchỉỉ nnếếu :u :

 MMááyy gigiảải i (solve) b

y cho phéép xp xáác đc địịnh, trong m

nh, trong mộột kho

t khoảảng th

ng thờời gian h

i gian hữữu hu hạạn,n,

L1L1

L2L2

 L1 L1  L2 = {w | w

 PhPhéép hip hiệệuu

  ww *, m*, mááy cho ph nnếếu u ww LLPP hay hay ww LLCCPP Phân lớớp cp cáác bc bàài toi toáán tn tùùy theo

(complexity) y theo đđộộ phphứức tc tạạpp (complexity)

 Phân l  MMộột bt bàài toi toáán ln làà ttầầm thưm thườờngng (trivial) n

 L1 L1 –– L2 = {w | w

p giao  PhPhéép giao L2} L2 = {w | w  L1 vL1 vàà w w  L2}

(trivial) nếếu u LLPP = =  hohoặặc nc nếếu u LLCCPP = = 

 PhPhéép bp bùù

 LL’’ = {w | w

L2 = {w | w  L1 vL1 vàà w w  L2}L2}

= {w | w  L} ho L} hoặặc Lc L’’ = = * * -- L L

30/30/5656

29/29/5656

CCáác phc phéép top toáán trên ngôn ng

n trên ngôn ngữữ

CCáác phc phéép top toáán trên ngôn ng

n trên ngôn ngữữ



 PhPhéép ghp ghéép np nốối :i :

 PhPhéép bao đ



 L1L2 = = {w | w = uv, u

p bao đóóng (closure) : ng (closure) :  LL** = L= L00  LL11  ……  LLn n  …… ==

 0i

 PhPhéép ngh

 PhPhéép bao đ

ng dương :: p bao đóóng dương



 LL++ = L= L11  LL22  ……  LLn n  …… ==

L1L2 = = {w | w = uv, u  L1 vL1 vàà v v  L2}L2} p nghịịch đch đảảo :o : = {w | wRR  L}L}



1i

 NhNhậận xn xéét :t :

 LL++ = LL= LL** = L= L**LL  LL** = L= L++  { {  }}

m.nm.n

Ghép nối L1 có m Ghép nối L1 có m câu, và L2 có n câu, câu, và L2 có n câu, được ngng có ??? câu được ngng có ??? câu

 LLRR = {w | w  PhPhéép lp lũũy thy thừừa :a :  LLnn = LL= LL……L (n l  LLii = LL= LLii--1 1 = L= Lii--11L vL vớới i>0 i i>0  LL00 = {= {}}

 VVíí ddụụ ::

Khái niệm hữu hạn, vô hạn Khái niệm hữu hạn, vô hạn được hiểu như thế nào ? được hiểu như thế nào ? •Liên quan đến các phần tử •Liên quan đến các phần tử của một tập hợp : khái niệm của một tập hợp : khái niệm đếm (liệt kê) được đếm (liệt kê) được •Người ta đặt song ánh các •Người ta đặt song ánh các phần tử với số tự nhiên  phần tử với số tự nhiên  •hữu hạn ? tập hợp có n phần •hữu hạn ? tập hợp có n phần tử, nK<, bị chặn trên tử, nK<, bị chặn trên •vô hạn ? tập hợp có n phần tử •vô hạn ? tập hợp có n phần tử tuỳ ý, không bị chặn trên tuỳ ý, không bị chặn trên

ac, toe }

Cho L = { tic tic, t, tac, t

oe } khi đkhi đóó ::

 VVíí ddụụ ::

Là bản số của tích ĐêCac Là bản số của tích ĐêCac (Cartesian Product) (Cartesian Product)

Cho L = { tic tic, t, tac, t

ac, toe }

oe } khi đkhi đóó ::

 Cho L = {  LL** = {= { ,, tic, tac, toe, tictic, tictac, tictoe, tactic, tactac, tactoe, tic, tac, toe, tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toetac, toetoe, tictictic, tictictac, ... } toetic, toetac, toetoe, tictictic, tictictac, ... }

 Cho L = {  LL22 = LL= LL

ac, toetoe } = { tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toetac, toetoe } = { tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toet

L (n lầần)n)

31/31/5656

32/32/5656

VVíí ddụụ khkháác vc vềề ngôn ng

ngôn ngữữ

CCáác ngôn ng

nh quy (NNCQ) c ngôn ngữữ chchíính quy (NNCQ)

{ ., +, -- }, xay d

ngôn ngữữ chchíính quy

(Regular Languages) nh quy (Regular Languages)

  ttậập hp hợợp cp cáác c ngôn ng

= {0..9}  { ., +, }, xay dựựng cng cáác lc lớớp sp sốố :: 0..9, ., +, -- i câu trên llàà ghghéép tup tuỳỳ ý cý cáác chc chữữ ssốố 0..9, ., +,

 Cho Cho  = {0..9}  MMọọi câu trên tuy nhiên chỉỉ ghi nh tuy nhiên ch

trên  :: trên  ĐưĐượợc đc địịnh ngh

 SSốố ttựự nhiên

 LLàà ttậập hp hợợp nhp nhỏỏ nhnhấất (ch

 SSốố nguyên

 SSốố hhữữu tu tỷỷ  = { ..., 

 SSốố vô tvô tỷỷ

 Rõ rRõ rààng ng  llàà ttậập hp hợợp bp béé nhnhấất do đư

c xây dựựng tng từừ ccáác tc tậập p bao đóóngng i, ghéép vp vàà bao đ

t do đượợc xây d , {  } v} vàà { { aa } b} bởởi ci cáác phc phéép hp hộội, gh

sơ csơ cấấp p , {

ng câu làà ssốố ccóó nghnghĩĩaa nh nghĩĩa da dựựa trên c a trên cáác ngôn ng c ngôn ngữữ sơ c sơ cấấpp ), ghéép vp vàà đ đóóng lng lặặp *p * vvàà ccáác phc phéép top toáán hn hộội (i ( :: ““nhnhặặt rat ra””), gh t (chứứa a íít pht phầần tn tửử nhnhấất) ct) cáác ngôn ng c ngôn ngữữ t) nhữững câu l ghi nhậận (xn (xéét) nh = {0, 1, 2, ..., i, i+1, ... } ii0, 0,   nhiên  = {0, 1, 2, ..., i, i+1, ... } = { ..., --3, 3, --2, 2, --1, 0, 1, 2, ... } nguyên  = { ..., 1, 0, 1, 2, ... } |i||i|0, 0,   thõa mãn cáác đi thõa mãn c c điềều kiu kiệện sau n sau :: = { ..., --2/2, 2/2, --2/3, 2/3, --1/2, 0, 1/2, 2/2, ... } 1/2, 0, 1/2, 2/2, ... } |m/n| |m/n|0, 0,  1. 1.   , {, {}} 2. { aa } }   vvớới i aa   2. { 3. N3. Nếếu A, B u A, B  , th, thìì AAB, A.B v B, A.B vàà A* A*    = { ..., ..., ... } = = { ..., ..., ... } =    { ..., ..., ... } { ..., ..., ... }

33/33/5656

34/34/5656

VVíí ddụụ xây d

xây dựựng tng tậập NNCQ

p NNCQ 

nh quy (BTCQ) BiBiểểu thu thứức chc chíính quy (BTCQ)

}, nhữững ph

ng phầần tn tửử--ngôn ng

ngôn ngữữ ccóó ngay (t

ngay (tựự ccóó) :) :

 NgưNgườời ta s

i ta sửử ddụụng cng cáác c bibiểểu thu thứức chc chíính quy

 ChoCho ={={}, nh

Expressions) đ đểể bibiểểu diu diễễn cn cáác ngôn ng Expressions)

c ngôn ngữữ chchíính qui trên

Regular nh quy ( (Regular nh qui trên 

c xây dựựng BTCQ trên

ng BTCQ trên  llàà ccáác bic biểểu thu thứức đưc đượợc tc tạạo o

 NhNhữững ngôn ng

L đượợc xây d

c xây dựựng ki

quy) : u quy nạạp p ((đđệệ quy) :

 Qui tQui tắắc xây d ththàành theo c

nh theo cáác bưc bướớc quy n

c quy nạạp như sau

p như sau ::

   , , {{}}, {, {} }  ng ngôn ngữữ L đư t : NNếếu A, B

ng kiểểu quy n B, A.B vàà A* A*  

 LuLuậật :  A=A={{},},

u A, B  , th, thìì AAB, A.B v

(1)(1)

1.1. , ,  vvàà aa, v, vớới mi mọọi phi phầần tn tửử aa ccủủa a  ng BTCQ đđềều lu làà nhnhữững BTCQ hai BTCQ , 2.2. NNếếu u  vvàà  llàà hai BTCQ , ng BTCQ ththìì ((), (), (), (), ()*)* ccũũng lng làà nhnhữững BTCQ , ... nn, ... }, n b , ... }, n bấất kt kỳỳ n>0n>0 B= B= {{},}, AAB={B={, , },}, A.B={}={}={}, }, A.B={ B* = {, , , , , , , ... B* = {

ý 1 : Khi vi

 VVậậy sau bư

Chú ý 1 : Khi viết một BTCQ, có thể bỏ các dấu ngoặc đơn c đơn u ngoặặc đơn ChChúú ý 1 : c ưu tiên giảảm dm dầần : ch

n : chẳẳng hng hạạn vin viếết t aa* thay v

Khi viếết mt mộột t BTCQBTCQ, c, cóó ththểể bbỏỏ ccáác dc dấấu ngo * thay vìì ((aa)*)* theo mứức ưu tiên gi theo m theo mức ưu tiên giảm dần : chẳng hạn viết a* thay vì (a)*

, ... nn, ... } , ... } y sau bướớc nc nàày ta c y ta cóó :: , , {{}, }, {{}, {}, {}, ..., { }, ..., {, , , , , , , ...

ý 2 : CCóó ththểể viviếết t aa++bb thay v

 VVàà ccứứ ththếế titiếếp tp tụục xây d

c xây dựựng ng 

thay vìì viviếết t aabb ChChúú ý 2 : Chú ý 2 : Có thể viết a+b thay vì viết ab t 01+ 0 c ((0 (1)) + 0) cóó ththểể viviếết 01+ 0 , biểểu thu thứức ((0 (1)) + 0) c VVíí ddụụ, bi Ví dụ, biểu thức ((0 (1)) + 0) có thể viết 01+ 0

35/35/5656

36/36/5656

BiBiểểu diu diễễn ngôn ng

n ngôn ngữữ bbởởi bi

nh qui i biểểu thu thứức chc chíính qui

Bao đóóng cng củủa ba bảảng ch Bao đ

ng chữữ 

Đọc pxi

 Cho b

Cho bảảng ch

ng chữữ , k, khi đhi đóó, L = { a |

t NNCQ , L = { a | a a   } l} làà mmộột NNCQ

hay đượợc chc chỉỉ đ địịnh)nh)

Ngôn ngữữ LL(() ) đưđượợc bic biểểu diu diễễn (n (hay đư  Ngôn ng bbởởi BTCQ

theo cáác bưc bướớc quy n

c quy nạạp như sau

p như sau ::

i BTCQ  theo c

 Bao đ

Bao đóóng cng củủa L l

a L làà L* =

n câu t NNCQ cóó vô hvô hạạn câu

L* = * l* làà mmộột NNCQ c

1.1. L(L() =

) = , L(

, L() = {

) = {  }, L(a) = { a } cho

}, L(a) = { a } cho a a 

 CCóó ththểể liliệệt kê h

t kê hếết t ((đđếếm đưm đượợc) tc) tấất ct cảả ccáác câu c

c câu củủa a **

2.2. L((L((  )) = L(

)) = L() )  L(L())

* = (a + b)*  VVíí ddụụ * = (a + b)*

(2)(2)

3.3. L((L(()) = L(

)) = L()L()L())



111

4.4. L((L(()*) = L(

)*) = L()*)*

222

333

bbb

aaa

 TTừừ (1) v

(1) vàà (2) ta c

(2) ta cóó ttíính ch

t sau : nh chấất sau :

t ngôn ngữữ llàà chchíính qui

777

666

555

444

MMộột ngôn ng ngôn ngữữ đ đóó đư đượợc chc chỉỉ đ địịnh bnh bởởi mi mộột bi ngôn ng

nh qui nnếếu vu vàà chchỉỉ nnếếu (nu (nễễu, khu, khĩĩ )) nh qui t biểểu thu thứức chc chíính qui

bbbbbb

ababab

bababa

aaaaaa

ta = {a, b} thìì ta  Cho Cho  = {a, b} th  Cho  = {a, b} thì ta đã cđã cóó mmộột tht thứứ ttựự titiềền n đã có một thứ tự tiền ng trướớc bc b đđịịnh a đ nh a đứứng trư định a đứng trước b Cho hai câu w11, w, w22  Cho hai câu w  Cho hai câu w1, w2 ng trướớc c khi đkhi đóó ww11 đ đứứng trư khi đó w1 đứng trước ww2 2 khkhĩĩ |w|w11||| w| w22|| w2 khĩ |w1|| w2|

 NhNhậận xn xéét :t :

.........

888

 CCáác BTCQ c

c BTCQ cũũng tng tạạo tho thàành mnh mộột ngôn ng

aaaaaaaaa aabaabaab abaabaaba abbabbabb baabaabaa babbabbab bbabbabba bbbbbbbbb

vvìì chchúúng lng làà nhnhữững xâu ký t

ng xâu ký tựự trên b

t ngôn ngữữ trên bảảng ch

ng chữữ 

37/37/5656

38/38/5656

.........

VVíí ddụụ vvềề mmộột thu

t thuậật tot toáán kin kiểểm tra m tra câu đ

câu đốối xi xứứngng

MMộột st sốố vvíí ddụụ _ 1_ 1

 Cho b

Func PalinCheck(w: Func

PalinCheck(w: string

string): ): boolbool

ng đượợc mc mộột st sốố NNCQ trên

; i=1, l=len(w) OK = truetrue; i=1, l=len(w) OK =

ifif l>0

l>0 thenthen

whilewhile OK OK andand i<=l

i<=l andand w(i)=w(l)

w(i)=w(l) dodo i++; l

i++; l----

như sau :: NNCQ trên  như sau 4 câu LL11 ccóó 4 câu | |w|  8 8 }} LL22 ggồồm cm cáác câu c | |w| làà mmộột st sốố llẻẻ }} LL33 ggồồm cm cáác câu c

Return OKOK Return

Cho bảảng ch ng chữữ  = { a, b }, = { a, b }, ccóó ththểể xây d xây dựựng đư , a, aa, aab }} LL11 = {= {, a, aa, aab LL22 = {= { w w  ** | |w| LL33 = {= { w w  ** | |w| l LL44 = {= { w w  ** | n| naa(w) = n

...

w1 w2

wl-1 wl

i++

l--

| w = wRR }} (w) }} (w) = nbb(w) = {= {, a, ab, ba, aabb, abab, baab, ... } b, ba, aabb, abab, baab, ... } LL44 ggồồm cm cáác câu c c câu cóó ssốố chchữữ a a đđúúng bng bằằng sng sốố chchữữ bb LL55 = {= { w w  ** | w = w

, bb, aba, bab, abba, bbaaaabb, ... } , ... } ng (palindrome) c câu đốối xi xứứng (palindrome) = {= {, aa, aa, bb, aba, bab, abba, LL55 ggồồm cm cáác câu đ

Có thể có thêm các nhận xét gì về Có thể có thêm các nhận xét gì về các câu đối xúng ? các câu đối xúng ?

c câu cóó đ độộ ddàài i  88 c câu cóó đ độộ ddàài i llẻẻ Nghịch đảo câu xong thì Nghịch đảo câu xong thì cũng chính nó ! cũng chính nó ! Đọc xuôi, đọc ngược như Đọc xuôi, đọc ngược như nhau nhau Đứng bên tê, ngó bên ni, Đứng bên tê, ngó bên ni, cũng rứa cũng rứa Đứng bên ni, ngó bên tê, Đứng bên ni, ngó bên tê, cũng rứa cũng rứa Đi qua, đi lai, y chang ! Đi qua, đi lai, y chang ! Hai ký tự cách đều đầu và Hai ký tự cách đều đầu và cuối câu y chang ! cuối câu y chang !

39/39/5656

40/40/5656

MMộột st sốố vvíí ddụụ _ 2_ 2

MMộột st sốố ttíính ch

nh chấấtt

 Cho b

Cho bảảng ch

ng chữữ , , a a  , w

, w  * v* vàà L L  * *

 VVớới quy ư

i quy ướớc L(c L() l) làà NNCQ đbdb BTCQ

NNCQ đbdb BTCQ 

 Khi đKhi đóó ::

 L(L() = L(

 aakk = aa ... a = aa ... a  wwkk = ww ... w  k k = =  ...  LLkk = LL ... L = LL ... L

ngôn ngữữ ggồồm cm cáác câu l ngôn ng

c câu làà ghghéép k câu tu

p k câu tuỳỳ ý cý củủa La L

k chk chữữ a liên ti a liên tiếếpp ) = L() khi v ) khi vàà chchỉỉ khi khi  = =  = ww ... w ghghéép liên ti p k câu w p liên tiếếp k câu w NghNghĩĩa la làà :: ...  = = {{ w w  ** | |w| = k | |w| = k }} Hai BTCQ bằằng nhau c Hai BTCQ b ng nhau cùùng bi t NNCQ ng biểểu diu diễễn mn mộột NNCQ

 ĐĐểể chchứứng minh r

t k = 0 :  TrưTrườờng hng hợợp đp đặặc bic biệệt k = 0 : ng minh rằằng hai t ng hai tậập hp hợợp A v p A vàà B đã cho l ng nhau B đã cho làà bbằằng nhau

 aa00 = w= w00 = =   0 0 = L= L0 0 = { = {  }}  ChChúú ý ý { {  } }   ::

A = B A = B ccầần chn chỉỉ ra Ara AB vB vàà BBAA

t câu làà 

 còn

không cóó câu n

câu nàào !o !

 { {  } c} cóó mmộột câu l còn  không c

NghNghĩĩa a llàà ccầần CM hai chi n CM hai chiềều u ““”” vvàà ““””

41/41/5656

42/42/5656

ChChứứng minh w

ng minh w  (a(ab)b)(b(ba)a)

MMộột st sốố vvíí ddụụ _ 3_ 3

 ChChứứng minh r

ng minh rằằng :ng :

 GiGiảả ssửử w = ww = w11ww22...w...wnn  **

c BTCQ ::  CCáác BTCQ

(a*b)*  (b*a)* v (a*b)*

(b*a)* vàà **

y ra bốốn trưn trườờng hng hợợp như sau

p như sau ::

ccùùng ch

ng chỉỉ đ địịnh mnh mộột ngôn ng

nh qui ? t ngôn ngữữ chchíính qui ?

 BBằằng cng cáách ch ““ccùùng L hai BTCQ

ng L hai BTCQ”” ::

XXảảy ra b 1.1. w = aw = ann, d, do đo đóó w w  ( ( a )a )**  ( b( b**a )a )* *  (a(a**b)b)**(b(b**a)a)** 2.2. w = bw = bnn, d, do đo đóó w w  ( ( b )b )**  ( a( a**b )b )* *  (a(a**b)b)**(b(b**a)a)**

= L((a  b)*) = L(

= { a, b } b)*) = L(*) v*) vớới i  = { a, b }

(b*a)*) vàà LL22 = L((a

LL11 = L((a*b)* CCầần CM r

= L((a*b)*  (b*a)*) v n CM rằằng Lng L11 = L= L22??

 TTừừ nay v

nay vềề sau đ

sau đểể đơn gi

đơn giảản, ta vi

n, ta viếết wt w thay v

thay vìì wwL(L())

 LLờời gi

i giảải li làà CM hai chi

CM hai chiềều u ““”” vvàà ““”” ::

bao đóóngng

= (a*b)*(b*a)*

ng minh điềều ngư

(b*a)*  LL22 = = *, v*, vìì * l* làà bao đ t câu : i, ta xéét mt mộột câu :

u ngượợc lc lạại, ta x

““”” :: Rõ rRõ rààng Lng L11 = (a*b)* ““”” : : ĐĐểể chchứứng minh đi

w = ww = w11ww22...w...wnn  **

CCầần chn chứứng minh w

ng minh w  (a*b)*

(b*a)* (a*b)*(b*a)*

3.3. w chw chứứa a v w = a= a . . . w a a vàà b, kb, kếết tht thúúc bc bởởi b. Ta c . . . ab b . ab b . . . b. . b a a . . . a . . . ab b . i b. Ta cóó : : b b . . . . . bb a*ba*b (a*b)* (a*b)* a*ba*b (a*b)* (a*b)* Do đDo đóó, w , w  (a(a**b)b)**(b(b**a)a)** i a. a a vàà b vb vàà kkếết tht thúúc bc bởởi a. p 3, ta cũũng cng cóó :: 4.4. w chw chứứa a v Tương tựự trư trườờng hng hợợp 3, ta c Tương t w w  L((aL((a**b)b)**(b(b**a)a)**))

43/43/5656

44/44/5656

CCáác ngôn ng

c ngôn ngữữ phi ch

nh qui phi chíính qui

CCóó vô hvô hạạn không đ

n không đếếm đưm đượợc ngôn ng

c ngôn ngữữ

 NhNhậận xn xéét :t :

= { a, b }  = { a, b }  = { a, b }

 CCáác BTCQ l  CCáác BTCQ ch

 TTồồn tn tạại nhi nhữững ngôn ng

TTậập cp cáác NNCQ

c NNCQ 

 MMọọi ngôn ng

không thểể llàà chinh qui

i ngôn ngữữ không th  TTậập hp hợợp cp cáác ngôn ng

chinh qui :: c ngôn ngữữ vvàà ttậập hp hợợp cp cáác tc tậập hp hợợp con c

CCáác ngôn ng phi CQ c ngôn ngữữ phi CQ c BTCQ làà vô hvô hạạn đn đếếm đưm đượợcc c BTCQ chỉỉ bibiểểu diu diễễn tn tậập vô h c NNCQ, p vô hạạn đn đếếm đưm đượợc NNCQ, nhưng không biểểu diu diễễn hn hếết mt mọọi ngôn ng nhưng không bi i ngôn ngữữ ng ngôn ngữữ phi ch vvàà không c không cóó đ đủủ ccáác BTCQ đ nh qui phi chíính qui c BTCQ đểể bibiểểu diu diểển mn mọọi ngôn ng i ngôn ngữữ

* = { a, b }* * = { a, b }*

p con củủa ma mộột tt tậập hp hợợp A c

 TTậập hp hợợp cp cáác NNCQ l bbởởi mi mộột BTCQ v  SSẽẽ ccóó nhinhiềều ngôn ng

u A cóó vô hvô hạạn đn đếếm đưm đượợc c phphầần tn tửử ththìì 22AA ccóó vô hvô hạạn không đ

 CCóó 22nn ttậập hp hợợp con c p A cóó n phn phầần tn tửử  Có 2n tập hợp con của một tập hợp A có n phần tử n không đếếm đưm đượợc c phphầần tn tửử  NNếếu A c  Nếu A có vô hạn đếm được phần tử thì 2A có vô hạn không đếm được phần tử

p con củủa ma mộột t ttậập hp hợợp đp đếếm đưm đượợc (tc (tậập hp hợợp cp cáác câu) l c câu) làà không đ không đếếm đưm đượợcc i NNCQ đượợc bic biểểu diu diểển n c NNCQ làà đ đếếm đưm đượợc vc vìì mmỗỗi NNCQ đư c BTCQ làà đ đếếm đưm đượợcc t BTCQ vàà ttậập hp hợợp cp cáác BTCQ l i NNCQ u ngôn ngữữ khkháác vc vớới NNCQ

45/45/5656

46/46/5656

p con VVíí ddụụ ttậập con

VVấấn đn đềề bibiểểu diu diễễn ngôn ng

n ngôn ngữữ

 Cho A = { c

 MMộột ngôn ng

trên bảảng ch

ng chữữ  llàà ttậập hp hợợp con c

Cho A = { cụục, cc, cọọ, c, cẫẫng)ng) HHỏỏi ci cóó bao nhiêu

bao nhiêu ttậập hp hợợp con c

a A ? p con củủa A ?

 Cho L

m sao đểể bibiểểu diu diễễn hn hếết mt mọọi câu w

 TrTrảả llờời : c

i : cóó 22|A||A|=2=233 = 8 t= 8 tậập hp hợợp con c

p con củủa Aa A

Chi rứa ?

t ngôn ngữữ trên b Cho L++, l, lààm sao đ  Khi L c

p con củủa a ++ i câu wL ?L ? c câu t kê cáác câu

p con :  ĐĐóó llàà ccáác tc tậập hp hợợp con :

 Khi L c

ng}, ng, {ccụụcc} } , {c, {cọọ} } , {c, {cẫẫng},

{ r{ rỗỗng, { {{ccụụcc , c, cọọ}, {}, {ccụụcc , c, cẫẫng ng } , } , {c{cọọ,c,cẫẫng},

ng}, {{ccụục, cc, cọọ, c, cẫẫng} ng} }}

 NNếếu L g

nh chấất nht nhấất qut quáán P n

n P nàào đo đóó,,

 Lý thuy

Lý thuyếết st sốố

u L gồồm cm cáác câu c ng tân từừ đ đểể bibiểểu diu diễễnn ttíính ch

c câu cóó mmộột st sốố ttíính ch nh chấất P đ

ddùùng tân t

t P đóó

 , , , ,  vô hvô hạạn đn đếếm đưm đượợcc

* | P(w) } L = { w* | P(w) } L = { w

 NNếếu L l

u L làà NNCQ, s

NNCQ, sửử ddụụng BTCQ

nh L : ng BTCQ  chchỉỉ đ địịnh L :

 vô hvô hạạn không đ  DDựựng bng bằằng compa

n không đếếm đưm đượợc (lc (lấấp đp đầầy try trụục sc sốố)) ng compa--êke s

êke sốố

L = L()) L = L(

 L tuL tuỳỳ ý, ý, không ph

không phảải li làà NNCQ : s

NNCQ : sửử ddụụng ôtômat v

ng ôtômat vàà văn ph

văn phạạmm

-

... +

-- ÔÔtômat đo

tômat đoáán nhn nhậận câu c

n câu củủa ma mộột ngôn ng

t ngôn ngữữ

Văn phạạm sm sảản sinh ra câu cho m -- Văn ph

n sinh ra câu cho mộột ngôn ng

t ngôn ngữữ

Khi L cóó hhữữu hu hạạn câu, ch n câu, chỉỉ viviệệc lic liệệt kê c n câu, không thểể liliệệt kê h t kê hếết ct cáác câu c c câu củủa L,a L, Khi L cóó vô hvô hạạn câu, không th mmàà phphảải ti tììm cm cáách ch bibiểểu diu diễễn hn hữữu hu hạạnn ::

47/47/5656

48/48/5656

VVíí ddụụ bibiểểu diu diễễn ngôn ng

n ngôn ngữữ

VVíí ddụụ ssảản sinh ra câu c

n sinh ra câu củủa a ngôn ng

ngôn ngữữ

ngôn ngữữ trên

trên { a{ a, b, b } } đưđượợc đc địịnh ngh

nh nghĩĩa như sau

a như sau ::

 Cho L l

 Ngôn ng

n câu : Ngôn ngữữ ccóó vô hvô hạạn câu :

 LL11 = { a= { aii  i li làà mmộột st sốố nguyên t

Cho L làà ngôn ng 1. 1.   LL 2. N2. Nếếu w u w  L thL thìì awb

n sinh cáác câu c

a L như sau :: c câu củủa L như sau

}, hay nguyên tốố }, hay awb  LL = { a= { a22, a, a33, a, a55, a, a77, , ……, a, a1111, a, a1313, , …… }} 3. L không còn câu nàào kho kháác nc nữữa (ngo 3. L không còn câu n a (ngoàài 1 v i 1 vàà 2)2)

 LL22 = { a= { aiibbjj  i i  j j  0 }, hay 0 }, hay = { = { , a, ab, aab, aabb, ngôn ngữữ ggồồm cm cáác câu c

, a, ab, aab, aabb, …… }}

 Qui luQui luậật st sảản sinh c (1), L = {  }}  TTừừ (1), L = { CCoi oi  llàà w, tw, từừ (2), ta c

con a bên tráái nhi

c câu cóó mmộột dãy con a r i nhiềều hơn ho

t dãy con b, t dãy con a rồồi đi đếến mn mộột dãy con b, con b bên phảải i

u hơn hoặặc bc bằằng sng sốố con b bên ph

 LLạại do (2), ta c

 CCứứ ththếế, ta c

n L dướới di dạạng :ng :

c câu cóó ccáác cc cặặp ab tu

p ab tuỳỳ ý (0..n c

ý (0..n cặặp)p)

 L = { a

 CCóó ththểể bibiểểu diu diễễn L dư L = { aiibbii  i i  0 }0 }

(2), ta cóó câu awb = a câu awb = ab = ab, L = { , ab } b = ab, L = { , ab } llàà ngôn ng trong đóó ssốố con a bên tr trong đ i do (2), ta cóó L = { , ta cóó mmọọi câu c L = { , ab, i câu củủa L c , ab, aabb, aaabbb, ... aabb, aaabbb, ... }} a L cóó ddạạng ang aiibbii  i i  00 , ab, abab, ababab, …… }} = (ab)**  LL33 = (ab) = { = { , ab, abab, ababab, ngôn ngữữ ggồồm cm cáác câu c llàà ngôn ng

49/49/5656

50/50/5656

VVíí ddụụ đođoáán nhn nhậận mn mộột câu c

t câu củủa a ngôn ng

ngôn ngữữ

BBàài ti tậập 1p 1

c câu w ::

 GiGiảả ssửử đ địịnh ngh  CCóó ththểể thu g

ChoCho ccáác bic biểểu thu thứức chc chíính qui r, trong đóó nnếếu r = s th trong đ ChChứứng minh c

nh qui r, s, s, t,t, u r = s thìì ccóó nghnghĩĩa L(r) = L(s) a L(r) = L(s) t sau (d(dấấu + ~ d

ng minh cáác tinh ch

c tinh chấất sau

u + ~ dấấu u ):):

a ngôn ngữữ L gL gồồm cm cáác câu w nh nghĩĩa ngôn ng câu rỗỗng ng  : : w w   n w vềề câu r thu gọọn w v Thu gọọn bn bằằng cng cáách thay th

 Thu g

 VVíí ddụụ ::

 w = ab

ch thay thếế ddầần cn cáác xâu con ab c c xâu con ab củủa w b a w bởởi i  r + s = s + r 1.1. r + s = s + r (r*)* = r* 8. 8. (r*)* = r*

 w = aabbab

 Coi a, b l

u ngoặặc đơn c đơn cân bằằng nhau

Coi a, b lầần lưn lượợt lt làà ccặặp dp dấấu ngo  L gL gồồm cm cáác cc cặặp p ddấấu ngo thu đượợc tc từừ mmộột bi thu đư

 VVíí ddụụ, t, từừ bibiểểu thu thứức c (3*(x

2.2. r + (s + t) = (r + s) + t r + (s + t) = (r + s) + t r (s + t) = rs + rt 3.3. r (s + t) = rs + rt 9.9. r + r = r r + r = r r(st ) = (rs)t 10.10. r(st ) = (rs)t w = ab  L vL vìì : : abab   w = aabbab  L vL vìì : a: aababbab bab  ababab ab  abab   c đơn ( v( vàà ) :) : r = r 4.4. rr = = r = r r +  = r= r 5.5. r + * =  11.11. * = (r*s*)* = (r + s)* 12.12. (r*s*)* = (r + s)* u ngoặặc đơn cân b ng nhau không c i nhau không càài nhau r + r* = r* 13.13. r + r* = r* 6. (6. ( + r)* = r* + r)* = r* r = r = =  7.7. r = r (x + 1), th, thựực hic hiệện bn bỏỏ hhếết ct cáác c t biểểu thu thứức toc toáán hn họọc nc nàào đo đóó (3*(x  y)) y))  (x + 1) (r + s)t = rt + st 14.14. (r + s)t = rt + st ng, ta nhậận đưn đượợc câu ngo c đơn c câu ngoặặc đơn ký hiệệu tou toáán tn tửử vvàà totoáán hn hạạng, ta nh ký hi cân bằằng ng (())() cân b (())(), l, làà câu aabbab câu aabbab

51/51/5656

52/52/5656

BBàài ti tậập_2p_2

ng minh PhPhéép chp chứứng minh

2. T2. Tììm cm cáác BTCQ ch

c BTCQ chỉỉ đ địịnh nh phphầần bn bùù ccủủa ca cáác ngôn ng

c ngôn ngữữ sausau ::

Hệ quả Hệ quả

Định lý Định lý

Bổ đề Bổ đề

 (a(ab)*bb)*b  ((a((ab)(ab)(ab))*b))*

3. Cho ngôn ngữữ L trên b 3. Cho ngôn ng

ng chữữ { { a, a, b }b }

L trên bảảng ch a như sau ::

nh nghĩĩa như sau

đưđượợc đc địịnh ngh    LL

Mệnh đề Mệnh đề Pitagore: a2+b2=c2 Pitagore: a2+b2=c2

Phép CM quy nạp (induction) : Phép CM quy nạp (induction) : • Cần CM P(n), n  ? • Cần CM P(n), n  ? • Thử trường hợp P(0), P(1) • Thử trường hợp P(0), P(1) • Giả sử P(n) đúng • Giả sử P(n) đúng

Cần CM rằng P(n+1) đúng Cần CM rằng P(n+1) đúng

 NNếếu w u w  L thL thìì awb  NNếếu w u w  L thL thìì bwa

 NNếếu w1, w2

Tiên đề/Định đề Tiên đề/Định đề (công nhận) (công nhận)

Trời sinh ra thế ! Trời sinh ra thế !

awb  LL bwa  LL u w1, w2  L thL thìì w1w2 w1w2  LL ng quy nạạpp rrằằng :ng : ChChứứng minh b ng minh bằằng quy n nh nghĩĩa trên a trên khkhĩĩ L gL gồồm mm mọọi câu c i câu cóó L theo cáách đch địịnh ngh ngôn ngữữ L theo c ngôn ng ssốố chchữữ a đ a đúúng bng bằằng sng sốố chchữữ b (vi b (viếết gt gọọn nn naa(w) = n (w) ? (w) = nbb(w) ?