Ta có thể dùng biểu thức chính qui để biểu diễn ngôn ngữ
Định nghĩa
Cho Σlà một bộ chữ cái. Biểu thức chính quy trên Σđược định nghĩa một cách đệ quy như sau:
1) ∅là biểu thức chính quy ký hiệu cho tập rỗng
2) εlà biểu thức chính quy ký hiệu cho tập {ε}
3) ∀a ∈ Σ, alà biểu thức chính quy ký hiệu cho tập {a}
4) Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s), (rs)và( r*)là các biểu thức chính quy ký hiệu cho các tập hợp R ∪S, RS, R* tương ứng.
Các phép toán trong ngoặc được thực hiện trước, sau đó là: phép bao đóng, phép nối kết, phép hợp.
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 32/44
Ví dụ
00là biểu thức chính quy biểu diễn tập {00}.
(0+1)*ký hiệu cho tập hợp tất cả các chuỗi số 0 và số 1, kể cả chuỗi rỗng = {ε, 0, 1, 00, 01, 10, 11, 010, 011, 0010 ..}
(0+1)*00(0+1)*ký hiệu cho tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 liên tiếp. = {00, 000, 100, 0000, 0001, 1000, 1001, 011001,..}
(1+10)* ký hiệu cho tất cả các chuỗi 0, 1 bắt đầu bằng số 1 và không có hai số 0 liên tiếp = {ε, 1, 10, 11, 1010, 111, 101010, ... }
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 33/44
Ví dụ
(0+1)*011 = ?.
0*1*0*= ?
Một chuỗi tên biếnđược gọi là hợp lệ trong một chương trình Pascal nếu nhưnó bắtđầu bằng ít nhất một chữcái và theo sauđó là các chữcái, số, ký hiệu gạch dưới(underline) hoặc một vài ký hiệu cho phép khác trên bàn phím máy tính.
r = (A + …+ Z + a + … + z) (A + …+ Z + a + … + z + 0 + … + 9 + _ + … )*
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 34/44
Ví dụ
Biểu thức chính quy ký hiệu cho tập hợp các sốnguyên trong ngôn ngữlập trình Pascal :
Một chuỗi sốnguyên trong một chương trình Pascal có thểbắt đầu bằng dấu âm (-) hoặc dấu dương (+) hay không chứa ký hiệu dấu, và theo sauđó là một chuỗi các ký hiệu sốvới ít nhất là một số.
Biểu thức chính quy có dạng nhưsau :
r = ( '+' + '-' + 'ε') ( 0 + … + 9) (0 + … +9 )*
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 35/44
VII. Sự tương đương giữa biểu thức chinh qui và NFAεεεε
ĐỊNH LÝ Nếu r là biểu thức chính quy thì tồn tại một NFAεεεε chấp nhận L(r).
Giải thuật
Phân tích biểu thức chính qui thành từng phần và áp dụng các qui tắc sau để xây dựng NFAεtương đương
Qui tắc cơ bản:
Cho biểu thức chính qui: r = a ∀a ∈ Σ
NFAεtương đương:
Start a
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 36/44
Giải thuật
Quy tắc cho phép hợp: r = r1+ r2
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 37/44 Quy tắc cho phép nối kết: r = r1r2
εεεε
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 38/44
Quy tắc cho phép bao đóng: r = r1*
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 39/44
Ví dụ
Xây dựng NFAεchấp nhận lớp ngôn ngữ được biểu diễn bởi biểu thức chính quy r = 01* + 1.
Giải
L(r) = { 0, 01, 011, 0111, 01111, 011111, … } là tập ngôn ngữ chứa các bitđơn 0, 1 bắtđầu bằng bit 0, theo sau là một chuỗi bit 1 vớiđộdài tuỳý.
Theo quy luật thứtự ưu tiên, biểu thức 01* + 1 thực chất là (0(1*)) + 1, vì vậy nó có dạngr1+r2vớir1= 01* vàr2= 1.
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 40/44 NFAεcho r2= 1:
NFAεcho r1= 01*: tách r1 = r3r4trong đó r3= 0; r4= 1*
NFAεcho r3= 0 :
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 41/44
NFAεcho r4= 1*:
Ta viết r4= r5*, trong đó r5= 1.
NFAεcho r5= 1
NFAεcho r4= r5* = 1* nhưsau :
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 42/44
NFAεcho r1= r3r4= 01* như sau :
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 43/44 NFAεcho r = r1+ r2= 01*+ 1 như sau :
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 44/44
Bài tập
1. Xây dựng NFAεchấp nhận lớp ngôn ngữ được biểu diễn bởi biểu thức chính quy:
a. r1= (00 + 1)*
b. r2= ((0 + 1)0*)*
2. Cho bảng chữcái {a,b}, tìm chuỗi cóđộdài ngắn nhất không thuộc ngôn ngữcủa biểu thức chính qui r = a*(ab)*b*.
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 45/44
Bài tập
3. Cho hai biểu thức chính qui:
r1 = a* + b*, r2 = ab* + ba* + b*a + (a*b)*
a. Tìm một chuỗi thuộc L(r2), những không thuộc L(r1) b. Tìm các chuỗi thuộc cảL(r1) và L(r2)
4. Tìm biểu thức chính qui biểu diễn ngôn ngữtrên bảng chữ cái {a,b}, mà ngôn ngữ đóđượcđịnh nghĩa một cáchđệqui nhưsau:
ε ∈L
Nếu x∈L , thì aabx∈L and xbb∈L .
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 46/44
Bài tập
5. NFAεđọc vào một ký hiệu thì chỉcó duy nhất 1 khảnăngđể chuyển.(đúng/sai)
6. NFA cho phép chuyển sang trạng thái khác khiđọc vàoε.
(đúng/sai)
7.ε-closure(q) có thểchứa hoặc không chứa q. (đúng/sai) 8. NFA là bộgồm 4 thành phần(đúng/sai)
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 47/44
Phần mềm JFLAP
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 2/13
Nội dung Nội dung
Văn phạm chính qui
Đồ hình biểu diễn văn phạm chính qui mẫu
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 3/13
Giới thiệu Giới thiệu
Lớp ngôn ngữ được chấp nhận bởiôtômát hữu hạnđược gọi là ngôn ngữchính quy
Lớpngôn ngữchính quicó thể được biễu diễn bởibiểu thức chính quy.
Chương này giới thiệu một cách khácđểmô tảngôn ngữchính quy thông qua cơchếsản sinh ngôn ngữ-đó làvăn phạm chính quy.
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 4/13 Trong đó với A, B ∈Δ và a ∈ Σlà một chuỗi các ký hiệu kết thúc. (có
thể rỗng).
Một văn phạm được gọi là văn phạm chính quy nếu nó thuộc dạng văn phạm tuyến tính trái hoặc tuyến tính phải.
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 5/13
Ví dụ
Cho văn phạm G({a,b}, {S}, P1, S) với các luật sinh như sau:
P1={ SaS | a } là văn phạm tuyến tính phải.
Cho văn phạm G({a,b}, {S,A,B}, P2, S) với các luật sinh như sau: P2={ SAa | Bb | a | b} là văn phạm tuyến tính trái.
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 6/13
Văn phạm chính qui
Văn phạm chính qui-- (tuyến tính phải) (tuyến tính phải)
Ngôn ngữcủa lớp văn phạm nàyđược gọi là ngôn ngữchính quy (RL: Regular Language)
Văn phạm chính qui suy rộnglà văn phạm mà các luật sinh có dạng A →aB, A →a hoặc A → εvới A, B∈Δvà a∈ Σ,
Văn phạm chính qui mẫulà văn phạm chính qui suy rộng nếu nó không có qui tắc có dạng A →a.
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 7/13
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 8/13
Ví dụ Ví dụ
Xét các văn phạm cho bởi các luật sinh sau: Văn phạm nào là vp chính quy, vp chính quy suy rộng, vp chính quy mẫu?
P1 = { S→aS | bS | cS| a| b| c} ?
P2= {SS →aS | bS | b| a}?
P3 ={S→aS | bS | cS| a| b| c| ε} ?
P4= {S→aS | bS| ε }?
P5={S →AB| a, A →a}?
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 9/13
Định lý:Đối với mỗi văn phạm chính quy suy rộng, có thểxây dựng văn phạm chính quy mẫu tươngđương với nó.
Giải thuật:
GiảsửG = (Σ,∆, P, S) là văn phạm chính quy suy rộng.
Xây dựng văn phạm chính qui mẫu G' = (Σ',∆', P', S')
Σ' =Σ
Δ’ =Δ∪∪∪∪{K}
S' = S.
Thay thếmỗi quy tắc có dạng A→a∈P bằng cặp quy tắc A→aK và K→ ε, các quy tắc khác giữnguyên ta thuđược P’.
Định lý Định lý
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 10/13 Biến đổi các luật sinh để tìm P’
Thay S→a bằng S→aK và K →ε
Thay S→b bằng S→bK và K →ε
Thay S→c bằng S→cK và K →ε
P' = { S→aS | bS|
cS | aK | bK | cK | ε;
K→ ε}.
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 11/13
Đồ hình biểu diễn văn phạm chính qui mẫu Đồ hình biểu diễn văn phạm chính qui mẫu
Đồhình biểu diễn văn phạm chính qui mẫu
Tậpđỉnh là các phần tửthuộc∆
Nếu có luật sinh A→aB thì có cungđi từ đỉnh Ađếnđỉnh B có nhãn là a.
Đỉnhứng với ký hiệu khởiđầu S gọi làđỉnh khởiđầu có nhãn start.
Đỉnhứng với luật sinh A→ εlàđỉnh kết thúc ký hiệu bởi hai vòng tròn.
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 12/13
Ví dụ
Cho văn phạm chính qui mẫu: G = (Σ, ∆, P, S) với Σ= { a, b, c }, ∆ = {S, K},
P = { S→ aS | bS | cS | aK | bK | cK, K →ε}.
Vẽ đồ hình biểu diễn văn phạm
Nhận xét
Đồ hình của văn phạm chính là ôtômát hữu hạn đoán nhận ngôn ngữdo văn phạm sinh ra Start
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 13/13
2/11/2014 Lý thuyết ngôn ngữ - Chương III Trang 14/13
Ví dụ 2
Chương IV
Văn phạm phi ngữ cảnh (CFG: Context Free Grammar)
2/11/2014 Lý thuyết ngôn ngữ - Chương II Trang 2/32
Nội dung