i ngườời !i ! ChChàào mo mọọi ngư Chào mọi người !
Hello Everyone! Hello Everyone! Hello Everyone!
nh thứức c vvàà Ôtômat Ngôn ngữữ hhìình th Ôtômat Ngôn ng Formal Language & Automata)) ((Formal Language & Automata
Bonjour Tout le Monde ! Bonjour Tout le Monde ! Bonjour Tout le Monde !
PGS.TS. Phan Huy Kháánhnh PGS.TS. Phan Huy Kh , phk@ud.edu.vn khanhph@vnn.vn, phk@ud.edu.vn khanhph@vnn.vn
他 好 !他他 好好 !!
аждый !! Привет KKаждый Привет Привет Kаждый !
Chương 11 MMởở đ đầầuu Chương 1 Mở đầu Chương
2/2/3838
Ta sTa sẽẽ hhọọc nhc nhữững bu
i mô ? ng buổổi mô ?
(cid:97)(cid:97) TrưTrườờng ĐHSP
: 05CTT12 ng ĐHSP : 05CTT12 nh) : ng quyếết đt địịnh) :
(Hai lớớp trưp trưởởng quy (Hai l (cid:86)(cid:86) ChiChiềều thu thứứ Hai hHai hààng tu
104, 13H30 ng tuầần, tn, tạại A5i A5--104, 13H30
(cid:86)(cid:86) NhNhữững bu
ng buổổi đi đầầu :u :
Hai 14/01 (cid:153)(cid:153) ChiChiềều thu thứứ Hai 14/01
To Start…
(cid:153)(cid:153) SSááng th
y, 26/01/2008, 7H00 ng thứứ BBảảy, 26/01/2008, 7H00
(cid:153)(cid:153) Sau T
t, t.29, 13H30, 25/02/08 Sau Tếết, t.29, 13H30, 25/02/08
“One picture is worth more than ten thousand words” “One picture is worth more than ten thousand words” Chinese Proverb Chinese Proverb
4/4/3838
Ghi chéép như th Ghi ch
p như thếế nnàào ?o ?
MMộột vt vàài i ““chuy
chuyệện nhn nhỏỏ”” bbắắt đt đầầu môn h
u môn họọc c
(cid:97)(cid:97) CCóó nên ghi b
c trò ? ng trên lớớp vp vàào so sổổ, v, vởở hhọọc trò ?
(cid:97)(cid:97) ThThủủ ttụục c ““chchàào ho hỏỏii”” ::
c ra khỏỏi li lớớp, không c
p, không cầần xin ph
n xin phéépp
i giảảng trên l ng slide cầần cn cóó TLTK+ c
(cid:86)(cid:86) VVàào lo lớớp mu (cid:86)(cid:86) Khi Gi
p muộộn, ho n, hoặặc ra kh ng viên (GV) hỏỏi, ci, cầần :n :
nên ghi bàài gi (cid:86)(cid:86) HHọọc bc bằằng slide c NNếếu không s nhnhà”à”
to giọọng đng đểể ccảả llớớp cp cùùng nghe đư
ng nghe đượợcc
(cid:86)(cid:86) Khi tr
(cid:97)(cid:97) Ghi bGhi bàài gi
ng trên lớớp vp vàào gio giấấy ry rờời A4i A4
Khi Giảảng viên (GV) h i rõ vàà to gi (cid:153)(cid:153) NNóói rõ v Khi trảả llờời, ci, cầần thn thựực hic hiệện ngay : n ngay : (cid:153)(cid:153) TTừừ chchốối, không bi
i, không biếết, ho
t, hoặặc trc trảả llờời tri trựực tic tiếếp vp vàào câu h
o câu hỏỏii
i giảảng trên l i môn họọc mc mộột tt tậập gip giấấy A4, c
u không sẽẽ xxảảy ra hi ch ghi hợợp lýp lý TLTK+ cáách ghi h y ra hiệện tưn tượợng ng ““THTHỪỪA TAY A TAY””, , ““đđểể tay tay ởở
(cid:97)(cid:97) ChuChuẩẩn bn bịị hhọọc :c :
ng cho buổổi di dạạyy
c thao táác tic tiếếp thp thụụ tri th t, liệệt kê, vun x
đưa ao bèèoo......””
i kiểểu u ““gigióó đưa ao b n chiếếu, u, ổổ ccắắm đim điệện...n...
u phân biệệtt y A4, cóó mmààu đu đáánh dnh dấấu phân bi tri thứức vc vàà ứứng dng dụụng :ng : t kê, vun xớớii
(cid:86)(cid:86) LLớớp sp sạạch sch sẽẽ (m(mọọi ngh (cid:86)(cid:86) NgNgồồi ti tậập trung g (cid:86)(cid:86) GiGiúúp GV chu (cid:97)(cid:97) KKếết tht thúúc môn h (cid:86)(cid:86) GiGiúúp GV d
i nghĩĩa), sa), sẵẵn sn sààng cho bu n tôi, không ngồồi ki p trung gầần tôi, không ng p GV chuẩẩn bn bịị mmààn hn hìình,nh, đ đèèn chi c môn họọc :c : p GV dọọn dn dẹẹp mp mààn hn hìình,nh, đ đèèn chi
n chiếếu, u, ổổ ccắắm đim điệện...n...
m phương phááp hp họọc tc tậập hip hiệệu quu quảả
(cid:86)(cid:86) MMỗỗi môn h Nguyên tắắc thao t (cid:97)(cid:97) Nguyên t Thu nhặặt, li (cid:86)(cid:86) Thu nh Phân loạại, si, sắắp xp xếếpp (cid:86)(cid:86) Phân lo Khoanh vùùng, gi (cid:86)(cid:86) Khoanh v (cid:86)(cid:86) ChChỉỉ đ địịnh, l (cid:86)(cid:86) VVậận dn dụụng, ho ng, hoààn thi (cid:97)(cid:97) TTììm kim kiếếm phương ph (cid:97)(cid:97) PhPháát huy c
t huy cáác gic giáác quan : m
c quan : mắắttnn, tai
, tainn, mi
, miệệngngnn, m, mũũiinn, tay
, tayn n ......
ng, giớới hi hạạnn nh, lựựa cha chọọn, tn, tììm kim kiếếmm n thiệện, ln, lààm gim giààu tri th u tri thứứcc
5/5/3838
6/6/3838
1
ĐĐểể ccóó ththểể ““ttốốc kýc ký””
MMụục đc đíích môn h
ch môn họọcc
(cid:97)(cid:97) DDùùng Sng Sửử ddụụng bng bảảng vi
t (BVT) : ng viếết tt tắắt (BVT) :
c phương phááp p
ttựự đ địịnh ngh
nh nghĩĩa cha chữữ viviếết tt tắắt ct củủa riêng m
a riêng mììnhnh
(cid:97)(cid:97) HHọọc phc phầần cung c nh thứức trong vi
n cung cấấp cơ s c trong việệc xây d
p cơ sởở totoáán hn họọc cc củủa ca cáác phương ph c ngôn ngữữ llậập trp trììnhnh c xây dựựng cng cáác ngôn ng
hhìình th
(cid:86)(cid:86) VVíí ddụụ :: ql = qu
p sinh viên hiểểu đưu đượợc nhc nhữững yng yếếu tu tốố cơ b
nh thứức như b
c như bảảng ch
ng chữữ, t, từừ vvụụng, c
cơ bảản cn củủa ma mộột t ng, cúú phphááp vp vàà
(cid:97)(cid:97) GiGiúúp sinh viên hi ngôn ngữữ hhìình th ngôn ng ngngữữ nghnghĩĩaa
(cid:97)(cid:97) HHọọc phc phầần trn trìình bnh bàày cy cáác công c
c công cụụ chchủủ yyếếu đu đểể llààm vim việệc vc vớới i văn phạạm vm vàà ôtômat, phân lo
ôtômat, phân loạại i
nh thứức lc làà văn ph
(cid:97)(cid:97) Luôn mang BVT theo m
i nơi Luôn mang BVT theo mìình, mnh, mọọi li lúúc mc mọọi nơi
c ngôn ngữữ hhìình th ccáác ngôn ng a Chomsky : ngôn ngữữ ccủủa Chomsky : ngôn ng
(cid:97)(cid:97) ChChỉỉ chchọọn ghi c
n ghi cáác ý ch
c ý chíính, hay t
nh, hay từừ khokhoáá
(cid:86)(cid:86) Ngôn ng
ql = quảản lýn lý pp = phương ph pp = phương pháápp pp+ = phân phốốii pp+ = phân ph i... = n= ngưgườời...
(cid:97)(cid:97) Không nh
Không nhấất thi
t thiếết ghi c
t ghi cảả câucâu
(cid:86)(cid:86) Ngôn ng
(cid:97)(cid:97) TTììm mm mọọi ci cáách đch đễễ vvẽẽ, thay v
, thay vìì chchỉỉ viviếết !t !
(cid:86)(cid:86) Ngôn ng
(cid:86)(cid:86) Ngôn ng
nh quy Ngôn ngữữ chchíính quy Ngôn ngữữ phi ng phi ngữữ ccảảnhnh Ngôn ngữữ ccảảm ngm ngữữ ccảảnhnh Ngôn ngữữ loloạại 0 (g i 0 (gầần gn gũũi vi vớới ngôn ng nhiên) i ngôn ngữữ ttựự nhiên)
7/7/3838
8/8/3838
KiKiếến thn thứức yêu c
ĐĐáánhnh gigiáá kkếếtt ququảả hhọọcc ttậậpp
c yêu cầầuu c tiên quyếết : To
c yêu cầầu kiu kiếến thn thứức tiên quy
t : Toáán cho Tin h
n cho Tin họọcc
(cid:97)(cid:97) Yêu c
(cid:97)(cid:97) Môn hMôn họọc yêu c (cid:86)(cid:86) Lý thuy
i dung trìình bnh bààyy trêntrên llớớpp
(cid:97)(cid:97) Tinh th
năng lựực hc họọc tc tậậpp
ng, ghi chéépp t câu hỏỏii
p internet u, truy cậập internet
i liệệu, truy c
n thiếết kht kháác :c :
Lý thuyếếtt (cid:153) Tập hợp (cid:153) Đồ thị ng minh (cid:86)(cid:86) KKỹỹ thuthuậật cht chứứng minh
Georg Cantor (1845–1918) Founder of Modern Set Theory
Yêu cầầu :u : (cid:86)(cid:86) HiHiểểu nu nộội dung tr (cid:86)(cid:86) ThThựực hic hiệện cn cáácc bbààii ttậậpp vvềề nhnhàà (cid:86)(cid:86) KhKhảả năng th năng thựực hc hàànhnh Tinh thầần thn tháái đi độộ vvàà năng l Nghe giảảng, ghi ch (cid:86)(cid:86) Nghe gi (cid:86)(cid:86) TrTrảả llờời vi vàà đ đặặt câu h Tham khảảo to tàài li (cid:86)(cid:86) Tham kh Tham gia họọc nhc nhóóm, tm, tậập thp thảảo luo luậận vn vàà thuy
thuyếết trt trìình nh
(cid:153) Qui nạp (cid:153) Phản chứng t mô phỏỏngng (cid:86)(cid:86) KKỹỹ thuthuậật mô ph (cid:97)(cid:97) CCáác kic kiếến thn thứức cc cầần thi (cid:86)(cid:86) Cơ sCơ sởở LLậập trp trììnhnh
(cid:86)(cid:86) Tham gia h (cid:86)(cid:86) ……
m tra giữữa ka kỳỳ : B: Bàài thi vi
c đòi hỏỏi mi mộột st sốố kkỹỹ năng năng :: năng đọọc hic hiểểu vu vấấn đn đềề
(cid:97)(cid:97) KiKiểểm tra gi (cid:97)(cid:97) KiKiểểmm tratra cucuốốii kkỳỳ : B: Bàài thi
i thi viếết 15t 15--30 ph i thi viviếết 60t 60--75 ph
30 phúútt 75 phúútt
(cid:97)(cid:97) Môn hMôn họọc đòi h (cid:86)(cid:86) KhKhảả năng đ (cid:86)(cid:86) TrTrìình bnh bàày diy diễễn đn đạạt vt vấấn đn đềề ((nghnghệệ thuthuậậtt !)!) (cid:86)(cid:86) KhKhảả năng th
năng thảảo luo luậận, ln, lààm vim việệc theo nh c theo nhóóm...m...
9/9/3838
10/10/3838
NNộội dung môn h
i dung môn họọcc
TTàài li
i liệệu tham kh
u tham khảảoo
nh + Bàài gi
i giảảng trên l
ng trên lớớpp
Chương 11 Chương
MMởở đ đầầuu
Gặp cô Hương, văn Gặp cô Hương, văn thư khoa CNTT thư khoa CNTT (chúng mình ?) (chúng mình ?)
(cid:97)(cid:97) GiGiááo tro trìình + B i liệệuu (cid:97)(cid:97) TTàài li
Chương 22 Chương
n (ôhh/ôh2/ô2h) Ôtômat hữữu hu hạạn (ôhh/ôh2/ô2h) Ôtômat h
(cid:86)(cid:86) NguyNguyễễn Văn Ba (cid:86)(cid:86) SM. D. Davis, E. J. Weyuker,
Chương 33 Chương
nh qui (VPCQ) Văn phạạm chm chíính qui (VPCQ) Văn ph
(cid:86)(cid:86) J. E. Hopcroft, J. D. Ulman,
, Ngôn ngữữ hhìình th n Văn Ba, Ngôn ng c, NXBKH&KT, 2002. nh thứức, NXBKH&KT, 2002. , Complexity and Computability, Complexity and
Automata Theory, ,
Chương 44 Chương
Ôtômat đẩẩy xuy xuốống (ng (ôđxôđx)) Ôtômat đ
Chương 55 Chương
MMááy Turing (MT) y Turing (MT)
Lý thuyếết t ngôn ng Introduction to Automata Theory , Addison -- Wesley, 1979 Wesley, 1979 ngôn ngữữhhìình thnh thứứccvvààôtômôtômáátt SM. D. Davis, E. J. Weyuker, Computability languages, Academic Press, 1983 , Academic Press, 1983 languages J. E. Hopcroft, J. D. Ulman, Introduction to Languages and Computation, Addison Languages and Computation Phan Huy Kháánh. nh. Lý thuy TTàài li u lưu hàành nnh nộội bi bộộ ngôn ngữữhhìình nh
(cid:86)(cid:86) Phan Huy Kh i liệệu lưu h nh lý thuyếết ôtômt ôtômáát vt vààngôn ng Văn Quân. . GiGiááo tro trìình lý thuy (cid:86)(cid:86) HHồồ Văn Quân , 2002 NXBĐHQG HCM, 2002 ththứức.c. NXBĐHQG HCM A. Salomaa, NhNhậập môn tin h ôtômat. . lý thuyếết tt tíính tonh toáánnvvààôtômat (cid:86)(cid:86) A. Salomaa, i 1992 NXB Khoa họọc Kc Kỹỹ thuthuậật, Ht, Hàà nnộội 1992 NXB Khoa h
(cid:97)(cid:97) Internet: t
m Google.com.vn, wikipedia Internet: tììm kim kiếếm Google.com.vn, wikipedia
p môn tin họọc, c, lý thuy
11/11/3838
12/12/3838
2
VVàài dòng l
i dòng lịịch sch sửử
Chương 11 Chương
MMởở đ đầầu u ☺☺
i niệệmm
“Nếu tôi cómột sốthành công nhất định trong “Nếu tôi cómột sốthành công nhất định trong toán học thì đólàvìtôi luôn thấy nórất khó” toán học thì đólàvìtôi luôn thấy nórất khó”
(cid:97)(cid:97) MMộột st sốố khkháái ni (cid:86)(cid:86) BBảảng ch
Hilbert Hilbert
(cid:97) Cantor (1845-1918) (cid:86) Lý thuyết tập hợp (cid:97) Hilbert (1862-1943) (cid:86) Toán học chặt chẽ (cid:97) Gödel (1906-1978)
(cid:86)(cid:86) Ngôn ng (cid:97)(cid:97) Mô tMô tảả ngôn ng
ngôn ngữữ
(cid:86) Lý thuyết về tính không đầy đủ
ng chữữ ((ΣΣ)) Câu (xâu) (cid:86)(cid:86) Câu (xâu) Ngôn ngữữ
(cid:97) Church, Kleene, Post, Markov, von Neumann, Turing
(cid:86)(cid:86) CCáác phc phéép top toáán (n (θθ) trên ngôn ng nh qui (BTCQ) (cid:86)(cid:86) BiBiểểu thu thứức chc chíính qui (BTCQ)
(cid:86) CM từ đlý mô (Preuves de quels théorèmes)? (cid:86) CM với thtoán mô (Avec quels algorithmes)?
(cid:86)(cid:86) CCáác ngôn ng
(ng2) ) trên ngôn ngữữ (ng2)
“Tầm nhìn ta thật ngắn “Tầm nhìn ta thật ngắn mà đã thấy bao thứ đểlàm” mà đã thấy bao thứ đểlàm”
Alan Turing Alan Turing
(cid:97) Turing (1912-1954)
(cid:86)(cid:86) VVấấn đn đềề bibiểểu diu diễễn ngôn ng
(cid:86) Máy Turing (cid:97) McCulloch, Pitts
(cid:86) Mạng nơ-ron nhân tạo
(cid:97) Chomsky
c ngôn ngữữ phi ch nh qui phi chíính qui n ngôn ngữữ
13/13/3838
14/14/3838
(cid:86) Mô hình toán học mô tả ngôn ngữ - hình thức hoá ngôn ngữ
Câu trên bảảng ch Câu trên b
BBảảng ch
ng chữữ vvàà câucâu
ng chữữ ΣΣ
(cid:97)(cid:97) BBảảng ch
(cid:97)(cid:97) 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/
(cid:97)(cid:97) 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 ΣΣ
(cid:86)(cid:86) 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)
(cid:86)(cid:86) ĐĐộộ ddàài ci củủa ma mộột câu l
ng chữữ (alphabet) : (alphabet) : (cid:86)(cid:86) 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 (cid:86)(cid:86) KKíích thư ch thướớc cc củủa ba bảảng ch ký hiệệu |u |ΣΣ|, hay Card( ký hi (cid:97)(cid:97) VVíí ddụụ mmộột st sốố bbảảng ch
ng chữữ ΣΣ ::
(cid:86)(cid:86) ĐĐộộ ddàài câu l
ng (empty word), câu rỗỗng (empty word),
(cid:86)(cid:86) MMộột câu c t câu cóó ththểể ccóó ttừừ 0 0 đđếến n ký t Câu cóó đ độộ ddàài bi bằằng 0ng 0 đư đượợc gc gọọi li làà câu r (cid:97)(cid:97) 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
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ựự n n ký tựự tutuỳỳ ýý
15/15/3838
16/16/3838
VVíí ddụụ vvềề câu trên b
câu trên bảảng ch
c câu PhPhéép ghp ghéép tip tiếếp cp cáác câu
ng chữữ ΣΣ
(cid:97)(cid:97) Cho hai câu u v
(cid:97)(cid:97) VVíí ddụụ
Cho hai câu u vàà v trên (cid:86)(cid:86) PhPhéép p ghghéép tip tiếếpp (Concatenation) c
v trên ΣΣ (Concatenation) củủa u v
(cid:86)(cid:86) NghNghĩĩa la làà câu
{ 0, 1 } { 0, 1 }
(cid:153)(cid:153) u đgl l
(cid:153)(cid:153) rrồồi đi đếến v l
{ { aa....z } ....z } { 0, ..., 7, ♠♠, , ♣♣, , ♦♦, , ♥♥ } } { 0, ..., 7, ASCII ASCII
(cid:86)(cid:86) TrưTrườờng hng hợợp câu w = xuy l (infix) củủa wa w
aa, , abab, zt, computer , zt, computer , 1234, ♣♠♣♠ 44♣♣33♦♦22♠♠, 1234, 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
(cid:97)(cid:97) Cho mCho mộột câu w c
t câu w cóó ccóó | |w|=n,
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 wwggồồ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,,
mmộột ký t (cid:86)(cid:86) VVíí ddụụ câu w=aaabbaabbba c
u đgl trung t u đgl (cid:86)(cid:86) NgưNgườời ta còn g trung tốố (infix) c 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ựự ::
(cid:86)(cid:86) 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
17/17/3838
18/18/3838
3
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ữữ
(cid:97)(cid:97) MMộột ngôn ng
t ngôn ngữữ hhìình th
nh thứức (nc (nóói gi gọọn ngôn ng
n ngôn ngữữ) :) :
(cid:97)(cid:97) 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 (cid:86)(cid:86) 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 ΣΣ
(cid:97)(cid:97) VVíí ddụụ ::
c xâu trên bảảng ch
ng chữữ ΣΣ
(cid:97)(cid:97) PhPhéép p ĐĐảảo ngư (cid:86)(cid:86) LLàà câu (cid:86)(cid:86) Rõ rRõ rààng ng εεRR = = εε (cid:86)(cid:86) 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 (cid:97)(cid:97) 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)
(cid:86)(cid:86) ΣΣ** 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 (cid:86)(cid:86) ΣΣ++ 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 (cid:153)(cid:153) ΣΣ++ = = ΣΣ** -- εε (cid:153)(cid:153) ∅∅ llàà ngôn ng
w đgl câu đốối xi xứứng : OMO, akitOM Otika... ng : OMO, akitOMOtika...
(cid:86)(cid:86) VVíí ddụụ
(cid:86)(cid:86) wwnn = ww= ww……w (n l (cid:86)(cid:86) 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)
(cid:153)(cid:153) L1 = {a, ab, abb, bba, bbb} l (cid:153)(cid:153) L2 = {(ab)
L1 = {a, ab, abb, bba, bbb} làà ngôn ng L2 = {(ab)nn | n > 0} l
ngôn ngữữhhữữu hu hạạnntrên {a, b} trên {a, b} trên {a, b} ngôn ngữữvô hvô hạạnntrên {a, b}
| n > 0} làà ngôn ng
w (n lầần)n)
19/19/3838
20/20/3838
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ữữ
(cid:97)(cid:97) PhPhéép ghp ghéép np nốối :i :
p do đóó ccóó ththểể ááp dp dụụng cng cáác phc phéép top toáán n
(cid:86)(cid:86) L1L2 = = {w | w = uv, u
∈ ∉∈∈ ∉∉
(cid:97)(cid:97) PhPhéép ngh
∩∩ ∪∪ ⊂⊂ ⊆⊆ ⊄⊄ ⊃⊃ ⊇⊇ ∩ ∪ ⊂ ⊆ ⊄ ⊃ ⊇
c ngôn ngữữ, c, cáác phc phéép top toáán:n:
(cid:86)(cid:86) LLRR = {w | w (cid:97)(cid:97) PhPhéép lp lũũy thy thừừa :a :
Ngôn ngữữ llàà mmộột tt tậập hp hợợp do đ (cid:97)(cid:97) Ngôn ng trên tậập hp hợợp :p : trên t (cid:86)(cid:86) ĐĐốối vi vớới ci cáác phc phầần tn tửử : : (cid:86)(cid:86) ĐĐốối vi vớới i ngôn ng ngôn ngữữ :: Cho L1, L2 vàà L lL làà ccáác ngôn ng (cid:97)(cid:97) Cho L1, L2 v (cid:86)(cid:86) PhPhéép hp hợợpp
L1L2 = = {w | w = uv, u ∈∈ L1 vL1 vàà v v ∈∈ L2}L2} p nghịịch đch đảảo :o : = {w | wRR ∈∈ L}L}
(cid:153)(cid:153) L1 L1 ∪∪ L2 = {w | w
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
(cid:86)(cid:86) LLnn = LL= LL……L (n l (cid:86)(cid:86) LLii = LL= LLii--1 1 = L= Lii--11L vL vớới i>0 i i>0 (cid:86)(cid:86) LL00 = {= {εε}}
L1L1
L2L2
(cid:153)(cid:153) L1 L1 ∩∩ L2 = {w | w
(cid:97)(cid:97) VVíí ddụụ ::
Là bản số của tích ĐêCac Là bản số của tích ĐêCac (Cartesian Product) (Cartesian Product)
(cid:86)(cid:86) PhPhéép hip hiệệuu
Cho L = { tic tic, t, tac, t
ac, toe }
oe } khi đkhi đóó ::
(cid:153)(cid:153) L1 L1 –– L2 = {w | w
L (n lầần)n) L1 hoặặc w L2 = {w | w ∈∈ L1 ho c w ∈∈ L2}L2} p giao (cid:86)(cid:86) PhPhéép giao L2} L2 = {w | w ∈∈ L1 vL1 vàà w w ∈∈ L2}
(cid:86)(cid:86) Cho L = { (cid:86)(cid:86) LL22 = LL= LL
LL
(cid:86)(cid:86) PhPhéép bp bùù
ac, toetoe } = { tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toetac, toetoe } = { tictic, tictac, tictoe, tactic, tactac, tactoe, toetic, toet
(cid:153)(cid:153) LL’’ = {w | w
L2 = {w | w ∈∈ L1 vL1 vàà w w ∉∉ L2}L2}
= {w | w ∉∉ L} ho L} hoặặc Lc L’’ = = ΣΣ* * -- L L
21/21/3838
22/22/3838
CCáác phc phéép top toáán trên ngôn ng
n trên ngôn ngữữ
CCáác ngôn ng
nh quy (NNCQ) c ngôn ngữữ chchíính quy (NNCQ)
∞
(cid:97)(cid:97) PhPhéép bao đ
(Regular Languages) ngôn ngữữchchíính quynh quy(Regular Languages)
(cid:97)(cid:97) ℜℜ ttậập hp hợợp cp cáác c ngôn ng
iL
p bao đóóng (closure) : ng (closure) : (cid:86)(cid:86) LL** = L= L00 ∪∪ LL11 ∪∪ …… ∪∪ LLn n ∪∪ …… ==
U
=0i
(cid:97)(cid:97) PhPhéép bao đ
ng dương :: p bao đóóng dương
∞
trên ΣΣ :: trên (cid:86)(cid:86) ĐưĐượợc đc địịnh ngh
iL
(cid:86)(cid:86) LL++ = L= L11 ∪∪ LL22 ∪∪ …… ∪∪ LLn n ∪∪ …… ==
nh nghĩĩa da dựựa trên c c ngôn ngữữ sơ c sơ cấấpp a trên cáác ngôn ng i, ghéép vp vàà đ đóóng lng lặặp *p * vvàà ccáác phc phéép top toáán hn hộội, gh
U
=1i
(cid:86)(cid:86) LLàà ttậập hp hợợp nhp nhỏỏ nhnhấất (ch
(cid:97)(cid:97) NhNhậận xn xéét :t :
(cid:86)(cid:86) LL++ = LL= LL** = L= L**LL (cid:86)(cid:86) LL** = L= L++ ∪∪ { { εε }}
(cid:97)(cid:97) VVíí ddụụ ::
t (chứứa a íít pht phầần tn tửử nhnhấất) ct) cáác ngôn ng c ngôn ngữữ c điềều kiu kiệện sau n sau ::
ac, toe }
Cho L = { tic tic, t, tac, t
oe } khi đkhi đóó ::
(cid:97)(cid:97) Rõ rRõ rààng ng ℜℜ llàà ttậập hp hợợp bp béé nhnhấất do đư
(cid:86)(cid:86) Cho L = { (cid:86)(cid:86) 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, ... }
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 ∅∅, {
thõa mãn cáác đi thõa mãn c 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* ∈∈ ℜℜ
23/23/3838
24/24/3838
4
nh quy (BTCQ) BiBiểểu thu thứức chc chíính quy (BTCQ)
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
(cid:97)(cid:97) NgưNgườời ta s
hay đượợc chc chỉỉ đ địịnh)nh)
Expressions) đ đểể bibiểểu diu diễễn cn cáác ngôn ng Expressions)
c ngôn ngữữ chchíính qui trên
Regular i ta sửử ddụụng cng cáác c bibiểểu thu thứức chc chíính quynh quy ( (Regular nh qui trên ΣΣ
Ngôn ngữữ LL((ξξ) ) đưđượợc bic biểểu diu diễễn (n (hay đư (cid:97)(cid:97) 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
1.1. L(L(∅∅) =
) = ∅∅, L(
, L(εε) = {
) = { εε }, L(a) = { a } cho
}, L(a) = { a } cho ∀∀a a ∈Σ∈Σ
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
(cid:97)(cid:97) 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 ::
2.2. L((L((αα ∪∪ ββ)) = L(
)) = L(αα) ) ∪∪ L(L(ββ))
(2)(2)
3.3. L((L((αβαβ)) = L(
)) = L(αα)L()L(ββ))
4.4. L((L((αα)*) = L(
)*) = L(αα)*)*
(1)(1)
(cid:97)(cid:97) TTừừ (1) v
(1) vàà (2) ta c
(2) ta cóó ttíính ch
t sau : nh chấất sau :
1.1. ∅∅, , εε vvàà aa, v, vớới mi mọọi phi phầần tn tửử aaccủủ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
t ngôn ngữữ llàà chchíính qui n
nh qui nếếu vu vàà chchỉỉ nnếếuu
MMộột ngôn ng ngôn ngữữ đ đóó đư đượợc chc chỉỉ đ địịnh bnh bởởi mi mộột bi ngôn ng
nh qui t biểểu thu thứức chc chíính qui
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)*
(cid:97)(cid:97) NhNhậận xn xéét :t :
(cid:86)(cid:86) CCáác BTCQ c
c BTCQ cũũng tng tạạo tho thàành mnh mộột ngôn ng
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 :ý 1 : Khi vi c ưu tiên giảảm dm dầần : ch thay vìì viviếết t aa∪∪bb ChChúúý 2 :ý 2 : CCóó ththểể viviếết t aa++bbthay v Chúý 2 : Có thể viết a+bthay 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
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ữữ ΣΣ
25/25/3838
26/26/3838
Bao đóóng cng củủa ba bảảng ch Bao đ
MMộột st sốố vvíí ddụụ _ 1_ 1
ng chữữ ΣΣ
(cid:97)(cid:97) Cho b
(cid:97)(cid:97) Cho b
Cho bảảng ch
ng chữữ ΣΣ, k, khi đhi đóó, L = { a |
t NNCQ , L = { a | ∀∀a a ∈∈ ΣΣ } l} làà mmộột NNCQ
Cho bảảng ch ccóó ththểể xây d
ng chữữ ΣΣ = { a, b }, = { a, b }, xây dựựng đư
ng đượợc mc mộột st sốố NNCQ trên
như sau :: NNCQ trên ΣΣ như sau
(cid:97)(cid:97) 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
(cid:97)(cid:97) 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 ΣΣ**
* = (a+ b)* (cid:86)(cid:86) VVíí ddụụ ΣΣ* = (a+ b)*
εεε
111
333
222
bbb
aaa
| |w| ≤≤ 8 8 }} c câu cóó đ độộ ddàài i ≤≤ 88 c câu cóó đ độộ ddàài i llẻẻ , a, aa, aab }} LL11 = {= {εε, a, aa, aab LL22 = {= { w w ∈∈ ΣΣ** | |w| LL33 = {= { w w ∈∈ ΣΣ** | |w| l 4 câu LL11 ccóó 4 câu 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 LL44 = {= { w w ∈∈ ΣΣ** | n| naa(w) = n
777
666
555
444
bbbbbb
ababab
bababa
aaaaaa
.........
888
aaaaaaaaa aabaabaab abaabaaba abbabbabb baabaabaa babbabbab bbabbabba bbbbbbbbb
c câu cóó ssốố chchữữ a đ a đúúng bng bằằng sng sốố chchữữ bb (w) = nbb(w) (w) }} b, ba, aabb, abab, baab, ... } = {= {εε, a, ab, ba, aabb, abab, baab, ... } LL44 ggồồm cm cáác câu c | w = wRR }} LL55 = {= { w w ∈∈ ΣΣ** | w = w
.........
.........
, bb, aba, bab, abba, baab, ... } = {= {εε, aa, aa, bb, aba, bab, abba, baab, ... } ng (palindrome) c câu đốối xi xứứng (palindrome) LL55 ggồồm cm cáác câu đ
27/27/3838
28/28/3838
MMộột st sốố vvíí ddụụ _ 2_ 2
MMộột st sốố ttíính ch
nh chấấtt
(cid:97)(cid:97) Cho b
Cho bảảng ch
ng chữữ ΣΣ, , a a ∈∈ ΣΣ, w
, w ∈∈ ΣΣ* v* vàà L L ⊆⊆ ΣΣ* *
(cid:97)(cid:97) VVớới quy ư
i quy ướớc L(c L(αα) l) làà NNCQ đbdb BTCQ
NNCQ đbdb BTCQ αα
(cid:97)(cid:97) Khi đKhi đóó ::
(cid:97)(cid:97) Khi đKhi đóó ::
(cid:86)(cid:86) L(L(αα) = L( NghNghĩĩa la làà ::
(cid:86)(cid:86) aakk = aa ... a = aa ... a (cid:86)(cid:86) wwkk = ww ... w (cid:86)(cid:86) ΣΣk k = = ΣΣΣΣ ... (cid:86)(cid:86) LLkk = LL ... L = LL ... L
c câu làà ghghéép k câu tu
p k câu tuỳỳ ý cý củủa La L
ngôn ngữữ ggồồm cm cáác câu l ngôn ng t k = 0 : (cid:97)(cid:97) TrưTrườờng hng hợợp đp đặặc bic biệệt k = 0 :
(cid:86)(cid:86) ĐĐểể chchứứng minh r
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 ... ΣΣ = = {{ 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
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
(cid:86)(cid:86) aa00 = w= w00 = = εε (cid:86)(cid:86) ΣΣ0 0 = L= L0 0 = { = { εε }} (cid:97)(cid:97) ChChúú ý ý { { εε } } ≠≠ ∅∅ ::
A = B A = B ccầần chn chỉỉ ra Ara A⊂⊂B vB vàà BB⊂⊂AA
t câu làà εε
không cóó câu n
câu nàào !o !
(cid:86)(cid:86) { { εε } c} cóó mmộột câu l còn ∅∅ không c (cid:86)(cid:86) còn
NghNghĩĩa a llàà ccầần CM hai chi n CM hai chiềều u ““⊂⊂”” vvàà ““⊃⊃””
29/29/3838
30/30/3838
5
ChChứứng minh w
MMộột st sốố vvíí ddụụ _ 3_ 3
ng minh w ∈∈ (a(a**b)b)**∪∪(b(b**a)a)**
(cid:97)(cid:97) GiGiảả ssửử w = ww = w11ww22...w...wnn ∈∈ ΣΣ**
ng minh rằằng :ng : L((a*b)* ∪∪ (b*a)*) = L((a
y ra bốốn trưn trườờng hng hợợp như sau
p như sau ::
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)**
(cid:97)(cid:97) ChChứứng minh r (b*a)*) = L((a ∪∪ b)*) = (cid:86)(cid:86) L((a*b)* c BTCQ :: (cid:86)(cid:86) NghNghĩĩa la làà ccáác BTCQ (b*a)* vàà ΣΣ** (a*b)* ∪∪ (b*a)* v (a*b)* ccùùng ch
= { a, b } b)*) = ΣΣ* v* vớới i ΣΣ = { a, b }
ng chỉỉ đ địịnh mnh mộột ngôn ng nh qui t ngôn ngữữ chchíính qui
(cid:97)(cid:97) TTừừ nay v
nay vềề sau đ
sau đểể đơn gi
đơn giảản, ta vi
n, ta viếết w
t w ∈∈ αα thay v
thay vìì w w ∈∈ L(L(αα))
(cid:97)(cid:97) LLờời gi
CM hai chiềều u ““⊂⊂”” vvàà ““⊃⊃”” :: ng (a*b)*∪∪(b*a)* ng minh điềều ngư
i giảải li làà CM hai chi ““⊂⊂”” :: Rõ rRõ rààng (a*b)* ““⊃⊃”” : : ĐĐểể chchứứng minh đi
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)** (b*a)* ⊂⊂ ΣΣ* v* vìì ΣΣ* l* làà bao đ i a. a a vàà b vb vàà kkếết tht thúúc bc bởởi a. u ngượợc lc lạại, ta x bao đóóngng t câu : i, ta xéét mt mộột câu : p 3, ta cũũng cng cóó :: w = ww = w11ww22...w...wnn ∈∈ ΣΣ** 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)**)) CCầần chn chứứng minh w ng minh w ∈∈ (a*b)* (b*a)* (a*b)*∪∪(b*a)*
31/31/3838
32/32/3838
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ữữ
(cid:97)(cid:97) NhNhậận xn xéét :t :
(cid:86)(cid:86) CCáác BTCQ l
(cid:86)(cid:86) CCáác BTCQ ch
(cid:86)(cid:86) TTồồn tn tạại nhi nhữững ngôn ng
TTậập cp cáác NNCQ
c NNCQ ℜℜ
= { a, b } ΣΣ = { a, b } Σ = { a, b } c BTCQ làà vô hvô hạạn đn đếếm đưm đượợcc CCáác ngôn ng phi CQ c ngôn ngữữ phi CQ 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 nh qui phi chíính qui c BTCQ đểể bibiểểu diu diểển mn mọọi ngôn ng i ngôn ngữữ không cóó đ đủủ ccáác BTCQ đ
chinh qui :: không thểể llàà chinh qui c ngôn ngữữ vvàà ttậập hp hợợp cp cáác tc tậập hp hợợp con c
* = { a, b }* ΣΣ* = { a, b }*
(cid:86)(cid:86) TTậập hp hợợp cp cáác NNCQ l bbởởi mi mộột BTCQ v
p con củủa ma mộột tt tậập hp hợợp A c
(cid:86)(cid:86) 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 đ
(cid:86)(cid:86) CCóó 22nn ttậập hp hợợp con c p A cóó n phn phầần tn tửử (cid:86) 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ửử (cid:86)(cid:86) NNếếu A c (cid:86) 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ử
vvàà không c i ngôn ngữữ không th (cid:97)(cid:97) MMọọi ngôn ng (cid:86)(cid:86) TTậập hp hợợp cp cáác ngôn ng 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
33/33/3838
34/34/3838
VVấấn đn đềề bibiểểu diu diễễn ngôn ng
n ngôn ngữữ
VVíí ddụụ bibiểểu diu diễễn ngôn ng
n ngôn ngữữ
(cid:97)(cid:97) MMộột ngôn ng
trên bảảng ch
(cid:97)(cid:97) Ngôn ng
n câu : Ngôn ngữữ ccóó vô hvô hạạn câu :
ng chữữ ΣΣ llàà ttậập hp hợợp con c m sao đểể bibiểểu diu diễễn hn hếết mt mọọi câu w
(cid:97)(cid:97) Cho L
(cid:86)(cid:86) LL11 = { a= { aii ⏐⏐ i li làà mmộột st sốố nguyên t
t ngôn ngữữ trên b Cho L⊆Σ⊆Σ++, l, lààm sao đ (cid:86)(cid:86) Khi L c
p con củủa a ΣΣ++ i câu w∈∈L ?L ? c câu t kê cáác câu
(cid:86)(cid:86) Khi L c
(cid:153)(cid:153) NNếếu L g
nh chấất nht nhấất qut quáán P n
n P nàào đo đóó,,
(cid:86)(cid:86) 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
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 đóó
}, hay nguyên tốố }, hay Khi L cóó hhữữu hu hạạn câu, ch n câu, chỉỉ viviệệc lic liệệt kê c = { a= { a22, a, a33, a, a55, a, a77, , ……, a, a1111, a, a1313, , …… }} 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 bi n câu, không thểể liliệệt kê h ch biểểu diu diễễn hn hữữu hu hạạn :n : , a, ab, aab, aabb, …… }}
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 a rồồi đi đếến mn mộột dãy con b, 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
* | P(w) } L = { w∈Σ∈Σ* | P(w) } L = { w u L làà NNCQ, s
(cid:153)(cid:153) NNếếu L l
NNCQ, sửử ddụụng BTCQ
nh L : ng BTCQ αα chchỉỉ đ địịnh L :
L = L(αα)) L = L(
llàà ngôn ng trong đóó ssốố con a bên tr trong đ
(cid:153)(cid:153) 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
c câu cóó ccáác cc cặặp ab tu
p ab tuỳỳ ý (0..n c
ý (0..n cặặp)p)
-- ÔÔ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ữữ
, ab, abab, ababab, …… }} = (ab)** (cid:86)(cid:86) LL33 = (ab) = { = { εε, ab, abab, ababab, ngôn ngữữ ggồồm cm cáác câu c llàà ngôn ng
35/35/3838
36/36/3838
6
VVíí ddụụ ssảản sinh ra câu c
n sinh ra câu củủa a ngôn ng
ngôn ngữữ
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ữữ
trên { a{ a, b, b } } đưđượợc đc địịnh ngh
nh nghĩĩa như sau
a như sau ::
ngôn ngữữ trên
c câu w∈∈Σ∗Σ∗ ::
(cid:97)(cid:97) GiGiảả ssửử đ địịnh ngh (cid:86)(cid:86) CCóó ththểể thu g
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
(cid:86)(cid:86) Thu g
(cid:97)(cid:97) VVíí ddụụ ::
Cho L làà ngôn ng (cid:97)(cid:97) Cho L l 1. 1. εε ∈∈ LL 2. N2. Nếếu w u w ∈∈ L thL thìì awb 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 n sinh cáác câu c
(cid:86)(cid:86) w = ab
Thu gọọn bn bằằng cng cáách thay th ch thay thếế ddầần cn cáác xâu con ab c c xâu con ab củủa w b awb ∈∈ LL a w bởởi i εε i 1 vàà 2)2) a (ngoàài 1 v a L như sau :: c câu củủa L như sau
(cid:97)(cid:97) Coi a, b l
(cid:97)(cid:97) Qui luQui luậật st sảản sinh c (1), L = { εε }} (cid:86)(cid:86) TTừừ (1), L = { CCoi oi εε llàà w, tw, từừ (2), ta c i do (2), ta cóó L = {
(cid:86)(cid:86) LLạại do (2), ta c
(cid:86)(cid:86) CCứứ ththếế, ta c
(cid:86)(cid:86) VVíí ddụụ, t, từừ bibiểểu thu thứức c (3*(x
(cid:86)(cid:86) L = { a
(cid:97)(cid:97) CCóó ththểể bibiểểu diu diễễn L dư L = { aiibbii ⏐⏐ ∀∀i i ≥≥ 0 }0 }
(2), ta cóó câu awb = a , ab } b = ab, L = { εε, ab } abab ⇒⇒ ab ab ⇒⇒ εε c đơn ( v( vàà ) :) : u ngoặặc đơn cân b ng nhau không c i nhau không càài nhau , ta cóó mmọọi câu c câu awb = aεεb = ab, L = { , ab, aabb, aaabbb, ... aabb, aaabbb, ... }} a L cóó ddạạng ang aiibbii ⏐⏐ ∀∀i i ≥≥ 00 w = ab ∈∈ L vL vìì : ab ⇒⇒ εε : ab : aabbab ⇒⇒ abab w = aabbab ∈∈ L vL vìì : aabbab (cid:86)(cid:86) w = aabbab u ngoặặc đơn Coi a, b lầần lưn lượợt lt làà ccặặp dp dấấu ngo (cid:86)(cid:86) L gL gồồm cm cáác cc cặặp p ddấấu ngo c đơn cân bằằng nhau thu đượợc tc từừ mmộột bi thu đư L = { εε, ab, i câu củủa L c n L dướới di dạạng :ng : (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) ng, ta nhậận đưn đượợc câu ngo c đơn c câu ngoặặc đơn (())(), l, làà câu aabbab câu aabbab 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
