Chuyên đề: Nghiên cứu Ngôn ngữ hình thức, Văn phạm phi ngữ cảnh và Automata đẩy xuống

Ờ Ả Ơ L I C M  N

ế ả ơ ầ Tr

ệ ỹ

c h t, em xin chân thành c m  n các th y cô giáo trong khoa Công   ậ ầ ế   ng ĐH K  thu t – H u c n CAND đã trang b  nh ng ki n ệ ự ế ứ ơ ả ậ ể ề ủ ầ ướ ườ ngh  thông tin Tr th c c  b n, c n thi ị ữ t và quý báu đ  em th c hi n chuyên đ  c a mình.

ệ ế ơ ỏ ọ ặ Đ c bi t, em xin bày t

ư

ầ ệ ậ ợ ạ ọ ề ẫ ầ   ắ ớ t  n sâu s c t i th y ườ ườ   i đã ng, ng   i giúp em trong quá

lòng kính tr ng và bi ả Nghiêm Văn H ng, giáo viên gi ng d y, và th y Cao Xuân Tr ỉ ả ạ ậ ướ ng d n, ch  b o và t o m i đi u ki n thu n l t n tình h ề ệ ự trình th c hi n chuyên đ .

ặ ấ ố ắ ủ ầ

ẫ ậ ượ ự ế ạ ệ

ế ế

ấ ừ ạ ự ể ầ

ỉ ẫ ủ ể ự ỡ ậ   c s  giúp đ  t n tâm c a th y giáo M c dù đã r t c  g ng cùng nh n đ ộ ượ ướ ư   ng d n, xong do trình đ  còn h n ch , tài li u ch a đ h c phong phú, và ố ớ ế ữ ỏ ộ n i dung này khá khó đ i v i em nên không tránh kh i nh ng thi u sót trong   ậ ỡ   ượ ự ứ ậ c s  quan tâm giúp đ , quá trình ti p nh n ki n th c. Em r t mong nh n đ ờ ể ế   ớ  b n bè đ  trong th i gian t ch  d n c a th y cô và s  góp ý t i em có th  ti p ấ ệ ề ộ ụ t c tìm hi u và xây d ng chuyên đ  m t cách hoàn thi n nh t.

ả ơ Em xin chân thành c m  n!

Ớ Ệ Ổ Ề Ề GI I THI U T NG QUAN V  CHUYÊN Đ

ứ ữ ứ ạ ữ Tên chuyên đề: Nghiên c u Ngôn ng  hình th c, Văn ph m phi ng

ẩ ố ả c nh và Automata đ y xu ng

ự Sinh viên th c hi n ệ : Hoàng Văn Thao

L p:ớ  B3­D2B

ướ ế ườ ng Giáo viên h ng d n ẫ : Thi u úy Cao Xuân Tr

ế ủ ấ Tính c p thi t c a chuyên đ ề:

ộ ấ ế ữ ứ

ọ ữ ọ ủ

ệ ữ ậ ơ ở ự

ữ ộ

ể ế ả ạ

ẫ ộ ự ữ

ấ ủ ạ ượ ứ

ự  hình th c văn ph m đ ừ ữ ọ ế

ọ ề ữ ọ ợ ủ ế ị ầ

ứ ẽ ữ ế ề ứ ế Lý thuy t ngôn ng  hình th c và Automata đóng m t vai trò r t quan ứ ượ ử ụ   ọ c s  d ng tr ng trong các c  s  toán h c c a tin h c. Ngôn ng  hình th c đ ế ề ươ   ng trình trong vi c xây d ng các ngôn ng  l p trình, lý thuy t v  các ch ả ố ớ ụ ứ ạ ị   d ch. Các ngôn ng  hình th c t o thành m t công c  mô t  đ i v i các mô   hình tính toán c  cho d ng thông tin vào ­ ra l n ki u thao tác. Lý thuy t ngôn ứ   ng  hình th c, chính vì th c ch t c a nó là m t lĩnh v c khoa h c liên ngành; ả ầ c phát sinh trong nhi u ngành khoa nhu c u mô t   ạ   ậ ọ ọ h c khác nhau t  ngôn ng  h c đ n sinh v t h c. Do đó nh ng khía c nh ữ   thích h p c a lý thuy t ngôn ng  hình th c s  có t m quan tr ng quy t đ nh trong các giáo trình v  Lý thuy t ngôn ng  hình th c và Automata.

ế ự ứ ứ

ấ ữ ữ ữ

ứ ữ ấ

ể ị ả ỉ

ượ  nhiên, mà nó v ữ ữ ự ể ể ệ ượ ạ ộ

ữ ự ủ ẫ   ữ Lĩnh v c mà lý thuy t ngôn ng  hình th c nghiên c u là nh ng m u   hình (pattern) có c u trúc bên trong ngôn ng  hình th c, và đó là nh ng khía ạ ứ c nh hoàn toàn mang tính ch t có cú pháp. Ngôn ng  hình th c không còn   ỏ   ơ t ra ngoài kh i đ n gi n ch  là đ  đ nh nghĩa ngôn ng  t ắ   c nh ng quy t c có cú ph m vi đó và nó cũng là m t cách đ  th  hi n đ  nhiên. pháp c a ngôn ng  t

ụ ủ ứ ổ ề ạ M c tiêu c a chuyên đ

ụ ờ ề ậ ế

ữ ữ

ấ ủ ệ ơ ượ ề ầ ộ

ặ ị

ữ ồ ữ ả ọ ữ ế ể ạ ộ

ủ ọ ứ ự ị ị ẽ ớ ữ ả ọ ầ ộ ứ   ề: Nghiên c u t ng quan v  văn ph m hình th c và các Automata, là nh ng công c  sinh ngôn ng , đ ng th i đ  c p đ n các   ữ ớ   i tính ch t c a ngôn ng  chính quy, ngôn ng  phi ng  c nh. Ngoài ra, cũng gi ầ ươ   c v  Trình biên d ch, m t ph n quan tr ng c a h c ph n Ch ng thi u s  l ế ắ   trình d ch g n bó ch t ch  v i Lý thuy t ngôn ng  hình th c và Automata, ơ ở trong đó Văn ph m phi ng  c nh là c  s  lý thuy t đ  xây d ng B  phân tích   ấ cú pháp, là thành ph n quan tr ng nh t trong m t Trình biên d ch.

ố ượ ữ ứ : Ngôn ng  hình th c ế ứ  và lý thuy t Automata . Đ i t ng nghiên c u

ạ ứ : Ph m vi nghiên c u

ươ ệ ể ị ữ ả  cùng hai ph ng ti n đ  xác đ nh chúng là Văn

 Ngôn ng  phi ng  c nh ữ ữ ả ; ạ ph m phi ng  c nh

ẩ ố  Automata đ y xu ng.

ươ Ph ng pháp nghiên c uứ :

ươ ứ ệ  Ph ng pháp nghiên c u tài li u;

ươ  Ph ng pháp chuyên gia;

ươ ự ệ  Ph ng pháp th c nghi m.

ộ ứ : N i dung nghiên c u

ế ề ữ ả ứ ữ ạ  Lý thuy t v  Ngôn ng  hình th c, Văn ph m phi ng  c nh và Automata

ố ẩ đ y xu ng;

ữ ả ữ ứ ạ  Các tính ch t c a Ngôn ng  hình th c, Văn ph m phi ng  c nh và

ẩ ấ ủ ố Automata đ y xu ng;

 Ứ ữ ứ ụ ủ ớ ị ng d ng c a Ngôn ng  hình th c và Automata v i trình biên d ch.

ề ồ ươ Chuyên đ  g m 5 ch ng:

ươ ữ ề ậ ạ ứ Nh p môn v  văn ph m và ngôn ng  hình th c Ch ng I:

ữ ệ 1.1 Khái ni m ngôn ng

ữ ạ ạ ở 1.2 Văn ph m và ngôn ng  sinh b i văn ph m

ấ ủ ộ ố ữ 1.3 M t s  tính ch t c a ngôn ng

ươ ữ ả ạ Văn ph m phi ng  c nh Ch ng II:

ữ ả ẫ 2.1 Suy d n phi ng  c nh

ữ ả ế ạ ổ 2.2 Bi n đ i các Văn ph m phi ng  c nh

ươ ẩ ố Automata đ y xu ng Ch ng III:

ề ẩ ị ố 3.1 Automata đ y xu ng không ti n đ nh

ữ ả ẩ ạ ố 3.2 Automata đ y xu ng và Văn ph m phi ng  c nh

ươ ổ ị ề T ng quan v  trình biên d ch Ch ng IV:

ữ ậ 4.1 Ngôn ng  l p trình

4.2 Trình biên d chị

ữ ả Ứ ụ ủ ạ ẩ ố ớ   4.3  ng d ng c a Văn ph m phi ng  c nh và Automata đ y xu ng v i

trình biên d chị

ươ ộ Demo m t bài toán Ch ng V:

ơ ở ế 5.1 Bài toán và c  s  lý thuy t

ụ ề ự ươ ươ ữ 5.2 Demo ví d  v  s  t ng đ ng gi a BTCQ và NFAε

ả ẩ : S n ph m

 Báo cáo chuyên đ ;ề

ươ ơ  Ch ng trình demo c  b n.ả

Ụ Ụ M C L C

Ụ Ụ M C L C HÌNH

Ụ Ả Ụ M C L C B NG

LỜI NÓI ĐẦU

Ngôn ngữ là phương tiện để giao tiếp, sự giao tiếp có thể hiểu là giao  tiếp  giữa  con  người  với  nhau,  giao  tiếp  giữa  người  với  máy,  hay  giao  tiếp  giữa máy với máy.  Ngôn ngữ để  con người có thể giao tiếp với nhau được  gọi là ngôn ngữ tự nhiên, chẳng hạn như tiếng Anh,  tiếng Nga, tiếng Việt…  là  các  ngôn  ngữ  tự  nhiên.  Các  quy  tắc  cú  pháp  của  ngôn  ngữ  tự  nhiên  nói  chung  rất  phức  tạp  nhưng  các  yêu  cầu  nghiêm  ngặt  về  ngữ  nghĩa  thì  lại  thiếu  chặt  chẽ,  chẳng  hạn  cùng  một  từ  hay  cùng  một  câu  ta  có  thể  hiểu  chúng  theo  những  nghĩa  khác  nhau  tùy  theo  từng  ngữ  cảnh  cụ  thể.  Con  người  muốn  giao  tiếp  với  máy  tính  tất  nhiên  cũng  thông  qua ngôn ngữ. Để  có sự giao tiếp giữa người với máy hay giữa máy với nhau, cần phải có một  ngôn  ngữ  với  các  quy  tắc  cú  pháp  chặt  chẽ  hơn  so  với  các  ngôn  ngữ  tự  nhiên, nói cách khác,  với  một  từ  hay  một  câu  thì  ngữ  nghĩa  của  chúng  phải  là  duy  nhất  mà  không  phụ  thuộc  vào  ngữ  cảnh.  Những  ngôn  ngữ  như  thế  được gọi là ngôn ngữ hình thức.  Con người muốn máy  tính  thực  hiện  công  việc,  phải  viết  các  yêu  cầu  đưa  cho  máy  bằng  ngôn  ngữ  máy  hiểu  được.  Việc viết các yêu cầu như thế gọi là lập trình.  Ngôn ngữ dùng để lập trình  được gọi là ngôn  ngữ lập trình.  Các ngôn ngữ lập trình đều là các ngôn ngữ  hình thức.

Cả  ngôn  ngữ  hình  thức  lẫn  ngôn  ngữ  tự  nhiên  đều  có  thể  xem  như  những tập các từ,  tức là các xâu hữu hạn các phần tử của một bộ chữ cái cơ  sở nào đó. Về mặt truyền thống, lý  thuyết ngôn ngữ hình thức liên quan đến  các  đặc  tả  cú  pháp  của  ngôn  ngữ  nhiều  hơn  là  đến  những  vấn  đề  ngữ  nghĩa. Một đặc tả về cú pháp của  một ngôn ngữ có hữu hạn từ, ít nhất về  nguyên tắc, có thể được cho bằng cách liệt kê các từ. Điều đó không thể áp  dụng  đối  với  các  ngôn  ngữ  có  vô  hạn  từ.  Nhiệm  vụ  chính  của  lý  thuyết  ngôn ngữ hình thức là nghiên cứu các  cách đặc tả hữu hạn của các ngôn ngữ  vô hạn.

ừ Lý  thuy tế   ngôn  ngữ  hình  th cứ   và  ôtômat  đóng  m tộ   vai  trò  r tấ   quan  cượ  sử d ngụ   tr ngọ   trong các cơ sở toán h cọ  c aủ  tin h c.ọ  Ngôn ngữ hình th cứ  đ ngươ   trình  trong vi cệ   xây  d ngự   các  ngôn  ngữ  l pậ   trình,  lý  thuy tế   về  các  ch   Các  ngôn  ngữ hình th cứ  t oạ  thành m tộ   công cụ mô tả đ iố  v iớ  các mô  ị d ch. hình  tính  toán  cả  cho  d ngạ   thông  tin  vào­ra  l nẫ   ki uể   thao  tác.  Lý  thuy tế   ngôn  ngữ  hình  th c,ứ   chính  vì  th cự   ch tấ   c aủ   nó  là  m tộ   lĩnh  v cự   khoa  h cọ   liên  ngành;  nhu  c uầ   mô  tả  hình  th cứ   văn ph mạ  đ cượ  phát  sinh  trong nhi uề   ngành khoa h cọ  khác nhau t ữ ọ   đ nế  sinh v tậ  h c.ọ ng  h c ngôn

ị c.ượ  Ngoài ra cũng gi

ị iớ   thi uệ  sơ l ngươ  trình d ch/. Báo cáo  này  nh mằ   trình  bày  về  văn  ph mạ   hình  th cứ   và  ôtômat  đ yẩ   xu ngố , là nh ngữ  công cụ sinh ngôn ng ,ữ  đ ngồ  th iờ  đề c pậ  đ nế  các tính  ch tấ    ngôn  ngữ đệ quy và  ngôn  c aủ  ngôn ngữ chính quy, ngôn  ngữ phi  ngữ c nh,ả ngữ đệ quy đ mế  đ cượ  về trình biên  d ch,   m tộ  ph nầ  quan tr ngọ  c aủ  h cọ  ph nầ  Ch

7

ề ồ ầ Chuyên đ  g m 8 ph n chính:

ớ ệ ề ờ ở ầ Gi ề i thi u v  chuyên đ L i m  đ u:

ươ ữ ề ậ ạ ứ Nh p môn v  văn ph m và ngôn ng  hình th c Ch ng I:

ươ ữ ả ạ Văn ph m phi ng  c nh Ch ng II:

ươ ẩ ố Automata đ y xu ng Ch ng III:

ươ ổ ị ề T ng quan v  trình biên d ch Ch ng IV:

ươ ớ ề ươ ệ Gi i thi u v  ch ng trình Demo Ch ng V:

ư ề ế ứ ả ổ ậ Đ a ra m t s  đánh giá t ng quan v  k t qu  nghiên c u, nêu

K t lu n:  ướ ộ ố ờ ể ớ ế ng phát tri n trong th i gian t i. ra h

ư ệ ượ ẫ ả   c trích d n, tham kh o

Tài li u tham kh o:  ự ệ ả Đ a ra các tài li u đã đ ề ệ khi th c hi n chuyên đ .

8

ƯƠ Ữ Ậ CH NG 1. Ạ NH P MÔN V  VĂN PH M VÀ NGÔN NG  HÌNH

Ề TH CỨ

1.1. Khái ni mệ  ngôn ngữ

ơ ả ệ Các khái ni m c  b n

B ngả  ch  ữ cái

ệ ả ộ ế M t dãy : Phan Đình Di u, có vi

ệ Theo tài li u [3], tác gi ầ ử  kí hi uệ  (cid:0) (cid:0)  đ h uữ  h nạ  hay  t “ cượ  g iọ  là m tộ  b ngả  chữ  cái trong đó m iỗ

ữ ộ ộ vô h nạ  các ph n t ầ ử (cid:0) (cid:0) (cid:0) (cid:0) đ  a  ph n t , ệ ượ ọ c g i là m t kí hi u (m t ch  cái). ”.

ừ ị T  đó ta có Đ nh nghĩa I.1.

I.1

ị Đ nh nghĩa T pậ   (cid:0) (cid:0) khác  r ngỗ   g mồ   h uữ   h nạ   hay  vô  h nạ   các  ký  hi uệ   đ cượ   g iọ   là (cid:0) (cid:0) b ngả  chữ cái.  M i ỗ ph n ầ tử a(cid:0) (cid:0) đ ượ ọ  là m t chộ c g i ữ cái hay m tộ  ký hi u.ệ

Thí dụ 1.1:

(cid:0)

, (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) , (cid:0) ,(cid:0) , (cid:0) },

Dưới đây là các bảng ch  ữ cái: (cid:0) = {a, b, c, …, x, y, z}, , (cid:0) , (cid:0) Δ = {(cid:0) Г = {0, 1}, W = {if, then, else, a, b, c,  d, e, f, +, (cid:0) , (cid:0) , /, =, (cid:0) }.

Từ

ị

Đ nh nghĩa  I.2 Giả sử có b ngả  chữ cái (cid:0) (cid:0) = {a1, a2, …, am}, m tộ  dãy các chữ cái α = ai1

(cid:0) (cid:0) (cid:0) ả (cid:0) (1 ≤  j ≤ t) đ ượ ọ là m t ộ từ hay m t ộ xâu trên b ng ch c g i ữ

ai2  cái (cid:0) … ait, v iớ  aij  .

Tổng số vị trí của các ký hiệu xuất hiện trong xâu α được gọi là độ dài  (cid:0) là một xâu  ,  trong  đó

của từ α và ký hiệu là | α |. Như vậy, một từ trên bảng chữ cái (cid:0) hữu  hạn  gồm  một  số  lớn  hơn  hay  bằng  không  các  chữ  cái  của  (cid:0) một chữ cái có thể xuất hiện nhiều lần.

Xâu  không  có  chữ  cái  nào  được  gọi  là  từ  r ngỗ   và  được  ký  hiệu  là  (cid:0) .  (cid:0) = Rõ  ràng  từ  rỗng  là  từ  thuộc mọi bảng chữ cái. Hai từ (cid:0) và (cid:0)

được gọi là bằng nhau, và được ký hiệu là (cid:0) (cid:0) = (cid:0) (cid:0) = a1a2…an  , nếu n =  m và a = i

với mọi i = 1, 2, …, n. b1b2…bm  b i

9

(cid:0) (cid:0) , và (cid:0) (cid:0) Δ thì α cũng là từ trên bảng

(cid:0) được ký hiệu là (cid:0) *,

còn tập mọi  = (cid:0) * \ .  Như vậy (cid:0) +

Nếu α là một từ trên bảng chữ cái (cid:0) ch  ữ cái Δ. Tập mọi từ trên bảng chữ cái (cid:0) từ  khác  rỗng  trên  bảng  chữ  cái (cid:0) {(cid:0) } và (cid:0) * = (cid:0) + (cid:0) (cid:0) {(cid:0) }.  D  ễ thấy rằng các tập (cid:0) * (cid:0) được ký hiệu là  (cid:0) + và (cid:0) + là vô hạn.

Về cấu trúc đại số thì (cid:0) * là một vị nhóm tự do sinh bởi (cid:0) (cid:0) với đơn vị là

. Có th  ể chứng minh được

ượ ế là một nửa nhóm tự do sinh bởi (cid:0) và (cid:0) + là vô hạn đ m đ c.

b ng ả trên từ rỗng (cid:0) , còn (cid:0) +  rằng các tập (cid:0) *  Thí dụ 1.2: Ta có (cid:0)

chữ  cái  Г = {0,1}.  (cid:0) = {a, b, c, …,

(cid:0) , 0,  01, 101, 1010, 110011 là  các  t ừ Các xâu (cid:0) , beautiful, happy, holiday là các từ trên b ngả  chữ cái (cid:0) z}.

Ngôn ngữ

ị Đ nh nghĩa I.3

(cid:0) * (cid:0) Cho  bảng  chữ  cái  (cid:0) được  gọi  là  một  ngôn  ngữ

,  mỗt  tập  con  L  (cid:0) hình thức  (hay ngôn ngữ) trên bảng chữ cái (cid:0) .

Tập rỗng, ký hiệu (cid:0)

, là một ngôn ngữ không gồm một từ nào và được  gọi là ngôn ngữ rỗng.  Vậy ngôn ngữ rỗng là ngôn ngữ trên mọi bảng chữ cái.

(cid:0) Chú ý rằng ngôn ngữ rỗng: L = (cid:0) là khác với ngôn ngữ ch  ỉ gồm một từ

rỗng: L = {(cid:0) }.

Thí dụ 1.3:

(cid:0) (cid:0) (cid:0) còn (cid:0) + là ngôn ng  ữ gồm tất

(cid:0) *   ừ khác t là ngôn ng  ữ gồm tất cả các từ trên (cid:0) . ừ trống  trên (cid:0) c  ả các t

(cid:0)  L = { (cid:0) , 0, 1, 01, 10, 00, 11, 011,100} là một ngôn ngữ trên bảng ch  ữ cái

Г = {0, 1}.

(cid:0)  L = {a, b, c, aa, ab, ac, abc} là  ngôn ngữ trên bảng ch  ữ cái (cid:0) (cid:0) = {a, b, c}.

n (cid:0)  L = {(cid:0) , a, b, abb, aab, aaa, bbb, abab}, L n = {a b | n(cid:0) (cid:0) N} là hai ngôn 2

1  ngữ trên bảng chữ (cid:0) (cid:0) = {a, b}, L là ngôn ngữ hữu hạn trong khi L là ngôn 1 2

ngữ  vô  hạn.  Mỗi  từ  thuộc  ngôn  ngữ L có số chữ cái a bằng số  chữ cái b 2

với a và b không xen kẽ, a nằm ở phía trái và b ở phía phải của từ.

10

Các phép toán trên các từ

Phép nhân ghép

ả ị ệ Theo tài li u [5], tác gi : Nguy n Văn Đ nh, có vi

ế Tích  ghép  (hay  trên  b ngả   chữ ễ nhân  ghép)  c aủ   hai  từ  α  =  a1a2…a m

t “ và  từ  (cid:0) (cid:0) =  b1b2…bn  ữ cái (cid:0) . ả trên b ng ch cái (cid:0) , là từ (cid:0) (cid:0) = a1a2…amb1b2…b n

Kí hiệu phép nhân ghép là  (cid:0) (cid:0) = α.(cid:0) (cid:0) (hay (cid:0) (cid:0) = α(cid:0) ).” ị ừ T  đó ta có Đ nh nghĩa I.4.

và từ (cid:0) (cid:0) = b1b2…bn

ị Đ nh nghĩa I.4 Tích ghép (hay nhân ghép) c aủ  hai từ α = a1a2…am  ả trên b ng ch , là từ (cid:0) trên  b ngả  chữ cái (cid:0) ữ cái (cid:0) . (cid:0) = a1a2…amb1b2…bn

(cid:0) (cid:0) = α(cid:0) ). (cid:0) = α.(cid:0) (hay (cid:0)

Kí hiệu phép nhân ghép là  (cid:0) Thí dụ 1.4: Trên bảng chữ cái W = {if, then, else, a, b, c,  d, e, f, +, (cid:0) , (cid:0)

(cid:0) =  if  a+b=c then c(cid:0) d=e và (cid:0) (cid:0) = else c/d=f, còn α(cid:0) , /, =, (cid:0) }, ta  (cid:0) là từ:  if a+b=c

có các từ (cid:0) then c(cid:0) d=e else c/d=f.

Cho  (cid:0) (cid:0) =  {a,  b,  c},  khi  đó:  Từ  (cid:0) (cid:0) (cid:0) =  abcbcb  chứa  2  vị  trí  của  bcb,  đó  (cid:0) chứa  . Từ

là  a*bcb*cb  và abc*bcb*,  φ  =  bcb  là  một  từ  con  của  (cid:0) một  vị  trí  của  ký  hiệu  a,  đó  là *a*bcbcb.

Từ (cid:0) (cid:0) = 010111001 trên bảng chữ cái {0, 1} có độ dài 9, trong đó 0101 là

.

tiền tố và 11001 là hậu tố của (cid:0)  ừ ngược Phép lấy t

ị ả

…am ế Giả sử có từ khác  t “ cượ  g iọ  là  đ am­1… a2a1

ệ Theo tài li u [5], tác gi r ngỗ  (cid:0) (cid:0) (cid:0) = a1a2  từ ng c ượ (hay từ soi g c aủ  từ (cid:0) , và đ c ượ ký hi u ệ là (cid:0) R, hay (cid:0) ^ .

ị Khi (cid:0) (cid:0) = (cid:0) (cid:0) ta quy  ừ ễ : Nguy n Văn Đ nh, có vi trên b ngả  chữ cái (cid:0) , khi đó từ am  ươ ng) cướ  (cid:0) R  =  (cid:0) .” 5. Đ nh nghĩa I. T  đó ta có

ị 5 Đ nh nghĩa I.

11

(cid:0) Giả sử có từ khác r ngỗ  (cid:0) trên b ngả  chữ cái (cid:0) , khi đó từ am …am

ươ ượ (cid:0) = a1a2  c  ượ (hay từ  soi  g c g i ọ   là  từ  ng ng) c aủ   từ  (cid:0) ,  và  đ c  ượ ký đ

a1  am­1…  a2   hay (cid:0) ^ hi u ệ là (cid:0) R, .

(cid:0) cướ  (cid:0) R ta quy =  (cid:0) .

(cid:0) = (cid:0) Khi (cid:0) Thí dụ 1.5:  Cho các từ α = 100110 và (cid:0) (cid:0) = aabb trên bảng ch  ữ cái {0,1,a,b}, theo định

nghĩa ta có:

= (011001)R = 100110 = α.

αR  (cid:0) R = 011001 và (αR)R  = bbaa và ((cid:0) R)R = (bbaa)R = aabb = (cid:0) .

Cho các từ happy và oto trên bảng ch  ữ cái (cid:0) (cid:0) = {a, b, c, …x, y, z}, khi đó

= yppah và (oto)R = oto. Ngoài ra ta có: | (happy)R | = | yppah| = |

ta có: (happy)R  happy | = 3.

Phép chia từ

Là phép toán ngắt b  ỏ phần đầu hay phần cuối của một từ.  Ta có các

định nghĩa sau:

 Phép chia trái của từ α cho từ (cid:0)

(cid:0) (hay thương bên trái của α và (cid:0) ) cho  (cid:0) trong  từ α, và

kết quả là phần còn lại của từ α sau khi ngắt b  ỏ phần đầu (cid:0) được ký hiệu là \ (cid:0)

 Phép chia phải của từ α cho từ (cid:0) (cid:0) cho  kết quả là phần còn lại của từ α sau khi ngắt b  ỏ phần cuối (cid:0) (cid:0) (hay thương bên phải của α và (cid:0) )  trong

α từ α, và được ký hiệu là /

Các phép toán trên ngôn ng .ữ

Các họ ngôn ngữ cụ thể  thường được đặc  trưng một cách tiện lợi qua  các  phép  toán  xác  định  trên  ngôn  ngữ,  họ  đó  gồm  các  ngôn  ngữ  nhận  được  bằng việc tổ  hợp từ một số ngôn  ngữ  cho  trước  bởi  một  số  phép  toán  nào  đó. Vì mỗi ngôn ngữ là một tập hợp nên ta có các phép toán  đại số tập hợp  như là phép giao, phép hợp, phép hiệu, phép lấy bù trên các ngôn ngữ. Chẳng  (cid:0) thì ta cũng có các ngôn  hạn, với L là hai ngôn ng  ữ trên bảng ch  ữ cái (cid:0) và L 1

(cid:0) (cid:0) 2  ng  ữ mới sau đây trên bảng chữ cái (cid:0) : L , L , L .L , (cid:0) * . 1 (cid:0) L 2 1 (cid:0) L 2 1 2 \ L 1

Phép hợp

12

ả Nguy n Qu c Th ng – Nguy n Lâm Tùng, ắ ễ ợ ủ ượ ọ c g i là h p c a hai ngôn } đ có vi ệ Theo tài li u [9], tác gi ậ t “ế T p các t ễ ố ho c ặ x(cid:0) (cid:0) (cid:0) L2

:  ừ {x | x(cid:0) (cid:0) (cid:0) L1    ng  Lữ 1 và L2, ký hi uệ  L1(cid:0) (cid:0) L2.”.

ừ ị T  đó ta có Đ nh nghĩa I.6.

ị Đ nh nghĩa I.6

(cid:0) Hợp của hai ngôn ngữ L và L trên bảng chữ cái (cid:0) (cid:0) L , 1 , ký hiệu L 1 2

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) là một  ngôn ngữ trên bảng chũ cái (cid:0) (cid:0) * | (cid:0) L = {(cid:0) 2  , đó là tập từ: hoặc (cid:0) (cid:0) L (cid:0) L } 1 2

Định  nghĩa  phép  hợp  có  thể  mở  rộng  cho  một  số  hữu  hạn  các  ngôn  , là tập ngữ,  tức  là  hợp  của  các  ngôn ngữ L trên bảng ch  ữ cái (cid:0) , …, L , L 1 2 n

từ:

và

13

Phép giao

ị Đ nh nghĩa I.7

Giao của hai ngôn ngữ L và L trên bảng chữ cái (cid:0) , ký hiệu L ∩ L là 2 1 2,

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1  một  ngôn ngữ trên bảng ch  ữ cái (cid:0) (cid:0) * | (cid:0) L = {(cid:0) , đó là tập từ: (cid:0) L và (cid:0) (cid:0) L } 1 2

Định  nghĩa  phép  giao  có  thể  mở  rộng  cho  một  số  hữu  hạn  các  ngôn  , là tập ngữ, tức là giao của các  ngôn ngữ L trên bảng ch  ữ cái (cid:0) , …, L , L 2 1 n

từ:

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) {(cid:0) (cid:0) * | (cid:0) với mọi i, 1 ≤ i ≤ n } (cid:0) L i,

Phép lấy phần bù

ị I.8

Đ nh nghĩa Ngôn  ngữ  phần  bù  của  ngôn  ngữ  L  trên  bảng  chữ  cái  (cid:0) ,  ký  hiệu  C L (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (hay  đơn giản là CL, nếu không  gây nhầm  lẫn), là một ngôn ng  ữ trên  bảng  (cid:0) * | (cid:0) chữ cái (cid:0) , đó là tập từ:  C (cid:0) L }. L = {(cid:0) (cid:0)

Thí dụ 1.6:

Cho ngôn ngữ L = {(cid:0) , 0, 01}, L = {(cid:0) , 01, 10} trên bảng ch  ữ cái (cid:0) (cid:0) = {0, 2 (cid:0) = {(cid:0) , 0, 01, 10}, L ∩ L = {(cid:0) , 01}. 1  (cid:0) L 1 2 1}, khi đó ta có: L 1

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) *,  với |  (cid:0) | là một s  ố chẵn },  khi  đó ta có:

2  Cho ngôn ng  ữ L  = {(cid:0) (cid:0) +, (cid:0) (cid:0) (cid:0) (cid:0) | là một số lẻ}. với | (cid:0) L = {(cid:0) C (cid:0)

Phép nhân ghép

ị Đ nh nghĩa I.9

Cho  hai  ngôn  ngữ  L trên  b ngả   chữ  (cid:0) và  L trên  b ngả   chữ  (cid:0) .  Nhân 1 1 2 2

ghép  hay tích c aủ  hai ngôn ngữ L và L là m tộ  ngôn ngữ trên b ngả  chữ (cid:0) 1 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 1  ,  đu cợ  xác đ nhị = {(cid:0) L | (cid:0) (cid:0) L và (cid:0) }. , ký hi uệ  L 2   b i: ở L 1 2 1 (cid:0) L 2 L 2 1 2

Thí dụ 1.7:

Đây là một phản ví dụ để chỉ ra rằng phép nhân ghép không có tính phân  phối đối  với phép giao.  Phép hợp, phép giao không có tính phân phối đối với

14

phép nhân ghép. Xét các ngôn ng  ữ L = {0, 01}, L = {01, 10}, L = {0} trên 1 2 3

bảng chữ cái (cid:0) (cid:0) = {0, 1}.

Có thể kiểm tra được rằng phép nhân ghép không có tính phân phối đối (cid:0) (cid:0) với phép giao: Ta có: L (cid:0) L = (cid:0) , do đó: L (L ) = (cid:0) , 3 2 1 2 (cid:0) L 3

Mặt khác, ta có L L L = {00, 010}, do 1 2 (cid:0) đó: (L ) (cid:0) = {001, 010, 0101, 0110} và L 1 L (cid:0) L (L ) (cid:0) 3  ) (cid:0) L ) = {010}. Vậy L (cid:0) (L ), tức là L 2 1 (cid:0) (L 1 3 1 2 3 (cid:0) (L 1 2 L 3 1

phép nhân ghép không có tính phân phối đối với  phép giao.

Kiểm tra tính phân phối của phép hợp, phép giao đối với phép nhân ghép: (cid:0) Ta có: L L = {010, 100}, do đó: L ) = {0, 01, 010, 100}, (cid:0) (L 2 3 L 3 2 1

(cid:0) (cid:0) Mặt khác ta cũng có L = {0, 01, 10} và L = {0, 01}, do đó: (cid:0) L (cid:0) L 2 1 3 1 (cid:0) (cid:0) (cid:0) (L (cid:0) L (cid:0) L )(L )  = {00,  001, 010, 0101, 100,  1001}.  Vậy  L L ) (cid:0) (L 2 3 1 (cid:0) (cid:0) (cid:0) 1  (cid:0) (L 1  )(L 3 (cid:0) L ),  tức  là  phép  hợp  không  có  tính  phân  phối  đối  với 1 2 (cid:0) L 2 1 3

phép nhân ghép. Tương tự, đối với phép giao, ta có:  L L = {010, 100}, do đó: 2 3 (cid:0) L (cid:0) (L ) = (cid:0) . 1 L 3 2

(cid:0) (cid:0) (cid:0) (cid:0) Mặt khác L (cid:0) L = {01}, L (cid:0) L = {0}, do đó: (L (cid:0) L )(L ) 1 1 1 1 3 (cid:0) (cid:0) (cid:0) = {010}. Vậy L 2  L ) (cid:0) (cid:0) (L 3  )(L (cid:0) L 2 ). Tức là phép giao không 1 (cid:0) (L 2 3 1 (cid:0) L 2 1 (cid:0) L 3

có tính phân phối đối với  phép nhân ghép. Vì phép ghép ngôn ngữ có tính kết

n được  dùng  với  mọi  ngôn  ngữ  L  và  số  tự nhiên n theo

hợp  nên  ký  hiệu  L nghĩa quen thuộc sau:

Phép lặp

ị I.10

Đ nh nghĩa Cho ngôn ngữ L trên b ngả  chữ cái (cid:0) , khi đó:

*.

ậ ừ ượ ữ ặ ữ ệ ọ  T p t c g i là ngôn ng  l p c t c a ngôn ng  L, ký hi u là L

ậ ậ ợ ắ ủ ừ ủ đ ữ ặ ủ V y ngôn ng  l p c a L là t p h p lũy th a c a L:

+

L*=

,

ậ ừ ượ ắ ủ ữ ặ ọ  T p t c g i là ngôn ng  l p c t c a ngôn ng  L, ký hi u là L

ợ ủ ừ ươ ậ ọ đ ữ ặ ắ ủ V y ngôn ng  l p c t c a L là h p c a m i lũy th a d ữ ủ ng c a L: L ệ +=

15

Thí dụ 1.8:

+ Xét ngôn ng  ữ L = {0, 1} trên b ngả  ch  ữ (cid:0) (cid:0) = {0, 1}. Ta có:

2 ậ ộ = {00, 01, 10, 11}, t p h p ợ  các xâu nhị phân đ  dài 2; L

3 L = {000, 001, 010, 011, 100, 101, 110, 111}, tập hợp các xâu nh  ị phân độ

* n là tập hợp các xâu nhị phân độ dài n. Vì vậy, L là tập

dài 3.  Tương tự, L hợp tất c  ả các xâu nh  ị phân.

+ Xét hai ngôn ngữ trên bảng ch  ữ (cid:0) (cid:0) = {a}:

2n | n (cid:0) (cid:0) 1}, L = {a 1

5n+3 | n (cid:0) (cid:0) 0}. L = {a 2

Khi đó, ta có L 2 = {a + } , L 5 = {a * } 3 {a }. 1 2

Phép lấy ngôn ngữ ngược

ị

Đ nh nghĩa I.11 Cho  ngôn  ngữ  L  trên  bảng  chữ  cái  (cid:0)

R một ngôn ngữ trên bảng chữ cái (cid:0) ,  khi  đó  ngôn  ngữ  ngược  của  L  là  ^ hay L , là tập từ: , được ký hiệu là L

R (cid:0) (cid:0) (cid:0) (cid:0) * / (cid:0) R (cid:0) L (cid:0) L}

(cid:0) = {a, b,

R = {(cid:0) Thí dụ 1.9: Cho L = {(cid:0) , ab, abc, cbaa} là một ngôn ng  ữ trên bảng chữ cái (cid:0) = {(cid:0) , ba, cba, aabc} là ngôn ngữ ngược của L. c}, khi đó L

Phép chia ngôn ngữ

ị I.12

,  khi  đó  thương  bên  trái  của  X, Đ nh nghĩa Cho  ngôn  ngữ  X  và  Y trên  bảng  chữ  cái  (cid:0) ngôn  ngữ X cho ngôn ngữ Y là một ngôn ng  ữ trên (cid:0) , được ký hiệu là \ Y

là tập từ:

X (cid:0) \ = {z (cid:0) (cid:0) * / x (cid:0) (cid:0) X, y (cid:0) (cid:0) Y mà x = yz} Y

Cho ngôn ngữ X và Y trên bảng chữ cái (cid:0) , khi đó thương bên phải của ngôn

16

X ngữ X cho ngôn ngữ Y là một ngôn ngữ trên (cid:0) , được ký hiệu là là tập từ: / Y,

X (cid:0) / = {z (cid:0) (cid:0) * / x (cid:0) (cid:0) X, y (cid:0) (cid:0) Y mà x = zy} Y

ữ ở ạ ạ 1.2. Văn ph m và ngôn ng  sinh b i văn ph m

Ta có thể hình dung một văn phạm như một “thiết bị tự động” mà nó có  khả năng sinh  ra một tập hợp  các từ  trên  một  bảng  chữ  cái  cho trước. Mỗi  từ  được  sinh  ra  sau  một  số  hữu  hạn  bước thực  hiện  các  quy  tắc  của  văn  phạm.

Việc  xác  định  một  ngôn  ngữ  trên  bảng  chữ  cái  cho  trước  có  thể  được

thực hiện bằng  một trong các cách thức sau:

 Cách  1.  Đối  với  mỗi  từ  thuộc  ngôn  ngữ  đã  cho,  ta  có  thể  chọn  một  quy cách hoạt động của  “thiết bị tự động” để sau một số hữu hạn bước làm  việc nó dừng và sinh ra chính từ đó.

 Cách 2.  “Thiết b  ị tự động” có khả năng lần lượt sinh ra tất cả các từ

trong ngôn ng  ữ đã cho.

 Cách 3. Với mỗi từ (cid:0) (cid:0) cho trước, “thiết bị tự động” có thể cho biết từ

đó có thuộc ngôn ngữ  đã cho hay không.

Trong  lý  thuyết  văn  phạm,  người  ta  đã  chứng  minh  được  rằng  ba  cách  thức  trên  là  tương  đương  nhau  hay  văn  phạm  làm  việc  theo  các  cách  trên là tương đương nhau. Vì vậy, ở đây ta  quan tâm đến cách thứ nhất, tức   đẽ ó mà  là ta xét văn phạm như là một “thiết bị tự động” sinh ra các  từ. Vì l người ta còn gọi các “thiết b  ị tự động” đó là văn phạm sinh.

Định nghĩa văn phạm

ả ầ ộ Văn ph mạ  G là  1 bộ ệ Theo tài li u [2], tác gi : Tr n Văn L c, có vi t: “

ế s pắ  th  tứ ự g mồ  4 thành ph n: ầ G = < (cid:0) , , S, P >…”

ừ ị T  đó ta có Đ nh nghĩa I.13.

ị I.13

Đ nh nghĩa Văn ph mạ  G là 1 bộ s pắ  th  tứ ự g mồ  4 thành ph n: ầ G = < (cid:0) , , S, P >,

trong đó:  (cid:0)

ượ ế (cid:0) là m tộ  b ngả  chữ cái, g iọ  là b ngả  chữ cái cơ b nả  (hay b ngả  chữ cái   hay ký hi uệ ọ là m t ộ ký hi u ệ k t thúc c g i

(cid:0) (cid:0) (cid:0) k tế  thúc), m iỗ  ph nầ  tử  c aủ  nó đ cơ b nả ;  (cid:0) là m tộ  b ngả  chữ cái, (cid:0) (cid:0) = (cid:0)

, g iọ  là b ngả  ký hi uệ  phụ (hay  cượ   g iọ   là  m tộ   ký

báng  chữ  cái  không  k tế   thúc),  m iỗ   ph nầ   tử  c aủ   nó  đ hi uệ  không k tế  thúc hay ký hi uệ  ph .ụ

17

(cid:0) (cid:0) cượ  g iọ  là ký hi uệ  xu tấ  phát hay tiên đ ;ề đ

(cid:0) (cid:0) (cid:0) đ

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)  S (cid:0)  P là t pậ  h pợ  các quy t cắ  sinh  có d ngạ  (cid:0) cượ   g iọ   là  vế  ph i  ả c aủ   quy  t cắ   này,  v iớ   (cid:0) , (cid:0) ,  (cid:0) cượ   g iọ   là vế trái và  *  (cid:0) ((cid:0) và  trong (cid:0) ) (cid:0) (cid:0) đ (cid:0) ch aứ  ít nh tấ  m tộ  ký hi uệ  không k tế  thúc.

* (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) | (cid:0) (cid:0) = α’Aα’’, với A (cid:0) (cid:0) ) (cid:0) ((cid:0) }

(cid:0) Δ, α’, α’’, (cid:0) (cid:0) = {0,1}, (cid:0) = {S, A, B} thì các quy tắc S (cid:0)

P = {(cid:0) Chẳng hạn, với (cid:0) (cid:0) 1A1B, A (cid:0)

(cid:0) 0S1A,    (cid:0) ,… là các quy tắc hợp lệ vì vế trái luôn chứa ít nhất  (cid:0) 0B,… là (cid:0) A, 01 (cid:0)

0AB (cid:0) 1 ký hiệu phụ thuộc .  Nhưng  các quy tắc dạng  0 (cid:0) các quy tắc không hợp lệ.

Thí dụ 1.10:

(cid:0) Các b  ộ bốn sau là các văn phạm: (cid:0) G = <{0,1},{S},S,{S(cid:0) 0S1,S(cid:0) (cid:0) }>, 1

(cid:0) (cid:0) G = <{a, b}, {S, A}, S, {S(cid:0) Ab, A(cid:0) aAb, A(cid:0) (cid:0) }>, 2

(cid:0) (cid:0) G = <{a, b, c}, {S, A, B, C}, S, {S(cid:0) ABC, A(cid:0) aA, B(cid:0) bB, C(cid:0) cC, A(cid:0) a, 3

B(cid:0) b, C(cid:0) c}>

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) có  thể được viết là (cid:0) | (cid:0)

Chú ý: Nếu các quy tắc có vế trái giống nhau có thể viết gọn lại: hai quy  , (cid:0) .  Chẳng hạn, như trong văn  ở thí dụ 1.10, ta có thể viết hai  quy tắc của nó dưới dạng S(cid:0) 0S1 | tắc (cid:0) phạm G 1

(cid:0) . Ngôn ng  ữ sinh bởi văn phạm

ị Đ nh nghĩa I.14

(cid:0) (cid:0) (cid:0) Cho văn phạm G = < (cid:0) (cid:0) ) * . Ta nói (cid:0)

, (cid:0) G (cid:0) , , S, P > và (cid:0) (cid:0) trong G, ký hiệu (cid:0) ├ ((cid:0) (cid:0) hay ngắn gọn là (cid:0) ├ (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) P  và  (cid:0) ,  (cid:0) (cid:0) ((cid:0) được suy  (cid:0) (nếu  *  (cid:0) ) sao (cid:0) (cid:0) (cid:0) (cid:0) d nẫ  tr cự  ti p ế từ (cid:0) không  sợ  nhầm  lẫn),  nếu  tồn  tại  quy  tắc  (cid:0) cho (cid:0) . , (cid:0)

(cid:0) (cid:0) (cid:0) nhận vế trái (cid:0) (cid:0) của quy tắc (cid:0) (cid:0) như là từ

(cid:0) = (cid:0) (cid:0) = (cid:0) Điều này có nghĩa là nếu (cid:0) (cid:0) bằng (cid:0) con thì ta thay (cid:0) (cid:0) để được từ mới (cid:0) .

(cid:0) (cid:0) (cid:0) Cho văn phạm G = < (cid:0) , (cid:0) * (cid:0) ) . Ta nói (cid:0)

, , S, P > và (cid:0) G (cid:0) suy d nẫ  từ (cid:0) (cid:0) trong G, ký hiệu (cid:0) ╞ ((cid:0) (cid:0) hay ngắn gọn là (cid:0) ╞ (cid:0) được  (cid:0) (nếu không

18

sợ  nhầm  lẫn),  nếu  (cid:0) (cid:0) =  (cid:0) (cid:0) hoặc  tồn  tại  một  dãy  D  =  (cid:0) ,…, ,  (cid:0) 0 1

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ((cid:0) *  sao cho (cid:0) (cid:0) ) = (cid:0) , (cid:0) = (cid:0) (cid:0) và (cid:0) ├ (cid:0) , với i = 1, 2,..., k. k k i­1 i

Dãy D = (cid:0) , (cid:0) 0  , …, (cid:0) được gọi là một d nẫ  xu tấ  của (cid:0) (cid:0) từ (cid:0) (cid:0) trong G 0 1 k (cid:0) (cid:0) và số k được gọi là độ dài của dẫn xuất này.  Nếu (cid:0) = S và (cid:0) (cid:0) * thì dãy 0 k

D gọi là dẫn xuất đầy đủ.

Nếu (cid:0) được suy dẫn trực tiếp từ (cid:0) bằng việc áp dụng một quy tắc i i­1

p nào đó trong G thì ta nói quy tắc p được áp d ngụ  ở bước th  ứ i.

(cid:0) ,  , S,  P  >.  Từ  (cid:0)

(cid:0) *  được  gọi  là  sinh  b iở   văn  . Ngôn ngữ sinh b iở  văn phạm G, ký hiệu

Cho  văn  phạm  G  =  <  (cid:0) phạm G nếu tồn tại suy dẫn S╞ (cid:0) L(G), là tập hợp  tất cả các từ sinh bởi văn phạm G:

(cid:0) * (cid:0) L(G) = {(cid:0) | S ╞

G (cid:0) }. ,  P Hai  văn  ph mạ   G =  <  (cid:0) , , S >  và  G =  <  (cid:0) , , S ,P > 1 1 2 2 2 2 2

1  1 ) = L(G ). cượ  g iọ  là t đ ngươ  đ 1 ngươ  n uế  L(G 1 2

Thí dụ 1.11:

Xét  văn  ph mạ   G trong  thí  dụ  1.11  Từ  (cid:0) (cid:0) =  00001111  đ cượ   suy  d nẫ   từ 1

4 4 ầ ằ 00001111  (có  thể  vi tế   ng nắ   g n làọ ). B ng vi c s 1 (cid:0)

S  b ngằ   dãy  d nẫ   xu tấ   độ  dài  5:  S├  0S1├  00S11├  000S111├  0000S1111  ├  (cid:0) = 0 n n ụ n n (cid:0) ồ ệ ử d ng n l n (n | n (cid:0) (cid:0) 0) quy t c 1 r i quy ắ . Do đó L(G ta có: S  0╞ t c 2,ắ (cid:0) 0}. ) = {0 1 1 1

Xét văn phạm G trong thí dụ 1.10 Sử dụng quy tắc 1, rồi n lần (n (cid:0) (cid:0) 0) 2

n n+1 n quy tắc 2, sau đó quy tắc 3 để kết thúc, ta có: S  ├ Ab  ╞ a Ab n b  ├ a b .

n+1 n ) = {a b | n (cid:0) (cid:0) 0}. Do đó L(G 2

) = {tôi ăn cơm, anh ăn cơm, ch  ị ăn cơm, tôi ăn D  ễ dàng thấy rằng: L(G 4

phở, anh ăn phở,  chị  ăn  phở,  tôi  uống  sữa,  anh  uống  sữa,  chị  uống  sữa,  tôi  uống café, anh uống café, chị  uống café}.

), Ta  có  thể  biểu  diễn  việc  dẫn  xuất  từ    đến  một  từ  trong  L(G 4

chẳng  hạn  “tôi  ăn  cơm”  bằng  một  cây  gọi  là  cây  d nẫ   xu tấ   hay  cây  phân  tích cú pháp như dưới đây. Tất nhiên, theo  quan điểm phân tích cú pháp thực

19

tế, việc xem xét các quy tắc theo hướng ngược lại là t  ừ phải  qua  trái.  Điều  đó  có  nghĩa  là  cây  dưới  đây  được  xử  lý  từ  dưới  lên  trên  chứ  không  phải  là  từ trên xuống dưới. (Hình 1.1).

ấ ụ ẫ Hình 1. Cây d n xu t cho ví d

Phân loại văn phạm theo Chomsky

ả : Tr n Văn Ban, có vi

t “ ế (cid:0)  là t p ch  cái và S  ữ ậ ữ ượ ứ ệ

ố

ạ ượ ắ ả ự ủ

ắ ẫ ạ ố ế Trong đ nh nghĩa c a ủ   ị ệ ầ Theo tài li u [8], tác gi (cid:0) VN. Để  N, (cid:0) , P, S); VN là t p các bi n,  ạ ậ văn ph m G = (V ở ệ ợ ả   ti n l c sinh ra b i văn i cho vi c nghiên c u và kh o sát các ngôn ng  đ ạ ạ c các ngôn ph m, chúng ta tìm cách phân lo i chúng. Mu n phân lo i đ   ấ   ẫ ạ ữ ng , chúng ta ph i d a vào các d ng khác nhau c a các qui t c d n xu t. ạ  …” ấ ủ Chomsky đã chia các qui t c d n xu t c a văn ph m G thành b n lo i

Professor

.  Born  December of          Technology iườ  ta chia các văn ph mạ  thành          ,  Massachusetts         7  ,  1928  Philadelphia, Pennsylvania,

ạ D aự  vào đ cặ  đi mể  c aủ  t pậ  quy t cắ  mà ng các  nhóm  khác  nhau.  Noam  Chomsky  (Institute Institute   USA) đã phân lo iạ  văn ph m thành b nố  nhóm:

 Nhóm 0:  Văn phạm không hạn chế (hay văn phạm ngữ cấu, văn phạm

tổng quát),

 Nhóm 1:  Văn phạm cảm ngữ cảnh,

 Nhóm 2:  Văn phạm phi ngữ cảnh,

 Nhóm 3:  Văn phạm chính quy.

Dưới đây là các định nghĩa cho các nhóm văn phạm nói trên.

nghĩa I.15

, , S, P > mà không có m tộ  ràng bu cộ  nào đ iố   v iớ   cượ  g iọ  là văn ph mạ  t ngổ  quát  hay văn ph mạ  không

Đ nhị Văn ph mạ  G = < (cid:0) các quy t cắ  c aủ  nó đ h nạ  ch .ế

(cid:0) (cid:0) Như  vậy,  các  quy  tắc  trong  văn  phạm  nhóm  0  có  dạng:  (cid:0) ,  với  (cid:0) (cid:0) =

20

* (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ((cid:0) (cid:0) Δ, α’, α’’, (cid:0)

* (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ) α’Aα’’, A (cid:0) .Các quy tắc của văn phạm nhóm 0  được gọi là quy tắc không hạn  chế.  Ngôn ngữ do văn phạm nhóm 0 sinh ra  được gọi là ngôn ng  ữ tổng quát. Văn  phạm  G  =  <  (cid:0) ,  với (cid:0) (cid:0) = α’Aα’’, A (cid:0) (cid:0) Δ, α’, α’’, (cid:0) , và | (cid:0) | ≤ | (cid:0) cượ |, đ (cid:0) ((cid:0)

ữ ả ,  ,  S,  P  >  mà  các  quy  tắc  của  nó  đều  có  dạng:  (cid:0) ) g iọ  là văn ph mạ  nhóm 1hay  văn ph mạ  c mả  ng  c nh.

Các  quy  tắc  trong  văn  phạm  nhóm  1  được  gọi  là  quy  tắc  c mả   ngữ  c nhả . Ngôn  ngữ  do  văn  phạm cảm  ngữ cảnh sinh ra được gọi là  ngôn ngữ  cảm ngữ cảnh.

Các  văn  phạm mà  các  quy  tắc  của  chúng  có  dạng  trên,  đồng  thời  chứa (cid:0) , cũng được xếp vào lớp văn phạm nhóm 1.

thêm quy  tắc  rỗng  S(cid:0) Thí dụ 1.12:

(cid:0) Cho văn phạm:  G = <{1},  {S, A, B}, S,  P >, với P =  {S(cid:0) , S(cid:0) 1A, 1 1 1

2n A(cid:0) 1B, B(cid:0) 1A,  A(cid:0) 1}. Khi đó, G ) = {1 | n là văn phạm chính quy và L(G 1 1

2n 2n (cid:0) (cid:0) 0}.  Thật vậy, sử dụng quy tắc 1,  ta  có  S├  1 ,  ((cid:0)

(cid:0) =  1 ,  với  n  =  0),  sử  (cid:0) 1) liên tiếp cặp quy  tắc 3 và 4, cuối cùng là

dụng quy tắc 2, rồi n­1 lần (n (cid:0) quy tắc 5, ta có:

2n­2 2n­2 S  ├ 1A ├ 11B ├ 111A ├ … ╞ 1(1 )A ├ 1(1 )1 = 1 2n .

21

ấ ủ ộ ố ữ 1.3. M t s  tính ch t c a ngôn ng

Một s  ố tính chất của văn phạm và dẫn xuất

ị

Đ nh lý I.1 Với mọi văn phạm G = < (cid:0) , , S, P >, luôn tồn tại một văn phạm G’ =

<  (cid:0) ’, ’, S’, P’ > tương đương với văn phạm G, tức là L(G) = L(G’).

Ch ngứ  minh:

Gi ả sử có văn phạm G = < (cid:0) , , S, P >, ta xây dựng văn phạm G’ = <

(cid:0) ’, ’, S’, P’  >, trong đó:

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) ’ =  (cid:0) , và với mỗi a (cid:0) ,  ta bổ xung  một  ký hiệu    (cid:0) và (cid:0) (cid:0) }

(cid:0) (cid:0) gọi là đối ngẫu của  a, đặt Г  = {  |  a (cid:0) (cid:0) Г

(cid:0) (cid:0) ’ = (cid:0) (cid:0) S’ = S

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) P’  =  P (cid:0) P ,  v iớ   P =  {    (cid:0) (cid:0) a  |  (cid:0) a  (cid:0) (cid:0) },  P =  {(cid:0) | 2 (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) 2 (cid:0) và  (cid:0) 1  (cid:0) P},  (cid:0) 1  (cid:0) là  các  xâu  (cid:0) (cid:0) đã  đ (cid:0)

(cid:0) (cid:0) (cid:0) L(G’):  Lấy  bất  kỳ  (cid:0)

G G(cid:0) (cid:0) L(G),  khi  đó  ta  có  G (cid:0) ├ ├ (cid:0) và  (cid:0) cượ   thay  các  ký  hi uệ   thu cộ   (cid:0) b ngằ  các ký hi uệ  đ iố  ng uẫ  c aủ  nó. Dễ th yấ  r ngằ  L(G) = L(G’), th tậ  v yậ  ta  sẽ ch ngứ  minh hai bao hàm th c:ứ a./  Ch ngứ   minh  L(G)  (cid:0) , tức là ta có một dãy  suy  dẫn  trực  tiếp  trong  G:  S  =  (cid:0) … S╞ 0 1

G  (cid:0) ├ =  (cid:0) ,  với  dãy  suy  dẫn  này,  ta  thay  mọi  quy tắc trong các suy dẫn (cid:0) k i

G  (cid:0) ├ , ( 0 ≤ i ≤ k­1), bởi các quy tắc tương ứng trong P và P ,  ta  nhận i+1 2

G’ 1  G’  (cid:0) G’  (cid:0) ├ ├ =  (cid:0) ,  do được  dãy  các  suy  dẫn  trong  G’:  S  =  (cid:0) ’ …  ├ ’ m ’ 0

G’(cid:0) (cid:0) (cid:0) (cid:0) đó  ta  có S╞ , tức là (cid:0) (cid:0) L(G’).  Vậy L(G) (cid:0) 1  (cid:0) L(G’).

(cid:0) (cid:0) b./  Ch ngứ   minh  L(G’)  (cid:0)

G’(cid:0) (cid:0) L(G’),   khi  đó   ta  có  G’  G’  G’  (cid:0) ├ ├ (cid:0) L(G):  Lấy  bất  kỳ  (cid:0) , tức là ta có một dãy  suy dẫn trong G’: S = (cid:0) S╞ … ├ ’ ’ 1 0

(cid:0) G’  (cid:0) ├ = (cid:0) , trong các suy dẫn (cid:0) , ( 0 ≤ i ≤  k­1),  ta  thay  mọi  kí  hiệu  a i i+1 (cid:0) (cid:0) (cid:0) ’ k  (cid:0) Г  bởi  các  ký  hiệu  tương  ứng  a  (cid:0) ,  khi  đó  mọi  quy  tắc  đều thuộc P, 1

G G  (cid:0) G  (cid:0) ├ ├ ta nhận được dãy các suy dẫn trưc tiếp trong G: S = (cid:0) … ├ 0 1 k

22

G(cid:0) (cid:0) (cid:0) = (cid:0) , ta có  S╞ (cid:0) L(G).

, tức là (cid:0) ợ (cid:0) L(G). Vậy L(G’) (cid:0) ẫ Đ nị h lý I.2 (H p thành các suy d n)

ệ ế W=(V, P)  và cho  u1,…, un, v1,…, vn  là các xâu trong  V*.

*vn, thì ta có u1…un *v1…vn.

t lai   *v1,…, un Cho h  vi ờ ế u1  n u Bây gi

ứ ừ ậ ầ ị Ta th a nh n đ nh lý trên (không c n ch ng minh).

Tính đóng của lớp ngôn ng  ữ sinh bởi văn phạm

lý I.3

Đ nhị Lớp  ngôn  ngữ  sinh  bởi  văn  phạm  là  đóng  đối  với  phép  hợp  ((cid:0) ),  phép

giao (∩) và  phép nhân ghép ngôn ng  ữ (.)

Ch ngứ  minh:

Trước  hết,  ta  sẽ  chứng  minh  lớp  ngôn  ngữ  sinh  bởi  văn  phạm  là  đóng  đối  với  phép  hợp,  việc  chứng  minh  tính  đóng  của  lớp  ngôn  ngữ  sinh  bởi  văn  phạm  đối  với  các  phép  giao  và  phép  nhân ngôn ngữ là hoàn toàn tương  tự.

Giả sử L , L là các ngôn ngữ được sinh bởi văn phạm G = <(cid:0) , , 1

1 = <(cid:0) 2  , S , P >, G , S , P >, tức là L = L(G ), L = L(G 1 1 2 2 2 2 1 1 ). Ta chứng  2 2 (cid:0) 1  2 minh tồn tại văn phạm G sao cho  L(G) = L (cid:0) L 1 . 2 1

(cid:0) Xây dựng văn phạm G sinh ra ngôn ngữ L (cid:0) L như sau: G = <(cid:0) , , 1 2

S, P>, với:

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) = (cid:0) 1

(cid:0) 2 (cid:0) {S} Δ =  Δ 1

(cid:0) (cid:0) P = P 2  (cid:0) P (cid:0) {S(cid:0) S , S(cid:0) S } 1 2 2 1

(cid:0) (cid:0) L bằng cách chứng  minh hai bao  hàm 2 Ta sẽ chứng  minh L(G) = L 1

thức:

(cid:0) (cid:0) (cid:0) a./  Ch ngứ   minh  L(G)  (cid:0) :  Giả  sử  (cid:0) (cid:0) L(G),  khi  đó  tồn  tại (cid:0) L 1

(cid:0) L 2 G (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) một suy dẫn trong văn  phạm G: S ╞ , trong đó (cid:0) (cid:0) * = ((cid:0) )*. Do 1

cách xây dựng tập quy tắc P, nên trong suy dẫn S╞ (cid:0) 2 , có hai kh  ả năng:

23

G G1 (cid:0) (cid:0) ╞ (cid:0)  hoặc S├ , vậy (cid:0) (cid:0) là kết quả của suy dẫn S ╞ (cid:0) , S (cid:0) trong G 1 1 (cid:0) (cid:0) do đó (cid:0) 1 ).  (a) (cid:0) L(G 1

G G2 (cid:0) (cid:0) ╞ (cid:0)  hoặc S├ , vậy (cid:0) (cid:0) là kết quả của suy dẫn S ╞ (cid:0) , S (cid:0) trong G 2 2 (cid:0) (cid:0) 2 ).  (b) do đó (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) L(G 2 Từ (a) và (b), ta thấy (cid:0) , hay L(G) (cid:0) (cid:0) L (cid:0) L (cid:0) L 1 2

(cid:0) (cid:0) b./ Ch ngứ  minh L (cid:0) L (cid:0) L 2 (cid:0) L(G): Giả sử (cid:0) 1 (cid:0) L (cid:0) L , khi đó ta cũng có 1 2 1 (cid:0) (cid:0) (cid:0) (cid:0) hai khả năng: (cid:0) 2  ho c ặ (cid:0) (cid:0) L (cid:0) L : 1 2

(cid:0) (cid:0) (cid:0) G1  (cid:0) ╞ (cid:0)  Nếu (cid:0) (cid:0) L ), khi đó ta có suy dẫn S , do đó = L(G 1 1 1 (cid:0) trong G 1

G G1  (cid:0) ╞ ta cũng có suy dẫn S ├ (cid:0) là một suy dẫn trong G (vì theo cách xây S 1

dựng G, mọi quy tắc và mọi ký hiệu trong  G cũng đều thuộc G), như vậy 1 (cid:0) (cid:0) (cid:0) (cid:0) L(G).

(cid:0) (cid:0) (cid:0) G2  (cid:0) ╞ (cid:0)  Nếu (cid:0) (cid:0) L ), khi đó ta có suy dẫn S , do đó = L(G 2 2 2 (cid:0) trong G 2

G G2  (cid:0) ╞ ta cũng có suy dẫn S ├ (cid:0) là một suy dẫn trong G (vì theo cách xây S 2

dựng G, mọi quy tắc và mọi ký hiệu trong  G cũng đều thuộc G), như vậy 2 (cid:0) (cid:0) (cid:0)

(cid:0) (cid:0) (cid:0) (cid:0) L(G). Vậy  ta  luôn  luôn  có  (cid:0) (cid:0) L (cid:0) L(G).  Tức  là  ta  đã (cid:0) L(G),  do  đó:  L 1 2 (cid:0) chứng minh được rằng L(G) = L . (cid:0) L 2 1

Tương  tự,  để  chứng  minh  tính  đóng  của  lớp  ngôn  ngữ  sinh  bởi  văn  , ,

phạm đối với phép nhân  ghép ngôn ngữ, ta xây dựng văn phạm G = <(cid:0) S, P> sao cho L(G) = L(G ) như  sau: ). L(G 1 2

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) = (cid:0) 1

(cid:0) 2 (cid:0) {S} Δ =  Δ 1

(cid:0) P = P 2  (cid:0) P (cid:0) {S(cid:0) S S ).L(G ) 1 2 }.  Khi đó L(G) = L(G 1 2 1 2

24

Để  chứng  minh  tính  đóng  của  lớp  ngôn  ngữ  sinh  bởi  văn  phạm  đối  ,  ,  S,  P>  sao  cho  L(G)  =

với  phép  giao,  ta  xây  dựng  văn  phạm  G  =  <(cid:0) L(G ) (cid:0) 1 (cid:0) L(G ) như sau: 2

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) = (cid:0) 1

(cid:0) (cid:0) (cid:0) (cid:0) Г (cid:0) {S} 2 (cid:0) Г 2 1 2

(cid:0) (cid:0) ủ ẫ Δ = Δ 1 = {  | a (cid:0) Trong đó: Г ệ   } là tập các ký hiệu đối ng u c a các ký hi u 1 1

ẫ ủ ệ ậ ố trong , còn Г2= { | b } là t p các ký hi u đ i ng u c a .

P =  { S  }

ậ ậ ệ ọ ề    , mà m i ký hi u a đ u

ẫ ươ ứ ổ ở ợ ệ ố ượ ừ c t ủ ượ ắ Trong đó  là t p h p các quy t c nh n đ c thay đ i b i ký hi u đ i ng u t ng  ng c a nó đ

25

ƯƠ Ữ Ả Ạ CH NG 2. VĂN PH M PHI NG  C NH

ữ ả ẫ 2.1. Suy d n phi ng  c nh

ụ ề ữ ả ạ Các thí d  v  văn ph m phi ng  c nh

ả ễ ị ế ệ Theo tài li u [4], tác gi : Nguy n Th  Trúc Viên, có vi t:

ộ ượ ọ ữ ả c g i là phi ng  c nh (context free)

ọ “M t văn ph m  ậ nếu m i lu t sinh trong ạ G = (V, T, S, P) đ P có d ngạ

A → x,

trong đó A ∈ V còn x ∈ (V ∪T)*.”

ừ ị T  đó ta có Đ nh nghĩa II.1.

ị Đ nh nghĩa II.1

ữ ả ạ Văn ph m phi ng  c nh là m t văn ph m ọ ả   ạ G = (∑, ∆, P, S) mà m i s n

ề ắ ấ ộ ạ ủ xu t (hay quy t c) c a nó đ u có d ng:

→α A , trong đó A∈∆ và α∈(∑∪∆)*

ướ ế ộ ố ụ ề ữ ả ạ Tr c h t ta hãy xem m t s  thí d  v  văn ph m phi ng  c nh.

Thí dụ 2.1:

ế ạ ệ ộ ố ặ ắ Trong các sách văn ph m ti ng Vi ậ   t ta g p m t s  các quy t c thành l p

ư câu nh  sau:

ể ạ M t ộ câu (có th ) có d ng ch  ngủ ữ v  ngị ữ

ể M t ộ ch  ngủ ữ (có th ) là m t ộ danh từ

ể M t ộ ch  ngủ ữ (có th ) là m t ộ đ i tạ ừ

ể ừ M t ộ v  ngị ữ (có th ) là m t ộ ộ đ ng t

ể M t ộ danh từ (có th ) là mèo

ể M t ộ danh từ (có th ) là bò

ể M t ộ đ i tạ ừ (có th ) là tôi

M t ộ đ i tạ ừ (có th ) làể nó

ể ộ M t ộ đ ng t ừ (có th ) là ăn

ể ộ M t ộ đ ng t ừ (có th ) là n mằ

ể ộ M t ộ đ ng t ừ (có th ) là u ngố

ừ ấ ỏ ộ ố ể ậ ắ T  các quy t c còn r t ít i trên, ta có th  đã thành l p m t s  câu nh ư

sau:

Tôi n mằ

Nó ăn

26

Bò u ngố

Mèo n mằ

ậ ướ ơ ộ Trong các quy lu t trên thì các t

ể ư ch  ngủ ữ, đ ng t i đ n nh   ủ g ch d ộ ấ

ộ ự ế ạ ướ  g ch d

i kép nh   ế ễ ể ạ

ộ ộ ộ ư ể ạ ắ ơ ừ...  ừ ạ ễ   là các ph m trù cú pháp bi u di n cho m t c u trúc con c a m t câu. Còn các tệ  (hay ký hi uệ ) tr c ti p có m t ư tôi, mèo... là các từ Vi ặ   ừ ạ t ắ ọ câu,  trong các câu. N u ta bi u di n m t cách ng n g n các ph m trù cú pháp  ầ ượ ừ l n l ch  ngủ ữ, v  ngị ữ, danh từ, đ i tạ ừ, đ ng t   t là U, C, V, D, Đ, G thì ta có th  trình bày l i các quy t c trên m t cách súc tích h n nh  sau:

U CV

C Đ

V G

D mèo

D bò

Đ tôi

Đ nó

G ăn

G n mằ

G u ngố

ữ ả ả ạ ấ

ế ệ

ế ệ ằ ố Và đó chính là các s n xu t trong văn ph m phi ng  c nh, trong đó U, C, V, D, Đ, G là các ký hi u không k t thúc, còn “mèo”, “bò”, “tôi”, “nó”, “ăn”, “n m”, “u ng” là các ký hi u k t thúc.

ụ Thí d  2.2:

ớ BNF (backus­nuaur form), ta

ữ ậ Trong các ngôn ng  l p trình, v i ký pháp  ể ị ộ ị có th  đ nh nghĩa m t đ nh danh sau:

│ │ ữ ữ ị ị ị <đ nh danh> ::=   <đ nh danh>  <đ nh danh> 

s >ố

│ │ │ │ ữ ::= A  B C ... Z

ố │ │ │ │ │ │ │ │ │ ::=0 1 2 3 4 5 6 7 8 9

ữ ả

ắ ị ữ ế ệ ố

,→ ư   Đó cũng chính là các quy t c phi ng  c nh, trong đó ::= có nghĩa nh   ệ   các kí hi u không k t thúc là <đ nh danh>, ,  và các kí hi u ế k t thúc là A,B,C,... Z,1,2,...,9.

Thí d  2.3ụ :

│ ứ ươ Trong Ch

ữ L  = {an  b  n n≥0 ng II ta đã ch ng minh r ng ngôn ng   ở ữ ạ ằ } là  ộ ể ượ ả   c s n sinh b i m t văn ph m phi

không chính quy. Ngôn ng  đó có th  đ ng  c nh ữ ả G=(∑, ∆, P, S) trong đó:

27

∑={a,b}, ∆={S} và

ồ ắ S aSb→ │ε P g m các quy t c:

ư ậ ữ ả ữ ữ ạ Nh  v y ngôn ng  đó là ngôn ng  phi ng  c nh (lo i 2).

:

ượ ả ạ ở c s n sinh b i văn ph m mà các

Thí d  2.4ụ Ngôn ng  ữ L={wwR│w∈{a,b}*} đ ắ quy t c là:

│ε → │ S aSa bSb

ữ ả ữ ữ ậ V y ngôn ng  này cũng là ngôn ng  phi ng  c nh.

ấ ơ ả ữ ả ẫ Tính ch t c  b n (phân rã các suy d n phi ng  c nh)

ằ ợ 2 Đ nh lý I.

ở ươ  ch ộ ng I nói r ng ta có th   ể ẫ ẫ

ớ i thành m t suy d n. Ph d n phát bi u ng t l

i nói chung, song l ẫ ộ ộ ậ ẫ

ữ ả ủ ẫ ấ

ộ   ẫ ủ ể h p thành ị  các suy d n c a m t ớ   ệ ế ạ ượ ạ i là không đúng v i c l h  vi t l ữ ả ạ ạ ọ ệ ế ạ i đúng v i các văn ph m phi ng  c nh: ta có m i h  vi   ớ   ữ ả th  ể phân rã  m t suy d n phi ng  c nh thành các suy d n con đ c l p v i ấ ơ ả ượ ẫ   nhau. Tính ch t c  b n này c a các suy d n phi ng  c nh là r t hay đ c v n ứ ụ d ng trong các ch ng minh sau này.

ả ễ ế ệ Theo tài li u [1], tác gi : nguy n Văn Ba, có vi t:

ặ ạ ộ

ộ ọ ∪∆. Cho   ∈V*. thế “Cho G=(∑,∆,P,S) là m t văn ph m phi ng  c nh và đ c V= ∑ 1...un  k v, trong đó u1 ∈ V* v i m i i=1,...,n và v

ớ ẫ m t suy d n trong G u ọ thì v i m i i=1,..., n t n t i v ữ ả ớ ồ ạ i ∈V* và ki∈N sao cho:

k i

i vi, i=k, và v1…vn=v.”

ọ ớ V i m i i=1,...,n: u

ừ ị T  đó ta có Đ nh lý II.1.

ị Đ nh lý II.1

ộ Cho  G=(∑,∆,P,S) là m t văn ph m phi ng  c nh và đ c

ộ ạ  G u1...un  k v, trong đó u1 ∈ V* v i m i ặ V= ∑∪∆. Cho  ọ  i=1,...,n và v∈V*. thế

ẫ m t suy d n trong ọ i=1,...,n t n t ớ thì v i m i ữ ả ớ ồ ạ vi ∈V* và ki∈N sao cho: i

k ọ  i=1,...,n: ui

i vi, i=k, và v1…vn=v.

ớ V i m i

ứ Ch ng minh

ứ ườ ạ ằ ị ợ n=2. Ta ch ng minh đ nh lý b ng quy n p trên k.

ể

ự ế ở ị ủ ẫ

β A→β∈P.  Tr ng h p  (cid:0) N u ế k=0: hi n nhiên. (cid:0) N u ế k=1: u1u2 1v. B i đ nh nghĩa c a suy d n tr c ti p ta có u1u2=u’Au”, v=u’ u’’ và

ườ ể ợ Hai tr ng h p có th  là:

│ ườ + Tr ng h p │ ợ u’   u│ │ 1 ta có u’=u1t và u2=tAu’’

Đ t ặ v1=u1 và v2 = t u’’β

28

ả có:

Qu  nhiên ta  u1 0 v1 và u2 1 v2; v=v1v2 và 0+1=1.

=u’At và u’’=tu2.

│ ườ ộ │ ợ u’ <  u ố ứ , u1 +Tr ng h p │ │ 1 ta có, m t cách đ i x ng

Đ t ặ v1=u’βt và v2=u2

ả

ể ủ ị ẫ ọ s  phát bi u c a đ nh lý là đúng v i m i suy d n có đ ộ

k­1w 1v.

Qu  nhiên ta có : u1 1v1 và u2 0v2; v=v1v2 và 1+0=1. (cid:0) N u ế k>1: Gi ỏ ả ử ứ ớ ộ ớ k. dài nh  thua k và ta ch ng minh nó cũng dúng v i đ  dài

Vì: u1u2 kv, và k>1, v y ậ u1u2

k 1w, u2

ả ế thi ạ t quy n p, ta có :

2w2, k1+k2=k­1, và w1w2 v.

ở B i gi w=w1w2 v i ớ u1 k

h 2v2, h1+h2=1.

1v1, w2

ở ứ ơ ở ự ệ ậ ạ ộ :

k

k

+h 1

1v1, u2

+h 2

2v2, k1+h1+k2+h2=k.

B i ch ng minh đã th c hi n cho đ  dài 1 (c  s  quy n p), v y thì v=v1v2 v i ớ w1 h

ư ế Nh  th  ta có : u1

ệ ổ ợ ườ ễ ợ  Tr ng h p n>2 là d  dàng

ng h p n>2: Vi c t ng quát hóa cho tr ạ ằ ườ (b ng quy n p trên n).

ấ ơ ả ượ ể ệ k. Chúng ta

ể Tính ch t c  b n nêu trên đ ể cũng có th  phát bi u nó theo quan h ố ớ c phát bi u đ i v i quan h     ệ * nh  sau. ư

ệ ả H  qu  II.1

*v trong m t văn ph m phi ng  c nh, thì t n t

*v1,...,un

*vn.

ữ ả ạ ộ N u ế u1...un ồ ạ v1,...,vn đ  choể i

v=v1..vn và u1

Cây suy d nẫ

ễ ả Nguy n Th  Trúc Viên, có vi

ệ Theo tài li u [4], tác gi ộ ị ứ ự ộ t “ ấ ẫ  là m t cây d n xu t cho ế Cho G = (V,  G nếu

ộ T, S, P) là m t VPPNC. M t cây có th  t và ch  nỉ ếu…”

ừ ị T  đó ta có Đ nh nghĩa II.2.

ị Đ nh nghĩa II. 2

ạ

ε  M t cây suy d n trong m t văn ph m phi ng  c nh  ộ ộ ẫ ượ ầ ử ỗ ỉ ắ ộ ữ ả G=(∑,∆,P,S) là m tộ   ộ ậ ∪∆∪{ } và thu c t p ∑

c g n m t nhãn là m t ph n t ệ ả ộ cây mà m i đ nh đ ề tho n mãn các đi u ki n sau:

ệ ủ ố ầ S.

ủ ệ ộ

ế ầ ử ủ ỗ ỉ ỗ ộ ệ ủ ế ộ (cid:0) Nhãn c a g c là ký ki u đ u  (cid:0) Nhãn c a m i đ nh trong là m t ký hi u không k t thúc (m t ph n t ầ ử  ặ    c a ∑) ho c là

ỗ ộ ủ c a ∆). Nhãn c a m i lá là m t ký hi u k t thúc (m t ph n t ε  (xâu r ng).

29

ớ ỉ (cid:0) V i m i đ nh trong, n u nó có nhãn là

ỗ ỉ ầ ượ ộ ả ế t có nhãn là ủ A và các con c a nó là các đ nh   X1,X2,...,Xk, thì A X→ 1X2...Xk ph i làm t s n xu t ấ   ả

n1,n2...,nk l n l c a ủ G.

ộ ế

ể ạ ệ ề ằ ỉ (cid:0) N u m t lá có nhãn là  , thì lá đó ph i là con duy nh t c a cha nó (đi u ề   ấ ủ ả ε ư    vô ích vào cây suy

ε ế ệ này ch  nh m đ  h n ch  ci c tùy ti n đ a thêm nhi u  d n).ẫ

ẫ ạ ộ ở

ộ ệ ủ ộ ỉ ế ọ ớ ế

ượ ọ  Cho m t suy d n, ta g i cây con là m t cây t o thành b i m t đ nh và   ố   ọ ậ m i h u du  c a nó, cùng v i các nhãn và các cung liên k t chúng. N u g c ủ c a cây con có nhãn là A, thì cây con đó đ c g i là m t ộ A­cây.

ọ ả ủ ế ế ẫ ộ

 Ta g i bi n (hay k t qu ) c a m t cây các suy d n hay c a m t ế ủ ằ ạ ủ ậ ự ừ á  c a cây theo tr t t ộ  A­cây     trái qua t

là xâu t o thành b ng cách ghép ti p các l ph i.ả

Thí dụ 2.7:

ữ ả ạ ộ Cho G=({a,b},{S,A},P,S) là m t văn ph m phi ng  c nh, trong đó P g mồ

ắ các quy t c sau:

→ │ S aAS a

→ │ │ A SbA SS ba

ộ ượ aabbaa đ

ừ ả c cho trong Hình   trái qua ph i, cho phép nh t l n l 2.1, trong đó  ặ ầ ượ   t

ể ậ ẫ M t cây suy d n có biên là xâu  ỉ ta ch  ra cách đi (men theo các cành) t các lá đ  thành l p ra xâu đó.

ộ ẫ Hình 2. M t cây suy d n

ủ ẫ ộ Hình 2.2 cho m t cây con c a cây suy d n trên .

30

ộ Hình 2. M t A­cây

31

ị Đ nh lý II.2

ộ ượ ả ữ ả G, m t xâu

ộ ẫ ủ w là đ ạ ộ ỉ ở   ạ c s n sinh b i Cho m t văn ph m phi ng  c nh  ủ   G w) khi và ch  khi có m t cây suy d n c a văn ph m đó mà biên c a

G (S* nó là w.

ứ Ch ng minh

ượ ấ ổ ứ ẳ ộ ị Đ nh lý II.2 đ c kh ng đ nh khi ta ch ng minh m t tính ch t t ng quát

ị ộ ơ h n m t chút là:

G u khi và ch  khi t n t

ế ệ ọ ớ ồ ạ ỉ V i m i ký hi u không k t thúc A, A* i m t ộ A­cây

có biên u.

ượ ự ệ ề ỉ c th c hi n theo hai chi u (khi,ch  khi).

ế ế ứ t u là biên c a m t ộ A­cây và ta ch ng minh

c h t ta gi ằ ả  thi ạ ủ ỉ ủ ố ứ Phép ch ng minh đ (cid:0) Tr A* ướ Gu, b ng quy n p trên s  m các đ nh trong c a cây. r ng ằ

ư ạ + m=1: Cây có d ng nh  trong Hình 2.3.

ộ ỉ ộ Hình 2. M t A­cây có m t đ nh trong

ư ế Nh  th  thì u=X1X2...Xk và A u→ ∈P. V y ậ A*u.

ọ ả ế thi

ậ ớ t r ng k t lu n là đúng v i m i cây có không quá  ả ử X1,X2,...,Xk là các h u du  s

ế

ở

ả  thi ừ ị ợ

* u1u2...uk (Hình 2.4). M t khác, n u

ặ ế i

Gu.

ệ ủ ậ ở ớ ậ ế ằ m­1  ệ  ỉ ộ A­cây có m đ nh trong. Gi Xi­cây,1≤i≤k, mà s  cácố ề ủ ố A. Chúng đ u là g c c a các  ố ủ   *ui, trong đó ui là biên c aủ   ạ ế ơ m. B i gi Xi t quy n p, ta có  ẫ 2  (h p   thành   các   suy   d n   )   ta   có:   ệ  ọ ậ ậ u=u1u2...uk là bên trái Xj cùng v i các h u du  c a nó. V y

+ m>1: Gi ỉ đ nh trong và xét m t  ự tr c ti p (con) c a g c  ỉ đ nh trong là ít h n  Xi­cây   (ui=Xi  n u  ế Xi∈∑).   T   Đ nh   lý   I. A=GX1X2...Xk  G ủ c a nó luôn luôn  biên c a ủ A­cây, cho nên ta có A*

32

ủ ộ Hình 2. M t A­cây và các cây con c a nó

ả ằ ạ ộ

ế A*  thi t  ồ ạ ủ ẽ ứ Gu và ta s  ch ng minh, b ng quy n p trên đ  dài ộ A­cây có biên là u. i m t

ấ ư ớ (cid:0) Bây gi ờ  ta gi ẫ ằ n c a dây d n, r ng t n t (cid:0) n=1: B y gi ờ A→u∈P và ta có m t ộ A­cây nh  trên Hình 2.3 v i biên là

u=X1X2...Xk.

ọ ả ệ ế ế ằ (cid:0) n>1: Gi

ớ ỏ thi ộ

ế A­cây có biên gi ả s

ớ i là  ả ử A  X→ 1X2...Xk là s n xu t đ ấ ượ ừ ị ẫ

ữ ả

ủ ỗ i m t

ậ

ể ỗ ằ ộ   t r ng v i m i ký hi u không k t thúc A, n u ta có m t u. Hãy    c dùng AG X1X2...XkG*u. T  Đ nh lý II.1   u= u1u2...uk và XiG*ui, 1≤i≤k. Vì r ngằ   ộ Xi­ ồ ạ ỏ ẫ XiG*ui, 1≤i≤k là nh  thua n, cho nên t n t ư ộ A­cây nh  trong Hình   ộ Xi­cây, 1≤i≤k. A­cây đó có biên

suy d n ẫ A*u mà đ  dài là nh  thua n, thì ta có môt  ẫ A*u có đ  dài n. Gi ộ ộ xét m t suy d n  ấ ủ ứ ướ trong b c th  nh t c a suy d n, nghĩa là  ẫ (Phân rã các suy d n phi ng  c nh) ta có  ộ đ  dài c a m i suy d n  ừ cây, 1≤i≤k có biên là ui. T  đó ta có th  thành l p m t  ớ ố ủ ố ố A v i g c c a m i m t  2.4 b ng cách n i g c  là xâu u= u1u2...uk.

ẫ ẫ ả ậ ằ Suy d n trái, suy d n ph i và tính nh p nh ng

ấ ở ộ Nh  đã th y

ế ủ ặ ẫ ố ẫ S*u. Trong s  các suy d n này, ta chú ý đ c bi ẫ ươ  trên, m t cây suy d n mà k t q a là u t ệ ớ t t ớ   ứ ng  ng v i ẫ   i hai suy d n

ư ề nhi u suy d n  sau:

ẫ ẫ c thay

ở ỗ ướ  m i b ấ ệ ạ ế ệ ế ằ  Suy d n trái, đó là suy d n mà trong đó,  th  luôn luôn là ký hi u không k t thúc n m bên trá ượ c, ký hi u đ i nh t trong d ng câu.

ẫ ệ ả ẫ c, ký hi u đ ở ỗ ướ  m i b

 Suy d n ph i, đó là suy d n mà trong đó,  ằ ệ ế ả ấ

ượ   c ạ   ế thay th  luôn luôn là ký hi u không k t thúc n m bên ph i nh t trong d ng câu.

ứ ễ ủ ẫ ộ D  dàng ch ng t ộ   ữ  r ng có m t song ánh gi a các cây suy d n c a m t

ả ớ ỏ ằ ẫ văn ph m ạ G v i các suy d n trái(hay ph i).

33

ạ ậ ằ M t văn ph m phi ng  c nh ữ ả G = (∑, ∆, P, S) là nh p nh ng n u t n t ế ồ ạ   i

ộ ả ủ ế ẫ ộ m t xâu w∈(∑∪∆)* cùng là k t qu  c a hai cây suy d n khác nhau.

ộ ữ ừ ạ ạ Cùng m t ngôn ng  có th  đ

c sinh ra t ằ ạ

ữ ằ

ố ữ ậ ộ ậ ề ằ ạ ằ

ườ ữ ế ượ  vô h n các văn ph m khác   ậ   ạ ậ nhau,   trong   đó   có   văn   ph m   là   nh p   nh ng,   có   văn   ph m   là   không   nh p ữ ả ằ ậ ượ   nh ng. M t ngôn ng  phi ng  c nh đ c nói là nh p nh ng c  h u, hay nói ế ấ ả ọ t c  các văn ph m sinh ra nó đ u nh p nh ng. g n là nh p nh ng, n u t   ữ ư ậ ồ ạ ằ ứ i ta ch ng minh r ng t n t Ng i nh ng ngôn ng  nh  v y.

Thí dụ 2.8:

ữ ả ạ ắ ồ Cho G0 là văn ph m phi ng  c nh g m các quy t c sau:

→ │ │ │ E E+E E*E (E) a

ứ ố ọ ể ử Văn ph m này s n sinh các bi u th c s  h c trong đó các toán t là + và

ả ề ạ a. ạ * và các h ng toán đ u là

0

ộ ẫ Hình 2. M t cây suy d n trong G

ả a+a*a. ẫ Các câu suy d n cho trên Hình ế 2.5 có k t qu  là

ươ ứ Suy trái t ớ ng  ng v i cây đó là:

EE*EE+E*Ea+E*Ea+a*Ea+a*a

ả ươ ứ ẫ Suy d n ph i t ớ ng  ng v i cây đó là:

EE*EE*aE+E*aE+a*aa+a*a

ạ ế ả ộ ư Tuy nhiên ta l i còn có m t cây khác có cùng k t qu  là a+a*a, nh  trên

Hình 2.6.

34

0

ủ ộ ẫ Hình 2. M t cây suy d n khác c a G

ư ậ ậ ằ Nh  v y văn ph m

ượ ướ ể ộ ề ạ G0  là nh p nh ng. Đi u đó có nghĩa là trong văn c hay nhân c hi u theo hai cách:  c ng tr ức  a+a*a  đ

ph m  ạ G0  bi u thể tr c.ướ

ằ ư ể ạ ừ ậ ướ ộ ợ c phù tr :

ặ ự ệ ộ

ở

ị ươ ớ ng v i văn ph m i m t văn ph m ng đ

ạ G1, t ắ ậ Đ  lo i tr  nh p nh ng ta đ a thêm m t quy  (cid:0) Ho c là ta luôn luôn th c hi n các phép toán (c ng và nhân) theo th  t ứ ự  ả ừ ơ  trái qua ph i khi các phép toán đó không b  ngăn cách b i vòng đ n. Yêu t   ạ G0, nh ngư   ươ ộ ẫ ớ ầ c u này d n t ằ không nh p nh ng, và có các quy t c sau:

→ │ │ E E+T E*T T

→ │ T (E) a

ặ ướ ộ (cid:0) Ho c là ta luôn luôn th c hi n phép nhân tr

ệ ự ơ ư ở

ẫ ớ ươ ươ ạ ộ G2, t ng đ

i m t văn ph m khác   ắ ằ ậ c phép c ng khi chúng ớ ộ ị không b  ngăn cách b i vòng đ n ( u tiên phép nhân so v i phép c ng). Yêu   ớ G0, cũng không  ầ c u này d n t ng v i   nh p nh ng, và có các quy t c sau:

→ │ E E+T T

→ │ T T*F F

→ │ F (E) a

ứ ạ ứ ư Trong G2 các phép toán cùng m c  u tiên mà đ ng c nh nhau thì đ ượ   c

ứ ự ừ ự ệ ả th c hi n theo th  t t trái qua ph i.

ượ Các cây suy d n cho xâu a+a*a trong các văn ph m ạ G1+G2 đ ầ   c cho l n

ượ l t trên các Hình ẫ 2.7 và 2.8.

35

1

ẫ ủ ộ Hình 2. M t cây suy d n c a G

1

ẫ ủ ộ Hình 2. M t cây suy d n c a G

ế ổ ữ ả ạ 2.2. Bi n đ i các văn ph m phi ng  c nh

ộ ườ ứ ự ề ạ ng thì m t văn ph m còn ch a đ ng nhi u y u t

ẳ Thông th ạ ệ ẫ

ế ố ủ ẫ ộ

ề ổ

ươ ữ ạ vô ích, ữ   ch ng h n các ký hi u không tham gia vào suy d n ra các xâu c a ngôn ng , A B→ (A,B∈∆) làm kéo dài cac suy d n m t cách ả ấ hay là các s n xu t có d ng    ạ   ầ ở ậ ầ ự ự t. B i v y nhi u khi ta c n bi n đ i các văn ph m không th c s  là c n thi ươ thành các văn ph m t ế ế ố ng mà không còn các y u t ạ ế ng đ vô ích n a.

ạ ỏ ệ Lo i b  các ký hi u vô ích

36

ộ

ạ Cho m t văn ph m phi ng  c nh  ộ ế ồ ạ ữ ả G = (∑, ∆, P, S) và đ t ặ V=∑∪∆. M t kýộ   ,α β∈V*  và ẫ S*αXβ*w, trong đó i m t suy d n

ế hi u  ệ X∈V  là có ích n u t n t w∈∑*, n u không nó là vô ích.

ư ậ ệ ộ Nh  v y m t ký hi u có ích ả X ph i là:

ệ ữ ộ ồ 1) m t ký hi u h u sinh, nghĩa là t n xâu x∈∑* mà X*x.

ế ượ ệ ộ ồ ạ 2) m t ký hi u đ n đ c, nghĩa là t n t i hai xâu ,α β ∈V* đ  cho  ể S*αX .β

ổ ề ạ ỏ ệ (Lo i b  các ký hi u vô sinh) B  đ  II.1

ồ ạ ậ ọ T n t

ớ i m t thu t toán cho phép, v i m i văn ph m phi ng  c nh  ữ ả ọ ậ ươ ạ ộ ữ ả G mà  ạ ỉ ươ G’ ch  có các ký   ng đ ng

ệ ữ L(G)≠, thành l p m t văn ph m phi ng  c nh t hi u h u sinh.

ứ

ệ ữ ậ ậ ợ

ướ ế Ch ng minh (cid:0) Thành l p t p h p các ký hi u h u sinh Tr c h t ta đ t: ặ W0=∑,

*:A→α∈P}

v i ớ i>0, Wi=Wi­1∪{A∈∆│∃α∈Wi­1

ố ặ W và cu i cùng đ t:

ạ ư ả ằ ậ

Các t p ậ Wi l n d n ( ậ ầ Wi Wi+1) nh ng l ế ẽ ỉ ầ

ạ ng, và ng ng l

ự ự ấ ẽ Wk+1=Wk+2,v.v... và nh  th  thì

ẽ ứ ư ế ế ệ ợ ữ ạ   ớ i luôn ph i n m trong t p h u h n ế ả ừ Wi  s  ph i d ng. Vì th  ta ch  c n tính các   Wi  liên ti p khi   ừ ừ ưở   i khi chúng ng ng tăng, nghĩa là W=Wk.   ta cũng s  có  ∩ ữ   ậ ằ W ∆ chính là t p h p các ký hi u không k t thúc h u

V.  V y dãy các   chúng còn th c s  tăng tr ờ khi có Wk=Wk+1. B y gi Ta s  ch ng minh r ng  sinh.

ồ ạ ữ ệ ế ộ a) Cho A∈∆ là m t ký hi u không k t thúc h u sinh, nghĩa là t n t ộ   i m t

suy d n:ẫ

A=α0α1...αk=u trong đó u∈∑*, k≥1

*, và b ướ ế ướ c ti p b ọ i, αk­i∈Wt ớ c r ng v i m i

ỏ ượ ằ ứ ị c, căn c  vào đ nh nghĩa c a các  *, và cu i cùng thì ố ủ Wi  *. V y thì ậ A ∈ Wt

Ta có u ∈ ∑* = W0 ứ  đ ta ch ng t A∈W ∆.∩

ồ ạ i đ  choể A ∈ Wi ∩ ∆.Ta

ế ạ ằ b) Cho A ∈ W ∩ ∆. Th  thì t n t ẽ ứ s  ch ng minh b ng quy n p trên i r ng ộ ố i m t s  nguyên ữ ằ  A là h u sinh.

* đ  choể

ậ ở ị + N u ế i = 1, b i đ nh nghĩa c a ủ  W1, ∃u∈W0 A→u∈P, v y ta có

ữ A*u và A là h u sinh.

∩ ả ử ớ ữ + Gi ọ ố  s  v i m i s  nguyên k

*:A→α∈P}.

Ta có A∈Wi ∩ ∆ = (Wi­1 ∆)∩  ∪ {A∈∆│∃α∈Wi­1

ế ở thi

ế ệ ế ỗ N u  ế A∈Wi­1  thì nó là h u sinh b i gi ữ ả *.  B i gi ạ ả ở ế ạ t quy n p. N u không ta có t quy n p thì m i ký hi u không k t thúc A→α∈P  v i αớ ∈Wi­1 thi

37

ộ ậ α ề , đ u suy d n đ c m t xâu trên ∑. Cho nên suy ra A cũng v y, nói

trong  cách khác A là ẫ ượ ữ h u sinh.

ậ ạ (cid:0) Thành l p văn ph m G’

ố ể ậ ư ư   ạ G’=(∑,∆’,P’,S’) nh  sau và l u ý

Cu i cùng ta có th  thành l p van ph m  L(G)≠  S∈W ∆.∩ r ng ằ

Ta đ tặ ∆’=W ∆∩

P’={A→u∈P│A∈∆’, u∈(∑∪∆’)*}

ứ và  (cid:0) Ch ng minh L (G)=L(G’)

ằ ấ ả ẫ ề Rõ ràng L(G’) L(G), vì r ng t t c  các suy d n trong ẫ   G’ đ u là suy d n

trong G

ư ọ Ng i, gi x∈L(G) và x L(G’). Nh  m i suy d n c a

ệ ặ

ả ử ằ  s  r ng  ộ ấ ư ậ ệ ấ ẫ ộ

ư ế ế

ộ ế ẫ ượ ạ ẫ ủ  x trong  c l ộ ả   ế ử ụ G  có s  d ng ít nh t m t ký hi u không k t thúc trong ∆­∆’ ho c m t s n ả ử ụ ế P­P’ (và nh  v y v n ph i s  d ng m t ký hi u không k t thúc xu t trong    ữ   ệ trong ∆­∆’). Nh  th  thì đã có m t ký hi u không k t thúc trong ∆­∆’ là h u ậ ằ L(G)=L(G’). sinh. Mâu thu n này cho phép ta k t lu n r ng L(G) L(G’). T  đó ừ

Thí dụ 2.9:

Cho  G=(∑,∆,P,S) trong đó

∑={a,b}, ∆={S,A,B,C}

→ │ │ P={S aA bAB abA

→ │ │ A aB bA a

→ │ B aB bB

→ │ │ } C aA bS a

ậ V y thì: W0 = {a,b}

ở W1=W0∪{A,C} (b i các quy t c ắ A a→  và C a→ )

ở W2=W1∪{S} (b i quy t c ắ S aA→ )

W3=W2∪

W={a,b,S,A,C}, ∆’={S,A,C} Từ đó:

G’=(∑,{S,A,C}, P’,S) và

→ │ → │ → │ │ P’={S aA abAS, A bA a, C aA bS a}. v iớ

ệ H  qu  I ả I.2

ộ ạ Cho m t văn ph m phi ng  c nh ữ ả G. Bài toán L(G)=  là gi ả ượ i đ c.

ỉ ể ậ W. Qu  v y, ả ậ L(G)=  khi và ch  khi S W, và ta đã có cách đ  tính t p

ổ ề ạ ỏ ế ượ ệ (Lo i b  các ký hi u không đ n đ c) B  đ  II.2

38

ộ ạ

ớ i m t thu t toán cho phép v i m i văn ph m phi ng  c nh   ươ ộ ữ ả ậ ạ ỉ ữ ả G  ệ   ươ G’  ch  có các ký hi u ọ ng đ ng

ồ ạ T n t ậ thành l p m t văn ph m phi ng  c nh t ế ượ đ n đ c.

ứ

ậ ậ ệ ế ượ c

Ch ng minh (cid:0) Thành l p t p h p các ký hi u đ n đ ợ Ta đ t:ặ  W0={S}, U0=

V i ớ i>0: Wi=Wi­1∪{A∈∆│∃B∈Wi­1, ∃u1u2∈(∑∪∆)*: B  u→ 1Au2∈P}

Ui=Ui­1∪{a∈∑│∃BWi­1,∃u1,u2∈(∑∪∆)*: B u→ 1au2∈P}

ố ặ W=i, U=i Và cu i cùng đ t:

ế ằ ứ Ti p theo ta ch ng minh r ng:

ữ ề ệ ậ ượ + Có th  tính các t p W và U m t cách h u hi u ; đi u này đ c suy ra

ừ ự ệ ể ộ ế Wi+1=Wi thì  k>1 : Wi+k=Wi+1=W và Ui+k=Ui+1=U. s  ki n n u t

ế

ượ ươ ệ   ậ U là t p các ký hi u c, và  ư ở ổ ề ự    B  đ  II.1,  nh   ng t ế + W là t p các ký hi u không k t thúc đ n đ c ch ng minh t

ứ ậ ể ậ ế ế k t thúc đ n đ ế xin chuy n đ n đ c gi

ạ ậ

ế ế ậ ệ ượ ề ượ c. Đi u này đ ộ ộ ả ư  nh  là m t bài t p. (cid:0) Thành l p văn ph m G’ Ti p đ n ta thành l p văn ph m ạ G’=(U,W,P’,S)

ễ ể ằ

trong đó: P’={A→u∈P│A∈W và u∈(U∪W)*} (cid:0) D  dàng ki m ch ng r ng L(G)=L(G’). ứ Thí dụ 2.10:

ế ụ ụ ở ừ ạ Ti p t c thí d trên, t văn ph m i, ta có:

W0={S}, U0=

W1=W0∪{A}, U1=U0∪{a,b}

W2=W1, U2=U1

W={S,A}, U={a,b} V yậ :

ạ ươ ươ ế ượ ỉ ồ ệ và văn ph m t ng đ ng v i ớ G’ ch  g m các ký hi u đ n đ c là:

G”=({a,b},{S,A},P”,S)

│ trong đó: P’’={S→aA abAS, A bA a → │ }.

39

ị Đ nh lý II.3

ề ể ượ ả ừ ộ M i ngôn ng  phi ng  c nh đ u có th  đ c s n sinh t ạ    m t văn ph m

ữ ả ệ ỗ ữ ả ỉ ữ phi ng  c nh ch  có các ký hi u có ích.

ứ Ch ng minh

ữ ụ

ượ =L(G) và L≠. Áp d ng lên  ỉ ữ

Cho m t ngô ng  phi ng    B  đ  II.1 ta thu đ ụ ế ụ ậ ở ổ ề G cách thành  ệ ạ G’ ch  có các ký hi u h u sinh.   ộ ượ   c m t văn B  đ  II.2 ta thu đ

ữ c nh L ả ộ c m t văn ph m  G’  cách thành l p  ế ượ ệ ộ ậ ở ổ ề l p  Ti p t c áp d ng lên   ỉ ph m ạ G” ch  có các ký hi u đ n đ c.

Rõ ràng r ngằ L(G’’)=L(G’)=L(G)=L

ứ ệ ỉ Ta hãy ch ng minh r ng ằ G” ch  có các ký hi u có ích.

ả ử ệ ộ ế s  trong G” có m t ký hi u vô ích ừ ổ ề X. T  b  đ  II.2, X là đ n đ ượ   c,

Gi nghĩa là:

G”* Xα β

α β ∃ , : S

ồ ệ ấ ả Vì G’ bao g m t ả t c  các s n xu t ấ G”, và G’ ch  cóỉ

ệ ữ ấ ả t c  các ký hi u và t ậ các ký hi u h u sinh, v y ta có:

S G”* Xα βG’*u, u∈∑*

ọ

ệ ế ẫ Suy d n trong  *u đ u là đ n đ Xα βG’

ổ ề ượ ề d n ẫ c (t ư ạ B  đ  II.2 và chúng còn l u l ầ ệ G’ này cho ta th y r ng m i ký hi u dùng trong ph n suy   ị ạ ỏ ở    S). V y các ký hi u đó không b  lo i b  b i ừ ạ G”. T  đó ta có: ấ ằ ậ ừ i trong văn ph m

SG”* Xα βG”*u

ề ộ ề ẫ   G”. Đi u mâu thu n

ế ệ ậ ệ Đi u đó có nghĩa là X là m t ký hi u có ích trong  G” không có ký hi u vô ích. này cho ta k t lu n là: trong

Chú thích

ụ

ạ ỏ ế ả ạ ư ầ ả ổ ề c) nh  trên là c n thi t. Đ o l ồ   B  đổ ề  II.2 (lo i bạ ỏ  ể ẫ ớ ế   i k t qu  sai i có th  d n t

áp d ng B  đ  II.1 (lo i b  vô sinh) r i ượ ụ ư ậ ự Tr t t ế không đ n đ nh  trong thí d  sau đây:

Thí dụ 2.11:

Xét văn ph m:ạ

S AB a→ │

A a→

ụ ớ ả ổ ề ị ạ ạ ấ S AB→ , và văn ph m thu

ượ Áp d ng B  đ  II.1, B b  lo i cùng v i s n xu t  c là: đ

S a→

A a→

40

ổ ề ị ạ ế ượ ụ ỉ Áp d ng B  đ  II.2, A b  lo i vì không đ n đ c, và ta ch  còn:

S a→

ế ổ ề ướ ụ , áp d ng B  đ  II.2 tr ng

ứ ự N u ti n hành theo th  t ấ ệ ượ ạ c l ế ổ ề ụ ạ

ả ậ ạ ạ ế ạ ượ lo i đ ớ ả v i s n xu t c, ta không c ký hi u và s n xu t nào. Ti p đó áp d ng B  đ  II.1, ta lo i B cùng i là: ấ S AB→ . V y văn ph m còn l

S a→

A a→

ệ ẫ v n còn có ký hi u vô ích là A.

ε ạ ỏ ả ấ Lo i b  các  ­s n xu t

ε ả ấ ả

ấ ứ ε ữ ứ ế

ạ ừ ườ ở ộ ư ả ả ạ Các  ­s n xu t (t c là s n xu t có d ng A ) không ph i là vô ích hoàn ả ạ t văn ph m ph i ch a ít ợ ng h p đó thì các →ε ấ ). Nh ng ngo i tr  tr

ε ấ ừ ộ toàn, b i vì khi xâu   là thu c ngôn ng , thì nh t thi →ε ườ ấ ấ ng là S nh t m t  ­s n xu t (th ε ả ể ạ ỏ ­s n xu t là th a, và có th  lo i b .

ị Đ nh lý II.4

ữ ả ạ ậ   Cho  G=(∑,∆,P,S) là m t văn ph m phi ng  c nh. Ta có th  thành l p

ạ ả ấ ộ ộ m t văn ph m phi ng  c nh ể ữ ả G’=(∑,∆,P’,S’) không có s n xu t mà:

L(G’)=L(G)­{ }.ε

ứ

ậ ậ ế ợ ỗ

Ch ng minh (cid:0) Thành l p t p h p các ký hi u không k t thúc sinh ra xâu r ng ệ Ta đ t:ặ E0={A A│ →ε∈P}

v i ớ i>0: Ei=Ei­1∪{A│∃u∈Ei­1* : A→u∈P}

E = i và

ế Th  thì:

ữ ẽ ộ ệ ậ E m t cách h u hi u, nghãi là ta s  thu đ ượ E sau c

ộ ố ữ ạ ể + Ta có th  tính t p  m t s  h u h n phép toán.

ệ ế ợ

ậ + E chính là t p h p các ký hi u không k t thúc sinh ra (nói riêng) xâu E={A∈∆│A* }ε ỗ r ng:

ị Vi c ch ng minh cho các đi u kh ng đ nh này m t l n n a l

ộ ầ ộ ề ổ ề ự ư ả ẳ  nh  trong B  đ  II.1. Xin dành cho đ c gi ệ ứ ệ ươ ng t ữ ạ ượ   i đ c ư ộ    nh  m t bài

ự th c hi n t t p.ậ

ậ ậ ả ấ

ứ (cid:0) Thành l p t p các s n xu t P’ Ta thành l p ậ P’ căn c  trên P theo hai b c:ướ

ớ ư ấ ả ấ ấ A X→ 1X2...Xn∈P ta đ a vào P’ t ả t c  các s n xu t có

ỗ ả + V i m i s n xu t  A→α1α2...αn trong đó: d ng ạ

41

1) N u ế Xi E thì αi=Xi

2) N u ế Xi∈E thì αi=Xi ho c ặ αi=ε

ấ ạ ỏ ấ ả ε t c  các  ­s n xu t.

ứ ố L(G’)=L(G)­{ }ε

ả + Lo i b  t (cid:0) Cu i cùng ch ng minh  + L(G’) L(G)­ { }ε

ε ε ả ấ ả ậ Vì G’ không có  ­s n xu t,   không thu c ứ   ộ L(G’). V y thì còn ph i ch ng

ấ minh tính ch t sau:

G’x thì A*Gx

ớ V i m i ọ A∈∆ và m i ọ x∈∑*, n u ế Ai (2­1)

ấ ­ Tính ch t này đúng v i ớ i=0.

ớ ả ế ằ ­ Ta ch ng minh nó cũng đúng v i ớ i+1 v i gi thi ớ   t r ng nó đã đúng v i

ẫ ộ ọ ứ m i suy d n có đ  dài cho t ớ i. i

i G’x, v i ớ Y1,...,YP ∈V∈∑∪∆.

Cho AG’Y1...YP

ở ấ ơ ả ữ ả ủ ệ ạ ả ả

ế B i tính ch t c  b n c a văn ph m phi ng  c nh (H  qu  II.1) và gi ạ t quy n p, ta có: thi

YjG*xj đ i v i (2­2) ố ớ j=1,...,p và x=x1...xp

1,...,αp,αp+1 c a E* sao cho: ủ

ị Do đ nh nghĩa c a P’, có các xâu α ủ

ấ ạ G (2­3) A→α1Y1...αpYpαp+1 là m t s n xu t trong văn ph m  ộ ả

ở ị B i đ nh nghĩa c a ủ  E ta có:

αj*Gε v i ớ j=1,...,p (2­4)

ừ ư ế 2­1) đã

ứ ượ T  các tính ch t ( c ch ng minh v i ấ 2­2), (2­3), (2­4) ta có  A*G  x  và nh  th  tính ( ớ i+1. đ

+ L(G’) L(G)­{ }ε

ỉ ầ ứ ằ Ch  c n ch ng minhh r ng:

Gx thì A*G’x

ớ ớ V i m i ọ A∈∆ và v i m i ọ x∈∑+, n u ế Ai (2­5)

ấ ­ Tính ch t là đúng v i ớ i=0.

ớ ả ế ằ ­ Ta ch ng minh nó cũng đúng v i ớ i+1 v i gi thi ớ   t r ng nó đã đúng v i

ẫ ộ ọ ứ m i suy d n có đ  dài cho t ớ i i

i Gx v i ớ X1,...,Xp∈V

AGX1...Xp Cho

ấ ơ ả ủ ữ ả ạ Theo tính ch t c  b n c a văn ph m phi ng  c nh, ta có:

n jGxj v i ớ j=1,...,p trong đó nj

Xj (2­6)

ỉ ố ủ ứ ủ Cho k1,...,kq là dãy tăng c a các ch  s  c a các xâu ỗ xj không r ng, t c là:

ừ ỗ x=xk1...xkq V i ớ j t 1 đ n (2­7) ế q, xkj là không r ng và

ở ị ủ B i đ nh nghĩa c a ủ P’ và c a dãy kj, ta có:

42

ộ ả A X→ k1...Xkq là m t s n xu t c a ấ ủ P’ (2­8)

ỉ ế T  (ừ 2­6),(2­7) và g a thi ạ t quy n p ta có:

Xkj*G’xkj (2­9)

ư ế ấ   ấ 2­7),(2­8) và (2­9) ta có: A*G’x và nh  th  tính ch t

T  các tính ch t ( ứ ớ i+1. ừ ượ (2­5) đ c ch ng minh v i

Thí dụ 2.12:

Cho văn ph mạ :

→ │ → │ε → │ → S ABC, A BB , B CC a, C AA b

Ta có: E={A,C,B,S}

ε ạ ươ ươ ấ ậ ả Văn ph m t ng đ ng không có  ­s n xu t l p theo cách trên là:

│ │ │ │ │ │ → S ABC BC AC AB A B C

A BB B→ │

→ │ │ B CC C a

→ │ │ C AA A b

ệ ả H  qu  II.3

ộ ạ Cho m t văn ph m phi ng  c nh ữ ả G. Bài toán ε∈L(G) là gi ả ượ i đ c.

ỉ ể ∈L(G) khi và ch  khi S∈E={A A*│ ε} mà t p  ậ E  là có th  tính

ượ Qu  v y, ε ả ậ ư c nh  trên. đ

ị Đ nh lý II.5

ộ ỗ

ậ

ạ ấ ạ Cho m t văn ph m phi ng  c nh  ộ ể có th  thành l p m t văn ph m phi ng  c nh  ε ả vô ích, và không có  ­s n xu t sao cho ữ ả G=(∑,∆,P,S). N u ế L(G) không r ng, ta   ữ ả G’=(∑,∆’,P’,S) không có ký hi uệ   L(G’)=L(G)­{ }.ε

ứ Ch ng minh

ε ạ ỏ ộ Đ u tiên ta lo i b  các  ­s n xu t. ta đ c m t văn ph m

ε ấ ế ồ

ượ ấ ạ H không có  ­ε ượ ạ ỏ ệ L(H)=L(G)­{ }. Ti p đ n ta lo i b  các ký hi u vô sinh r i các ư c. Làm v y ta không đ a thêm s n xu t m i nào vào

ả ε ượ ả ấ ầ ấ ả s n xu t mà  ế ệ ký hi u không đ n đ ế văn ph m ạ H, cho đ n văn ph m ả ế ậ ạ G’ thu đ ớ c là không có  ­s n xu t.

ấ ơ ạ ỏ ả Lo i b  các s n xu t đ n

ạ ả ấ ơ ộ S n xu t đ n là m t s n xu t có d ng

ế ấ ệ ộ ả ươ ả

ườ ặ ấ ẫ ng làm kéo dài các suy d n, cho nên cũng có khi ta đ t v n đ  lo i b

ấ ơ ươ ệ

ữ ở ụ ứ

ở  trên, văn ph m  ộ ụ ư ớ ứ ể

ể ỉ ể ạ ỏ ộ ạ ứ ứ ể ộ A B→  trong đó B là m t ký hi u ệ   ấ ơ   ầ ng di n là cú pháp thu n túy, thì s n xu t đ n không k t thúc. Trên ph ề ạ ỏ  th ả   ng di n ng  nghĩa, thì s n xu t đ n có khi cũng có chúng. Tuy nhiên trên ph ạ G2 có ch a các ẳ ạ ích. Ch ng h n trong thí d  đ a ra     M c 1.4  ấ ơ E T→  và T F→ , v i ý nghĩa là: m t bi u th c có th  ch  là m t ộ   ả s n xu t đ n  ỉ ứ ạ   h ng th c, và m t h ng th c có th  ch  là m t nhân th c. Có th  lo i b  các

43

ấ ữ ạ ổ

ệ ữ ể ỏ ả s n xu t đó ra kh i văn ph m mà không làm thay đ i ngôn ng , song các ý nghĩa trên thì không còn bi u hi n n a.

ệ ị Theo tài li u [12], ta có Đ nh lý II.6.

ị Đ nh lý II.6

ậ

ữ ả G=(∑,∆,P,S). Ta có th  thành l p m t ộ   ả ể ấ ơ ộ ươ ạ ạ Cho m t văn ph m phi ng  c nh  ng ươ G’=(∑,∆,P’,S) không có các s n xu t đ n. ng đ văn ph m t

ứ

ượ ị Ch ng minh (cid:0) Thành l p ậ G’ ệ Cho R là quan h  trên ∆ đ c đ nh nghĩa là:

ỉ A→B∈P ARB khi và ch  khi

ờ ặ ấ B y gi ta đ t:

P’={A→α│∃B→α∈P, v i ớ α ∆ và AR*B}

ể ừ ậ ậ ừ ằ L u ý r ng ta có th  tính P’  t văn ph m ạ G. V y l p đ ượ G’  t c văn

ư ph m ạ G đã cho.

ề ừ ự ệ (cid:0) L(G’) L(G) Suy ra đi u đó t s  ki n:

N u ế A→α∈P’ thì A*Gα

ề ằ ạ ị (cid:0) L(G) L(G’) ượ Đi u này đ ứ c xã đ nh ngay sau khi ta ch ng minh b ng quy n p trên i

r ng:ằ

Gx thì A*G’x

N u ế A∈∆ và x∈∑* mà Ai (2­10)

ề ệ ­ M nh đ  này đúng v i ớ i=0.

ứ ế ả ế ằ ẫ  r ng nó v n đúng v i ớ i+1 n u gi thi t r ng nó đã đúng

­ Ta ch ng t ọ ỏ ằ ộ ẫ ớ v i m i suy d n có đ n dài cho t ớ i. i

ẫ ủ

ộ Cho α0G... GαiGαi+1 là m t suy d n c a văn ph m  ộ ộ ộ i+1là m t xâu các ký hi u k t thúc. T n t

ừ ị

* ậ α0

ở

Gαj+1. Tính ch t (ấ 2­10) đ

ạ G có đ  dài  i+1, trong  ồ ạ j, 0 ≤ j ≤ i  ệ ế i  ủ P’, α0→αj+1 là m t s n xu t ấ   ộ ả Gαi+1, b i tính ch t c  b n c a văn ph m phi ng ữ  ạ ấ ơ ả ủ cượ   ừ ế  đó có k t lu n

đó α0 thu c vào ∆ và α sao cho α0,...,αj∈∆ và αj+1 ∆. T  đ nh nghĩa c a  * αj+1 ặ trong P’. M t khác ta có  ả ạ ế ả t quy n p. t c nh và gi  thi ứ i+1. ch ng minh cho

Thí dụ 2.13:

2:

→ │ ở ạ ạ E E+T T Tr  l i văn ph m G

→ │ T T*T F

→ │ F (E) a

44

R={(E,T),(T,F)} Ta có:

R*={(E,E),(T,T),(F,F),(E,T),(T,F),(E,F)}

ạ ươ ươ ấ ơ ả ậ Văn ph m t ng đ ng không có s n xu t đ n thành l p theo cách trên

là:

→ │ │ │ E E+T T*F (E) a

→ │ │ T T*F (E) a

→ │ F (E) a

ị Đ nh lý II.7

ỗ Cho văn ph m phi ng  c nh

ể ậ

ạ ộ ε ả ấ ơ th  thành l p m t văn ph m phi ng  c nh ả vô ích, không có  ­s n xu t và không có s n xu t đ n sao cho ữ ả G=(∑,∆,P,S). N uế  L(G) là không r ng, ta có   ữ ả  G’=(∑,∆’,P’,S’) không có ký hi uệ   ạ L(G’)=L(G)­{ }.ε ấ

ữ ả ạ ấ ượ ọ Văn ph m phi ng  c nh có các tính ch t trên đ ạ   ộ c g i là m t văn ph m

s ch.ạ

ứ Ch ng minh

ε ỉ ầ ạ ỏ ả

ạ ỏ

ụ ấ ơ ả ậ ả ượ ế

ấ ơ ạ ấ ả ớ ủ ả ả ạ ế ạ

ε ế ổ ạ ỏ ạ ỏ ả ả ẫ ấ ấ   ứ ự  sau: lo i b  các  ­s n xu t, Ch  c n áp d ng các bi n đ i theo th  t ệ   ạ ỏ ệ lo i b  các s n xu t đ n, lo i b  các ký hi u vô sinh, lo i b  các ký hi u ấ   ữ c. Qu  v y, lo i b  các s n xu t đ n t o ra nh ng s n xu t không đ n đ ớ ạ   m i, song không t o ra các v  ph i m i c a s n xu t, cho nên văn ph m t o ở ướ  b ra c hai v n không có các  ­s n xu t.

ị Đ nh lý II.8

ộ ộ ữ ế ữ ả G, và xâu x trên b  ch  k t thúc c a ủ G.

ạ Cho m t văn ph m phi ng  c nh  Bài toán x∈L(G) là gi ả ượ i đ c.

ứ

ể ở ổ ề ế ị ả ε∈L(G).

ấ ơ ỉ ả ượ ạ

ả ị

ε ủ ộ ặ ằ ạ │ x . V y ch  c n li

ậ c thành l p nh ẫ ủ ệ ạ │ ố ả ộ ẫ i │

Ch ng minh (cid:0) N u ế x=ε, thì b i B  đ  II.3, ta có th  quy t đ nh ph i chăng  (cid:0) N u ế x≠ε, x là thu c ộ L(G) khi và ch  khi x thu c  ộ L(G’), trong đó G’ là  ư  ấ văn ph m không có  ­s n xu t, không có s n xu t đ n, đ ọ ứ   tron g ch ng minh c a Đ nh lý II.7. Trong văn ph m đó m i suy d n c a xâu x t ph i có đ  dài nh  thua ho c b ng │ ỉ ầ ậ ấ ỏ ế   t kê các suy nh t thi ể ể   ấ ớ x  (s  các suy d n đó là h u h n) đ  ki m ữ ẫ ừ S có đ  dài nhi u nh t t   d n t ả ị đ nh ph i chăng ề x∈L(G).

ạ ẩ D ng chu n Chomsky

ầ

ữ ả ế M t ngôn ng ằ

ạ ớ ả : Tr n Văn C nh, có vi ề ượ ứ  → BC ho c A ữ   ộ ả t “ ạ   ộ c sinh ra b ng m t văn ph m  → a, v i A, B, C là bi n ế   ặ

ệ Theo tài li u [10], tác gi ε ấ ỳ phi ng  c nh b t k  không ch a   đ u đ ậ nào đó mà các lu t sinh có d ng A  ệ ế và a là ký hi u k t thúc. ”.

ừ ị T  đó ta có Đ nh nghĩa II.3.

45

46

ị Đ nh nghĩa II. 3

ộ ạ ở ạ ẩ ế    d ng chu n Chomsky n u

M t văn ph m phi ng  c nh  ả ữ ả G=(∑,∆,P,S) là  ạ ấ ủ ể ỉ các s n xu t c a nó ch  có th  có hai d ng sau:

A BC→ v i ớ A,B,C ∈ ∆,

A a→ v i ớ A∈ ∆ và a∈ ∑.

ề ẩ Các văn ph m phi ng  c nh

ữ ả ε ữ ạ ả

ề ỗ ạ ở ạ  d ng chu n Chomsky  đ u là các văn ữ ả ấ ph m phi ng  c nh không có  ­s n xu t. Cho nên các ngôn ng  do chúng sinh ứ ra đ u không ch a xâu r ng.

ị Đ nh lý II.9

ộ ữ ậ ộ ạ   ữ ả  G. Ta có th  thành l p m t văn ph m

ẩ ở ạ Cho m t ngôn ng  phi ng  c nh  d ng chu n Chomsky sao cho ể L(G’)=L(G)­{ }.ε G’

ứ Ch ng minh

ọ ữ ả ể ạ ậ ộ

ε ả ấ

ố ớ ươ ng đ ậ ε ả ỗ ế ấ ạ   Đ i v i m i văn ph m phi ng  c nh, ta có th  thành l p m t văn ph m ε ấ   ả ng, sai kém xâu r ng  , không có  ­s n xu t và không có s n xu t ạ G  không có  ­s n xu t và t ngay là văn ph m thi

ấ ơ ươ t ể ả ơ đ n. V y ta có th  gi ả không có s n xu t đ n.

Đ t ặ G=(∑,∆,P,S), ta thành l p ậ G’=(∑,∆’,P’,S) theo hai b c:ướ

ộ ả 1) N u còn m t s n xu t

ạ ỏ ả ộ ấ ệ

ứ ạ ỉ

ế ặ ằ ả ấ ấ A Y→ 1Y2...Yk v i ớ k>2,ta lo i b  s n xu t đó và ế   ấ A Y→ 1A’ và A’ Y→ 2Y3...Yk trong đó A’ là m t ký hi u không ả thêm hai s n xu t    ớ ế ả   ặ ạ i quá trình cho đ n khi văn ph m ch  còn ch a các s n k t thúc m i. L p l ộ ế xu t mà v  ph i có đ  dài thua ho c b ng 2.

ượ ệ 2) Trong văn ph m thu đ

ế ạ ả ư ấ ệ ả ổ

ặ ứ ỗ ủ ư ế ệ ệ

ấ

ộ ả ộ ậ ọ ộ ả ượ ấ ạ ế Ca a→ . Văn ph m nh n đ c là đã

ọ ư ậ ế   c nh  v y, ta l u ý m i ký hi u k t thúc có ự ộ ế m t trong các v  ph i có đ  dài 2 c a các s n xu t và th c hi n bi n đ i sau:   ớ   ế a đó, ta đ a thêm m t ký hi u không k t thúc m i C  m i ký hi u k t thúc  ở Ca, đ ng th i đ a ồ ệ ủ ờ ư   Ca, thay m i xu t hi n c a a trong các v  ph i đ  dài 2 b i  ẩ   ở ạ ớ thêm m t s n xu t m i là   d ng chu n Chomsky.

ứ ễ D  dàng ch ng minh L(G’)=L(G)­{ }.ε

47

ƯƠ Ố Ẩ CH NG 3. Ô TÔ MÁT Đ Y XU NG

ố ề ẩ ị 3.1. Ô tô mát đ y xu ng không ti n đ nh

ệ ị Khái ni m và đ nh nghĩa

ị Đ nh nghĩa III.1

ẩ ơ ọ ị ị

ố ộ ộ ộ ẩ ố tô mát đ y xu ng, là m t b  ­7 M=( ề  M t ô tô mát đ y xu ng không ti n đ nh (hay không đ n đ nh), g i là ô , ,  q0, Z0, F)

Trong đó:

(cid:0)

ớ

ạ ầ

ệ ầ

ậ ạ ậ ạ ố ộ ữ  là b  ch  vào; (cid:0) là m t t p h u h n các tr ng thái v i =; ộ ậ ữ ạ ạ (cid:0) q0Q là tr ng thái ban đ u; (cid:0) Z0  là ký hi u đ u trên stack (hay đáy stack); (cid:0) FQ là t p các tr ng thái th a nh n (hay tr ng thái cu i); ừ

(cid:0) ữ ạ ủ ể ậ ậ ị ệ  là hàm d ch chuy n, trong đó ký hi u là t p các t p con h u h n c a X.

ướ ề ắ ườ Quy c v  cách vi t ể ễ ắ ế : Sau đây đ  d  n m b t ta th ng dùng:

ể ể ệ ễ a,b,c… đ  bi u di n các ký hi u vào,

ể ể ễ u, v,w, x, y… đ  bi u di n các xâu vào,

ể ể ệ ễ A, B, C đ  bi u di n các ký hi u trên stack,

ể ể ệ ễ α β , ,… đ  bi u di n các xâu ký hi u trên stack,

ủ ạ ạ ẩ ọ ố ọ  Ta g i tình tr ng c a các ô tô mát đ y xu ng là m i xâu có d ng qw

trong đó*, qQ, w∑*.

0q0x đ

ạ ộ ượ ọ ạ ầ ộ ạ M t hình tr ng có d ng Z c g i là m t hình tr ng đ u.

ủ ầ ẩ ố ị ọ ệ ế ạ i ng m đ nh c a ô tô mát đ y xu ng M là h  vi ệ ế ạ   i t l t l

ắ ồ theo các cách sau:

ớ  Ta g i h  vi WM=(V, P), trong đó: (cid:0) V=Q∑, (cid:0) P g m các quy t c thành l p t ậ ừ *, a∑{} và Z V i p,qQ, α

α α ế ắ ộ N u ( ,p)(Z, q, a)  p là m t quy t c trong P.

ượ ế   c th a nh n theo tr ng thái cu i b i ô tô mát M, n u

* là đ ẫ i m t suy d n trong h  vi

M d

 M t xâu x ộ ộ ầ ố ở ướ ạ ừ ậ ệ ế ạ t l ạ ị i ng m đ nh W ồ ạ t n t i d ng:

WMp trong đó * và p  F

Z0q0x*

48

* là đ

ượ ậ ộ  M t xâu x ế ồ   c th a nh n theo stack r ng b i ô tô mát M, n u t n

ạ ệ ế ạ ộ ầ ị t ẫ i m t suy d n trong h  vi i ng m đ nh W ừ t l ỗ ở ướ ạ i d ng: M d

WMp trong đó p  Q

Z0q0x*

M xu t phát t

ấ ừ ộ ạ ượ ọ ị ộ ẫ ệ  m t hi n tr ng đ c g i là quá trình d ch

ủ M t suy d n W ể chuy n ô tô mát c a M.

ố ọ

ữ ượ ố ở ừ ạ ẩ ậ  Cu i cùng ta g i  (cid:0) Ngôn ng  đ ố   c th a nh n theo tr ng thái cu i b i ô tô mát đ y xu ng

M là ngôn ng :ữ

Mp,  * và p}

L(M)={w∑*| Z0q0w *

ữ ừ ậ ẩ ỗ ở ố (cid:0) Ngôn ng  th a nh n theo stack r ng b i ô tô mát đ y xu ng M là ngôn

ng :ữ

Mp, p}

N(M)={w∑*| Z0q0w *

ườ ừ ậ ạ ợ ng h p th a nh n xâu theo stack r ng thì t p các tr ng thái

Trong tr ậ ừ ế ậ ỗ ườ th a nh n F là không dùng đ n M, v y lúc đó ta th ạ ấ F= ng l y

ấ ơ ả ủ ố ẩ Các tính ch t c  b n c a ô tô mát đ y xu ng

ẽ ọ Cho M=(, ,  q0, Z0, F)là ô to mát đ y xu ng mà ta s  dùng trong m i phát

ấ ượ ề ậ ể ề ẩ ụ bi u v  tính ch t đ ố c đ  c p trong m c này.

ể ắ ắ

ủ ề ầ ạ

ồ ừ ặ ấ ề ấ ả T t c  các tính ch t đ u b t ngu n t ị ố ẩ ủ ệ ế ạ t l ậ ư ậ ượ ắ ộ đ c đi m c a các quy t c trong i ng m đ nh c a ô tô mát đ y xu ng, là đ u có d ng Zpa trong   ậ   c v n

ể ẫ ớ các h  vi đó p,q, Z, a{} và *. Vì v y |Z|=1, |a|1 và |. M t quy t c nh  v y khi đ ợ ụ ng h p: d ng, có th  d n t i các tr

ủ ộ ư ươ ườ (cid:0) N u |a|=1 (nghĩa lá a) thì đ  dài c a ph n t ầ ử xâu vào ch a đ ọ   c đ c

ộ ế ế ẽ ả đ n s  gi m m t;

ế ẽ ả ủ ộ

ư ộ ủ ế ộ

ầ ể ả ộ ướ ư ơ ọ ộ ề ờ (cid:0) N u |=0 (nghĩa là ) thì đ  dài c a stack s  gi m đi m t. ộ Đáng chú ý là đ  dài c a ph n xâu vào ch a đ c đ n cũng nh  đ  dài ị c d ch có th  gi m nhi u h n m t trong m t b

ả c u stack không bao gi chuy n.ể

ị III.1

i  qv, thì: β

Đ nh lý Cho p,q, β*; w, v∑*. N u  pwαế

(cid:0) ộ ậ ố ủ u∑*: w=uv (nghĩa là v là m t h u t c a w) và

(cid:0) pu α I  q.β

ự ệ ộ M t cách tr c quan, thì tính ch t này có nghĩa là các ký hi u ch a đ ư ượ   c

ế ấ ự ọ ế đ c đ n (nghĩa là xâu v) không can d  gì vào tính toán cho đ n lúc đó.

ứ Ch ng minh

49

ị ằ ứ ạ

α β ườ ấ ầ ng ( = , w=v, u=)

i+1qv và gi

ượ ệ Ta ch ng minh đ nh lý b ng quy n p theo i. (cid:0) V i i=0 tính ch t là t m th ớ (cid:0) Gi t r ng nó đã đ thi c nghi m đúng đ n i. Cho  pwα sả ử

ế ằ ắ ượ ướ ậ ả Zraq là quy t c đ c dùng trong b ế ẫ ố c suy d n c i cùng. V y:

pwα i’Zrav’qv, trong đó ’=β

thi ở B i gi

i  ’Zr. β  c a w (w = u’av) và  pu’α   ủ ủ   ấ ề ợ  tính ch t v  h p thành c a c a

ộ ậ ố ủ ặ ừ

ế ộ ậ ố ủ ệ ế ạ ẫ ả Twf ddos v là m t h u t các suy d n trong h  vi ạ t quy n p, av là m t h u t  c a w; m t khác t i ta cũng có: t l

i  ’Zra, β

α pu’a

ế ụ ụ ắ ượ Ti p t c áp d ng chính quy t c Zra q, ta thu đ c:

i  ’Zra  ’q β

α β pu’a

β β Thay u’a=u và  ’ = , ta có

puα i+1  qβ

ư ế ấ ượ ế ệ ớ Nh  th  tính ch t đó cũng đ c nghi m đúng v i i+1, và vì th  nó luôn

đúng.

H  quệ ả III.1

Cho p,q; ,α β* và w,v∑*.

* thì * : w=uv và  puα * q.β

N u  pwαế

ị Đ nh lý III.2

i  qvβ

ể ộ ị Cho m t quá trình d ch chuy n  pwα

α α α ế N u  = ’, trong đó | ’|1 (nghĩa là n u   là m t ti n t

ặ ủ  ch t c a  ố ộ ề ố ạ ế ể ố ị

ể ơ ẫ ớ α ) và ộ trong su t quá trình d ch chuy n, không k  trong hinh tr ng cu i cùng, đ  dài ủ c a stack v n luôn luôn l n h n||, thì:

β ộ ề ố ủ ớ (cid:0) = ’ v i | ’| (nghĩa là  là m t ti n t β β β  c a  ) và

i  qvβ

(cid:0) α ’pw

ộ ự ấ ị

ỉ ể   M t cách tr c quan, tính ch t này có nghĩa là trong quá trình d ch chuy n ẽ

ầ ự ệ ổ ự thì các ký hi u trong stack mà không có l n nào dâng lên đ nh stack thì s không thay đ i gì và không can d  gì vào s  tính toán.

ứ Ch ng min h

ị ứ ạ

α β ườ ấ ầ ng ( pw= qv).

ế ằ ượ ả t r ng nó đã đ thi c nghiên c u đúng đ n i. Cho  pwα

i+1   qv và β   ậ ố c suy d n cu i cùng. V y:

ắ ượ ử ụ ả ử ế ẫ ằ Ta ch ng minh đ nh lý trên b ng quy n p i. (cid:0) V i i=0, tính ch t là t m th ớ (cid:0) Gi  s  Zraq là quy t c đ ứ ướ c s  d ng trong b gi

50

(3­1) pwα iβ1Zravβ1qv, trong đó β1=β

1Z| || nh  v y |β

1|=||

ở ả ế ủ ị ư ậ B i vì gi thi t c a đ nh lý: |β (3­2)

ả ế ở B i gi thi ạ t quy n p, ta có:

là m t ti n t c a β c a β ộ ề ố ủ 1Z, do đó b i (ở 3­2) nó là m t ti n t ộ ề ố ủ 1:

β1= ’β 1, | ’β 1|

i  ’β 1Zra

’pwα (3­3)

ụ ắ ạ ố Áp d ng chính quy t c Zrap lên hình tr ng cu i cùng, ta có:

i ’β 1Zrav  ’β 1qv

(3­4) ’pwΑ

ố Đ i chi u ( ế 3­1), (3­3) và (3­4) ta có:

β ộ ề ố ủ ậ c a β β , nghĩa là  =  ’ =β β1=  ’β 1, v y là m t ti n t

β trong đó  ’=  ’ ở 3­4) tr  thành: β 1. T  đó ( ừ

i+1 ’qvβ

’pwα

ư ế ấ ượ ệ ớ ừ Nh  th  tính ch t đ c nghi m đúng v i i+1, và t đó nó luôn đúng.

ả III.2

* qv.  β

ể ộ ị H  quệ Cho m t quá trình d ch chuy n  pwα

ể ố ị ừ ’ trong đó | ’|1 và su t quá trình d ch chuy n, tr α α  = trong hình

ế N u  ố ủ ạ ẫ ộ ơ ớ α tr ng cu i cùng, đ  dài c a stack v n luôn l n h n | |, thì:

(cid:0) β β βớ =  ’ v i | ’|

* ’pvβ

(cid:0) α ’pw

ị ể ị III.3 (phân rã các quá trình d ch chuy n)

Đ nh lý Cho , α* và w*

*q thì t n t

*, hai s  nguyên k, l và m t tr ng thái r

ồ ạ ộ ạ ố N u  pw αế i hai xâu x,y

sao cho:

w=xy, i = k+l,  px α kr và ry lq.

ứ Ch ng minh

ẩ ề

ị

ấ ể ầ ộ ầ ể ạ

ộ ủ  s  k là đ  dài c a suy d n k  t

ậ ở ị ộ m t trong các b ả ử ộ đ  dài stack ít nh t m t l n đ t giá tr  ||. Gi ẫ ặ g p mà ||=|| và gi ẫ ạ ế đ n hình tr ng  đó. Đ t ả   ộ ố B i đ nh nghĩa các ôt ô mát đ y xu ng, đ  dài stack nhi u nh t là gi m ư ế ướ ị   c d ch chuy n. Nh  th , trong quá trình d ch chuy n đã cho, ấ ạ ị    s  ry là hình tr ng đ u tiên đã  tình tr ng đ u tiên  pwα ầ ạ ả ử   iq có th  vi ể ế t thành: ể ừ ặ l=j­k. V y thì suy d n đã cho

α ư

pwα  k lq (cid:0) N u k=0 thì  pw=, t ừ ỏ ấ đó ta d  d  dàng suy ra: =,  =0, p=r, w=y và nh ườ ầ α ế ượ ậ v y tính ch t trên đ ễ ễ ộ c th a mãn m t cách t m th ng.

51

ế ầ ủ ụ ầ ẫ ị ở Đ nh lý I II.2 áp d ng cho ph n đ u c a suy d n, ta có:

ộ ề ố ủ ư ậ (cid:0) N u k≠0, b i  ­  là m t ti n t c a . Nh ng ||=|, vì v y |=

­ αpw k ry

ị Theo Đ nh lý III.1 y là m t h u t c a w, nghĩa là x: w=xy, và αpxk ry.

i q.

ủ ứ ẫ ầ ộ ậ ố ủ ể ế Ph n th  hai c a suy d n có th  vi t khác đi là: ry

ậ ị ượ ứ V y đ nh lý đã đ c ch ng minh.

ệ ả H  qu  III.3

* 1, α2,…, αn

ộ ố

*, x1, x2,…, xn  các số

ồ Cho m t s  nguyên không âm n và α N u  ế αn  αn­1…  α1pwi  thì t n t

ạ ạ nguyên k1, k2,…, kn và các tr ng thia q i các xâu trong  ∑ 1, q2,…, qn+1 sao cho

w = x1, x2,…, xn,

i = k1, k2,…, kn,

q = q1, q2,…, qn+1

k q+1.

iqixi

ừ ế ớ và v i I t 1 đ n n ta có: α

ứ Ch ng minh

ả ự ế ủ ế ị K t qu  tr c ti p c a Đ nh lý III.3

ữ ẩ ố ừ ậ ng đ ng gi a hai lo i ô tô mát đ y xu ng th a nh n theo stack

ươ ừ ạ ạ ậ ươ T ố ỗ r ng và th a nh n theo tr ng thái cu i

ệ ị Theo tài li u [13], ta có Đ nh lý III.4.

ị Đ nh lý III.4

ồ ạ ẩ ố ộ ộ Cho L=L(M) trong đó M là m t ô tô mát đ y xu ng. T n t i m t ô tô mát

ố ẩ đ y xu ng M’ sao cho L=N(M’).

ứ Ch ng minh

ả ử Gi s  M=(∑, Q, ,, q0, Z0, F).

ạ ớ ư ộ Ô tô mát M’ có thêm hai tr ng thái m i q’ ệ   0và qe, cũng nh  m t ký hi u

0, nghĩa là

đáy stack m i Xớ

M’=(∑, Q  {q’0, qe},’,q’0, X0, )

ủ ệ ặ Ô tô mát M’ ban đ u đ t ký hi u đáy stack Z

0 c a M lên trên ký hi u đáy ủ 0 c a M:

ầ ờ ể ạ ồ ủ stack c a nó X ệ 0, đ ng th i chuy n sang tr ng thái ddaaud q

(3­5) ’(X0, q0, )={(X0Z0q0)}

ạ ộ ủ ự ế ậ Sau đó ô tô mát M’ r p theo s  ho t đ ng c a ô tô mát M cho đ n khi

ộ ạ ố ặ g p m t tr ng thái cu i:

ớ ọ (3­6) V i m i q, a{ } và Z : ’(Z,q,a)=(Z,q,a)

52

ệ

ừ ộ ị nh  là khi M đ c xong m t xâu và d ng l i

L u ý r ng ta dùng ký hi u X ng h p t ừ ọ ạ ớ ư ế ạ

0 làm đáy stack cho M’ (thay vì Z0) đ  để ề  ạ ở ộ    m t ậ   i v i stack r ng. Nh  th  thì khi M’ r p 0 và vì stack không r ng, nó   ừ

ợ ế ậ ẽ ừ ỗ

ư ừ ậ ậ ằ ư ộ ườ phòng m t tr ư ỗ tr ng thái không th a nh n, nh ng l ạ ớ ấ theo quá trình  y nó s  d ng l i v i stack còn có X ẽ s  không th a nh n xâu đó đúng nh  M đã không th a nh n xâu đó.

ộ ạ ặ ọ

e, đ  t

ể ừ ố ạ ướ ể ặ ế ụ ự Khi ô tô mát M g p m t tr ng thái cu i, ô tô mát M’ có hai l a ch n là ắ ầ  đó b t đ u các c M ho c chuy n sang tr ng thái q

ắ ti p t c b t ch ố ạ thao tác d c s ch stack:

α ớ ọ (3­7) V i m i q,  ∑ và Z:

’(Z,q,a)=(Z,q,a)

’(Z,q,)=(Z,q,),qe)}

ọ ớ (3­8) V i m i q:

(X0,q,),qe)}

ở ạ ỡ ế ệ ạ Khi ô tô mát M’ tr ng thái q i trong ọ e, nó d  h t m i ký hi u còn l

stack:

0}:

ớ ọ (3­9)V i m i Z{X

(Z,q,),qe)}

ầ ộ ủ

Các quy t c (3­5), (3­6), (3­7), (3­8) và (3­9) đinh nghĩa m t cách đ y đ ị ắ ể hàm d ch chuy n .

*.

0q0x*

ả ử ế Gi s  x, th  thì Z ớ M  v i q và

ư ệ Ô tô mát M’ làm vi c trên xâu x nh  sau:

0q’0x*

M’X0Z0q0x

ở ắ B i quy t c (3­5): X

ắ ắ ở ướ ạ ộ B i quy t c (3­6), M’ b t ch ủ c ho t đ ng c a M và cho:

M’X0Z0

X0q’0x*

ế ụ ệ ắ ở B i các quy t c (3­7) và (3­8) còn ti p t c làm vi c và cho:

M’qe

X0q*

0q’0x*

M’qe nghĩa là x.

ậ V y thì X

ươ ự ứ ể ế ằ Ng ượ ạ c l ằ i, cũng b ng cách t ng t , ta có th  ch ng minh r ng n u x

thì:

x.

ị Đ nh lý III.5

ồ ạ ẩ ố ộ Cho L=N(M) trong đó M là ô tô mát đ y xu ng. T n t ẩ   i m t ô tô mát đ y

xu ng ố M’ sao cho L=L(M’).

ứ Ch ng minh

53

Gi sả ử M=(∑, Q, ,, q0, Z0, )

ạ ớ ư ộ Ô tô mát M’ có thêm hai tr ng thái m i là ệ   q’0 và qf, cũng nh  m t ký hi u

đáy stack m i ớ X0.

M’=(∑, Q  {q’0, qf},{X0},  q’0, X0, {qf})

ệ ặ ầ ệ

ủ ể ạ ồ Ô tô mát M’ đ u tiên đ t ký hi u đáy stack  ờ stack X0 c a nó, đ ng th i chuy n qua tr ng thái Z0 c a ủ M lên trên ký hi u đáy q0:

(3­10) (X0, q’0,)={(X0, Z0,q0)}

ạ ộ ủ ế ậ Ti p đó ô tô mát M’ r p theo ho t đ ng c a M:

0, q’0,)={(qf)}

ọ ớ (3­11) V i m i qQ: (X

ầ ủ ắ ị Các quy t c (3­10), (3­11) đã đ nh nghĩa đ y đ  .

ứ ệ ượ ệ ươ ự ự ư ở ị Vi c ch ng minh L(M’)=N(M) đ c th c hi n t ng t nh Đ nh lý

III.4

54

ươ ươ ữ ẩ ạ ng đ ố ng gi a ô tô mát đ y xu ng và văn ph m phi ng ữ

3.2. T c nhả

ữ ả ữ ằ ớ ớ   Chúng ta s  ch ng minh r ng l p các ngôn ng  phi ng  c nh là trùng v i

ẽ ứ ữ ượ ừ ậ ẩ ố ớ l p các ngôn ng  đ c các ô tô mát đ y xu ng th a nh n.

ữ ả ừ ố ế ạ ẩ T  văn ph m phi ng  c nh đ n ô tô mát đ y xu ng

ả ữ ệ Theo tài li u [7], tác gi Phan Huy Khánh, có vi

ỉ ế ữ ế ướ ừ ộ ế M t ngôn ng  là phi   t “ ở m t ộ ôtômat đ yẩ   ậ c th a nh n b i

ữ ả ng  c nh n u và ch  n u ngôn ng  đó đ xu ng.ố ”.

ừ ị T  đó ta có Đ nh lý III.6.

ị Đ nh lý III.6

ữ ả ồ ạ ộ ẩ ộ ữ N u ế L là m t ngôn ng  phi ng  c nh, thì t n t ố   i m t ô tô mát đ y xu ng

M mà L=N(M)

ứ Ch ng minh

ả Gi ữ ả  s  G=(∑, ) là căn ph m phi ng  c nh s n sinh L. Ô tô mát M mà

ả ử ỉ ộ ạ ạ L=N(M) ch  có m t tr ng thái q:

M=)

ệ ấ ậ ầ ớ ộ ủ   V y M b t đ u quá trình đoán nh n v i duy nh t m t ký hi u đ u S c a

ậ ạ ở ắ ầ  trong stack. văn ph m

ỉ ộ ệ ỏ

ằ ầ ủ ể ở ỉ ủ ệ ở ắ c (

ự  ể ế ế N u đ nh là m t ký hi u không th  k t thúc A, ô tô mát M mô ph ng s ư   ộ ạ ế ạ ở i b i m t quy t c A c a văn ph m G, b ng cách này thay A b i  nh ng vi t l ượ R) đ  cho ký hi u đ u tiên c a  tr  thành đ nh stack ậ ự ả    đ o ng theo tr t t m i:ớ

R, q) | A}

ớ ọ (3­12) V i m i A: {(

ế ệ ớ ọ ệ   N u đ nh stack là m t ký hi u k t thúc a, thì ô tô mát đ  nó v i ký hi u

ộ ế ằ ỏ ỡ ỉ ế ọ ượ ở đ c đ  xâu vào, và n u b ng nhau thì d  a kh i stack: c

ớ ọ (3­13) V i m i a: = {()}

ủ ở ầ ắ ị ị Các   quy   t c   (3­12)   và   (3­13)   đã   đ nh   nghĩa   đ y   đ hàm   d ch

chuy n .ể

ộ ắ

ộ ẫ ỏ ỗ ạ ẫ ứ

ạ

ắ ờ

ả ử ế ệ ắ ầ

ớ

ằ ề ượ ở

*x đ iố   Các quy t c đó cho phép ô tô mát Mmoo ph ng m t suy d n trái S ộ ư ậ ớ   v i xâu vào x. Trong m t suy d n nh  v y thì m i d ng câu  (t c là m t xâu ớ *, *{} và u là m t ti n t ộ ề ố ủ ẫ    c a xâu trung gian trong suy d n) luôn có d ng  v i u ụ ộ ế ở ẽ ượ c thay th  b i nh  áp d ng m t quy t c A. Bây  s  ’, A s  đ x, nghĩa là . Gi   ắ ứ   ả ứ ệ ờ  các ký hi u k t thúc đ ng đ u xâu ’ ch c ch n ph i là các ký hi u đ ng gi ủ ủ ạ ầ ư ầ   đ u y. L u ý r ng ô tô mát M ghi nh  ph n  c a d ng câu  trong stack c a nó, ướ   ư nh ng theo chi u ng ng c, b i vì stack (trong xâu hình tr ng) luôn luôn h sang ph i, trong khi xâu  ti n theo chi u LIFO l

ề ế ả ạ  bên trái ạ ừ i t

55

ứ 1) Hãy ch ng minh L

Rq M

ạ ằ ứ ướ ế ệ ề Tr

ệ ớ

ệ ệ ế ế ề ả ẫ thi t là m nh đ  đã nghi m đúng cho đ n i và xét suy d n có đ ộ

c h t ta ch ng minh b ng quy n p I trên m nh đ  sau đây: i Gu v i uớ * và *, thì Squ* N u Sế (cid:0) V i i=0, m nh đ  đúng (v i u=,=S). ề ớ (cid:0) Gi dài i+1:

*, *. Trong đó A và u,v* ,

,αβ Si GuAβG uv

ừ ả ế T  gi thi ạ t quy n p ta có:

MβRAq

Squ*

ấ ợ ẫ ở B i tính ch t h p thành các suy d n ta có:

Squv*

ằ Vì r ng A, cho nên (α

MβRAqv RvR,q). MβRαRvRqv*

MβRαRq,

ừ T  đó: Squv*

ề ế ạ Là đi u cho phép k t thúc quy n p.

ề ừ ứ ụ ệ ườ ợ Áp d ng m nh đ  v a ch ng minh vào tr ng h p riêng ta có:

Gx v i xớ *, thì Sqx* *

Mq

N u Sế

ậ V y L(G)N(M).

ờ ứ 2) Bây gi ta ch ng minh

i

ướ ế ứ ệ ề ạ Tr c h t ta ch ng minh quy n p trên i m nh đ  sau:

G u

ế

ệ ề

Rq v i uớ * và * thì S* N u Squ M (cid:0) V i i=0, m nh đ  là đúng (). ớ (cid:0) Gi

ả ệ ệ ọ ị ể   ố ớ t m nh đ  đã nghi m đúng đ i v i m i quá trình d ch chuy n

i

ề ế ế  thi ề ủ c a M có chi u dài cho đ n i.

Rq là m t quá trình d ch chuy n có đ  dài là i+1. M

ả ử ể ộ ộ ị Gi s  Squ

ườ ể ợ Hai tr ng h p có th  là:

Rq, trong đó a

RaqaM Squi M

ườ ể ạ ợ ộ ố ộ ị Tr ng h p m t: D ch chuy n cu i cùng thu c lo i (3­13):

ở ị B i đ nh lý III.1 ta có:

u=u’a và

Raq M

Squ’i

ả ế ấ ờ ả ế Do gi thi ạ t quy n p, b y gi ta có gi thi t trong G:

56

G u=u

S*

RαRq = Rq, trong đó và

RAqM Squi M

ườ ể ạ ợ ố ộ ị ­ Tr ng h p hai: D ch chuy n cu i cùng thu c lo i (3­12):

ả ế ạ Do gi thi t quy n p, ta có trong G:

G.

S*

ử ụ ế ắ ượ S  d ng ti p quy t c ta thu đ c:

G,

S*

ế ề ạ là đi u cho phép k t thúc quy n p.

ề ừ ứ ụ ệ ườ ợ Áp d ng m nh đ  v a ch ng minh vào tr ng h p riêng, ta có:

Mq thì S* *

G x

ế N u Sqx

V y .ậ

ữ ả ừ ố ẩ ạ ế T  ô tô mát đ y xu ng đ n văn ph m phi ng  c nh

ệ ị Theo tài li u [11], ta có Đ nh lý III.7.

ị Đ nh lý III.7

ế ẩ ớ ộ ố ộ   Cho m t L=N(M) v i M là m t ô tô mát đ y xu ng, th  thì L là m t

ữ ả ữ ộ ngôn ng  phi ng  c nh.

ứ Ch ng minh

ừ ậ ẩ ỗ ố Gi s ả ử 0,0,) là ô tô mát đ y xu ng th a nh n L theo stack r ng.

ữ ả ủ ẫ ạ Ta l p m t văn ph m phi ng  c nh  sao cho các suy d n trái c a nó mô

ủ ỏ ộ ậ ự ạ ộ ph ng s  ho t đ ng c a M.

ặ Đ t  và p,q} và  trong đó .

ắ ậ ượ ư T p các quy t c P đ ậ c thành l p nh  sau:

0, q0, q] là m t quy t c,

ọ ắ ộ ớ (3­14) V i m i , [Z

k…X2X1,p) trong đó k và X1,X2,…,Xk thì v i m i s

ớ (3­15) N u (Xế ọ 1, s2,…,sk

ắ ộ [Z,q,sk][X1,p,s1] [X2,s1,s2]…[ Xk, sk­1,sk] là m t quy t c.

ế (3­16) N u () thì [ ắ ộ Z,q,a] là m t quy t c

ượ ằ ậ ớ ấ ạ Văn ph m G đ ư c thành l p nh  trên là nh m t i tính ch t sau:

ỗ ẫ ộ ỏ ị

M i suy d n trái sinh ra m t xâu∑ ể ộ ậ ủ ừ ẫ

ủ ạ ả ố

* trong G mô ph ng m t quá trình d ch   ỗ ạ chuy n c a ô tô mát M th a nh n xâu x. M i d ng câu trong suy d n đó có   *, *; d ng câu đó ph n ánh m t tình hu ng c a ô tô mát M:  ộ ạ u  d ng , trong đó ∑ ọ ủ là ph n đã đ c c a xâu x và xâu

R là n i dung stack.

ầ ộ

ằ ướ ứ ế ạ ằ ứ I Đ  ch ng minh r ng , tr c h t ta ch ng minh b ng quy n p trên

ệ ể ề m nh đ  sau đây:

57

G w∑* thì Zqw* i

M r

ế (a) N u [Z,q,r]

ề ắ ớ ộ ừ ở  đó b i các

ớ ầ ậ ậ V i i=0 m nh đ  đúng, vì [ ệ thành ph n l p (3­16), (), v y Zqw Z,q,r]w là m t quy t c (v i w), t * M r

ả ử ệ ệ ề ế ẫ ộ ọ

ớ  s  m nh đ  đã nghi m đúng v i m i suy d n có đ  dài cho đ n I, ẫ Gi ứ ớ ộ ộ ta ch ng minh nó cũng đúng v i m t suy d n có đ  dài i+1, trong đó i.

ộ ố ắ ẫ ộ ớ   D a vào đ nh nghĩa c a các quy t c, thì m t s  suy d n có đ  dài i+1 v i

ự ể ượ ế ư ị c vi ủ t thành nh  sau: (i) có th  đ

Gw

[Z,q,r]Ga[X1,s0,s1] [X2,s1,s2]…[ Xk, sk­1,sk]i

Trong đó a∑, k, sk=r và (Xk…X2X1,s0)

ấ ữ ả ẫ ị

ồ ạ   i 1,…,nk và các xâu w1,…,wk sao cho w=aw1…wn,  i=n1+…+nk  và

ớ Theo tính ch t phân rã các suy d n phi ng  c nh (Đ nh lý III.1) t n t ố các s  nguyên n ừ ớ v i j t i k:   1 t

j Gwj.

[xj,sj­1,sj]n

ả ế ẫ ạ thi t quy n p cho các suy d n cho các suy Vì nj,  ta có th  v n d ng gi

ộ ẫ d n có đ  dài n ụ ể ậ ế ở j và b i th :

* jsj­1wj

Msj

ừ ớ ớ (b) V i j t 1 t i k: X

k…X2X1,s0) ta có:

ạ L i vì có (X

(c) Zqaw1…wkMXk…X2X1s0w1w2…wk

ấ ợ ẫ ờ T  h p (b) và (c), nh  cào tính ch t h p thành các suy d n trong h  vi ệ ế   t

* Mr

ạ ượ ổ ợ i, ta thu đ l c Zqw

ọ ố ậ ấ ớ V y tính ch t (a) là đúng v i m i s  nguyên i.

ở ị ồ ạ ắ ộ ạ i m t tr ng thái q

Cho w. B i đ nh nghĩa c a các quy t c trong G, t n t ộ ố và m t s  nguyên i sao cho: S

Mq

ở ấ B i tính ch t (a) ta có: Z ủ G[Z0, q0, q]iw 0q0w*

ậ V y w.

ể ự ượ ể ậ N(M): Ch ng minh xin đ

ứ ầ ử ụ ể ằ ị ệ ứ   c chuy n thành bài t p. Đ  th c hi n ch ng ấ minh r ng, ta c n s  d ng tính ch t phân rã các quá trình d ch chuy n.

58

ụ Thí d  3.2:

ư ể ị Cho M=({a,b},{q0, q1},{a,Z},,q0,Z,). Hàm d ch chuy n  cho nh  sau:

(Z,q0,a)={(Za,q0)} (a,q1,b)={(,q1)}

(a,q0,a)={(aa,q0)} (a,q1,)={(,q1)}

(a,q0,b)={(,q1)} (Z,q1,)={(,q1)}

ibj| }

ễ ấ ằ D  th y r ng N(M)={a

ạ ậ ươ ươ ớ ươ Ta thành l p văn ph m t ng đ ng v i ô tô mát theo ph ư   ng pháp đ a

ị ra trong đ nh lý III.7.

ỉ ầ ậ ế ượ ừ ệ ắ Ta ch  c n l p các quy t c cho các ký hi u là đ n đ c t S.

S[Z,q0,q0] | [Z,q0,q1]

0),q0,a) ta thu đ

ừ T  (Za, q c:ượ

[Z,q0,q0]a[a, q0, q0] [Z,q0,q0] | a[a, q0, q1] [Z,q1,q0]

[Z,q0,q1]a[a, q0, q0] [Z,q0,q1] | a[a, q0, q1] [Z,q1,q1]

0),q0,a) ta thu đ

ừ T  (aa,q c:ượ

[a,q0,q0]a[a, q0, q0] [a,q0,q0] | a[a, q0, q1] [a,q1,q0]

[a,q0,q1]a[a, q0, q0] [a,q0,q1] | a[a, q0, q1] [a,q1,q1]

ậ ượ Ta còn nh n đ c:

[a,q0,q1]b Vì (,q1)(a,q0,b)

[a,q1,q1]b| Vì (,q1)(a,q1,b)(a,q1,)

[Z,q1,q1] Vì (,q1)(Z,q1,)

ạ ỏ ệ ế ượ ạ N u lo i b  các ký hi u vô sinh ta đ c văn ph m:

S[Z,q0,q1]

[Z,q0,q1] a[a, q0, q1] [Z,q1,q1]

[a,q0,q1] a[a, q0, q1] [a,q1,q1]

[a,q0,q1] b

[a,q1,q1] b|

[Z,q1,q1]

59

ƯƠ CH NG 4. T NGỔ  QUAN VỀ TRÌNH BIÊN D CHỊ

ậ 4.1. Ngôn ngữ l p trình

Mở đ uầ

Từ  ngàn  xưa  con  người  muốn  giao  tiếp  với  nhau  phải  dùng  ngôn  ngữ.  Vậy  người  giao  tiếp  với  máy  tính  tất  nhiên  cũng  thông  qua  ngôn  ngữ.  Con  người muốn  máy  tính  thực  hiện  công  việc,  phải  viết  các  yêu  cầu  đưa  cho  máy bằng ngôn ngữ  máy hiểu được. Việc viết các yêu cầu, ta gọi là lập trình  (programming). Ngôn ngữ  dùng để lập trình được gọi là ngôn ngữ lập trình  (programming language).

Viết chương trình để giải quyết vấn đề sẽ dễ dàng và tự nhiên hơn nếu  ngôn  ngữ  lập  trình  gần  với  vấn  đề  cần  giải  quyết.  Có  nghĩa  là  ngôn  ngữ  phải chứa đựng  các  cấu  trúc  thuật  ngữ,  phần  tử  dùng  để  miêu  tả  vấn  đề  và không phụ thuộc vào  máy tính cụ thể.

Các ngôn ngữ lập trình có tính chất như trên được gọi là ngôn ngữ cấp  cao.  Nhưng  máy  tính  chỉ  hiểu,  chỉ  chấp  nhận  ngôn  ngữ  cấp  thấp  riêng  của  mình, đó là chuỗi các số 0 và 1, chuỗi số đó lại không gần gũi chút nào đối  với con người.

Việc phân cấp ngôn ngữ lập  trình được dựa  trên cơ  sở của tính  không

phụ thuộc với máy tính ngày càng cao của các ngôn ngữ.

Phân lo iạ

 Ngôn ngữ máy (machine language),

 H pợ  ngữ (assembly language),

 Ngôn ngữ c pấ  cao (higher­level language).

Bởi vì máy tính chỉ có thể hiểu ngôn ngữ máy cho nên một chương trình  viết  trong  ngôn  ngữ  cấp  cao  cuối  cùng  rồi  cũng  được  dịch  sang  ngôn  ngữ  máy.  Công  cụ  thực  hiện  việc  dịch  đó  được  gọi  là  chương  trình  dịch  (translator).

Chương  trình dịch  được chia làm  hai  loại:  trình biên dịch  (compiler)  và

trình  thông dịch (interpreter).

 Trình biên dịch: chuyển một chương trình viết trong ngôn ng  ữ cấp cao  chương  trình  nguồn  sang  chương  trình  trong  ngôn  ngữ  cấp  cao  khác  hoặc  ngôn ngữ máy (cid:0) ngươ  trình đích. (cid:0) ch

Thời  gian  chuyển  một  chương  trình  nguồn  sang  chương  trình  đích

được  gọi là thời gian dịch (compile time).

Thời  gian  mà  chương  trình  đích  được  thực  thi  được  gọi  là  thời  gian

thực  thi (run time).

60

61

ơ ồ ị Hình 4. S  đ  trình biên d ch

Như  vậy,  đối  với  trình  biên  dịch,  chương  trình  nguồn  và  dữ  liệu  được

xử lý  trong thời gian khác nhau, đó là thời gian dịch và thời gian thực thi.

 Trình  thông  dịch:  quá  trình  xử  lý  dạng  bên  trong  của  chương  trình

nguồn và d  ữ liệu cùng một thời gian.

ơ ồ ị Hình 4. S  đ  trình thông d ch

Một  số  trình  thông  dịch  làm  việc  như  sau:  phân  tích  từng  phát  biểu  và

thực  thi luôn.

Hiện  nay  trình  thông  dịch  đa  phần  áp  dụng  kỹ  thuật  của  trình  biên  dịch  là  biên dịch chương trình nguồn sang dạng mã  trung gian. Từ mã trung  gian sẽ được thực thi bằng trình thông dịch.

Cú pháp và ng  ữ nghĩa

Để  tiện  lợi  hơn  trong  đặc  tả  và  hiện  thực  sự  biên  dịch,  ta  coi  sự  biên

dịch bao  gồm hai phép chiếu đơn giản hơn.

Th  ứ nhất là phép ánh xạ cú pháp (syntactic mapping), nó ánh xạ một  chương  trình viết trong ngôn ngữ nguồn sang cấu trúc là đối số của phép  ánh xạ tiếp theo,  đó  là  phép  ánh  xạ  ngữ  nghĩa  (semantic  mapping).  Cấu  trúc  của  phép  ánh  xạ  cú  pháp  là  cây  cú  pháp  (syntactic  tree).  Sau  đây  là  thí  dụ  cây  cú  pháp  được  xây  dựng  như  thế  nào  trên  chuỗi  nhập  vào  là  một câu tiếng Anh. Mỗi câu tiếng Anh được bẻ  ra thành những ký hiệu  cú pháp nhờ vào các luật văn phạm.

62

(cid:0) c có cây cú pháp A sau: Thí dụ 4.1:  Chuỗi ký tự a + b (cid:0)

Hình 4. Cây cú pháp A

Qua thí dụ trên ta thấy rằng với mỗi câu của ngôn ngữ đêu tồn tại cây cú  ph á p   của  nó.  Quá  trình  tìm  ra  cây  cú  pháp  của  một  câu,  được  gọi  là  quá  trình phân  tích cú pháp câu đó (syntactic analysis parsing). Quá trình phân tích  cú pháp được thực  hiện  dựa  trên  cơ  sở  các  luật  cú  pháp  của  ngôn  ngữ  (đó  chính là các quy tắc  hay luật sinh). Cú pháp của ngôn ngữ là tập luật sinh, nó  cung  cấp  cho  ta  mối  quan  hệ  giữa  mỗi  câu  của  ngôn  ngữ  với  cấu  trúc  cú  pháp.

4.2. Trình biên d chị

ị Đ nh nghĩa

ả ị ế Trình  biên  d chị ệ Theo tài li u [6], tác gi : Nguy n Gia Đ nh, có vi

ễ ngươ   trình  đ ngươ   trình  dùng  để  đ cọ   m tộ   ch t “ cượ   vi

ữ là  tế   trong  m tộ   ngôn  cượ   g iọ   là  ngôn  ngữ  ngu nồ   (source  language)  và  d chị    ngôn ngữ ngươ   ngứ  trong ngôn ng  khác, ngươ  trình đó sang ch ngươ  trình t

ch ngữ  l pậ   trình  đ ch đích …”

ừ ị T  đó ta có Đ nh nghĩa IV.1.

ị Đ nh nghĩa IV.1

Trình  biên  dịch  là  chương  trình  dùng  để  đọc  một  chương  trình  được  viết  trong  một  ngôn  ngữ  lập  trình  được  gọi  là  ngôn  ngữ  nguồn  (source  language)  và  dịch  chương  trình  đó  sang  chương  trình  tương  ứng  trong  ngôn

63

ng  ữ khác, ngôn ngữ  đích (target language).

Như  vậy  ta  sẽ  có  rất  nhiều  trình  biên  dịch,  vì  ta  có  hàng  ngàn  các  ngôn  ngữ  nguồn  từ  những  ngôn  ngữ  lập  trình  họ  cổ  điển  (Fortran,  Pascal) đến các ngôn ngữ  đặc biệt đã xuất hiện rất nhiều trong lĩnh vực  ứng dụng máy tính.

Các phần của trình biên d chị

Chương trình nguồn trong ngôn ngữ lập trình không gì khác là chuỗi các  ký  tự. Trình biên dịch có nhiệm vụ chuyển chuỗi ký t  ự này sang chuỗi ký tự  khác ­ đó  là mã đối tượng. Quá  trình này bao gồm các quá trình nh  ỏ hơn và  được đặt tên như sau:

 Phân tích từ vựng.

 Bảng danh biểu và thông báo lỗi.

 Phân tích cú pháp.

 Phân tích ngữ nghĩa.

 Sinh mã trung gian.

 Tối ưu mã trung gian.

 Sinh mã đối tượng.

Đối  với  một  trình  biên  dịch  tồn  tại  trong  thực  tế,  thứ  tự  các  quá  trình  nhỏ  có  thể  hơi  khác  so  với  thứ  tự  ở  trên.  Có  thể  một  số  quá  trình  nhỏ  kết  hợp lại với nhau  thành  một  quá  trình  duy  nhất.  Trình  biên  dịch  phải  có  khả   ệ cú pháp  năng  nhận  biết  chuỗi  nhập vào có phải là một chương trình hợp l không. Nếu không, trình biên dịch phải thông báo lỗi.

Phân tích từ v ngự  (lexical analysis)

Giai  đoạn  phân  tích  từ  vựng  là  giai  đoạn  đầu  của  quá  trình  biên  dịch.  Dòng nhập vào trình biên dịch là chuỗi các ký tự cho phép của một ngôn ngữ  lập trình, cũng là chuỗi nhập vào bộ phân tích từ vựng.

(cid:0) ( ), & >=… (cid:0) + = := / (cid:0)

Chẳng hạn, đối với ngôn ngữ Pascal, các ký tự alphabet là các ký tự sau:  A…Z, a…z, $ @ 0 1 2…9 dấu trống (cid:0) Trong chương trình nguồn, sự kết hợp một số ký tự alphabet sẽ tạo nên  một  thực thể của ngôn ngữ. Chẳng hạn, BEGIN là sự kết hợp 5 ký tự B, E,  G, I, N tạo  nên thực thể là từ khoá BEGIN.

Các thực th :ể

 Ký hiệu trống, dấu tab, dấu xuống hàng,

 Từ khoá: begin, end, goto, while, do, integer…,

 Chuỗi các ký tự số tượng trưng cho hằng số,

64

 Danh biểu, dùng để đặt tên cho các biến, hàm thủ tục, nhãn,  Các ký  hiệu  đặc  biệt:  +,  (cid:0) , /, (cid:0) ,  :=, ;, =, >,  >=,  <,  <=, được gọi là  các

token.

Nhiệm vụ của bộ phân tích từ vựng là khi tiếp nhận chuỗi ký tự nhập  phải  biết nhóm các ký tự thành các thực thể cú pháp token. Token là ký hiệu  kết thúc,  mỗi token sẽ có một cấu trúc từ vựng. Cấu trúc từ vựng này là một  cặp (loại token,  dữ liệu), gồm hai thành phần:

Thành phần thứ nhất là phạm trù cú pháp: hằng, biến.

Thành  phần  thứ  hai  là  con  trỏ,  chỉ  đến  thông  tin  của  token,  được  cất

giữ trong bảng, được gọi là bảng danh biểu (symbol table).

Với ngôn ngữ lập trình cho trước, số lượng loại token là hữu hạn. Tóm  lại  bộ  phân  tích  từ  vựng  là  bộ  dịch  (translator)  mà  đầu  nhập  của  nó  là  chuỗi  các  ký  tự,  tượng  trưng  cho  chương  trình  nguồn,  đầu  ra  là  các  token.  Dạng đầu ra này là đầu  nhập của bộ phân tích cú pháp.

Thí dụ 4.2:

Chương trình nguồn là phát biểu gán trong ngôn ngữ Pascal:

COST:=(PRICE+TAX)(cid:0) 65

Bộ  phân  tích  từ  vựng  có  nhiệm  vụ  nhận  biết:  COST,  PRICE,  TAX  là  nhóm token  thuộc loại danh biểu, 65 là token thuộc loại hằng. Các ký tự :=, (,  ), +, (cid:0)

(cid:0) tự bản thân  là token.  ả s  ử tất cả các hằng, danh biểu là các token có loại  và .  Gi Thành  phần thứ hai là dữ liệu, ở đây chính là con trỏ chỉ đến vị trí của các  token đó trong  bảng danh biểu, chứa đựng trị từ vựng (lexeme) của token và  các thuộc tính khác  của token. Thành phần thứ nhất của token sẽ được dùng  trong  giai  đoạn phân  tích  cú pháp. Thành phần thứ hai của token được dùng  trong giai đoạn xử lý ngữ nghĩa và sinh mã đối tượng.

Bảng danh biểu và thông báo l iỗ

Các  token  được  bộ  phân  tích  từ  vựng  nhận  biết  và  các  thông  tin  của  từng  token sẽ được lưu chứa trong bảng danh biểu. Xét phát biểu trong Thí  dụ 4.2. Sau hi  phát  biểu  được  đi  qua  bộ  phân  tích  từ vựng, bảng danh biểu  sẽ chứa các thông tin  sau:

65

ả ể ả B ng IV.1 B ng danh bi u 1

Ch  sỉ ố Token Các thông tin khác Lexeme

ế 1 id COST ự Bi n th c

ế 2 id PRICE ự Bi n th c

ế 3 id TAX ự Bi n th c

ằ 4 num 65 H ng s ố nguyên

Nếu  bộ  phân  tích từ  vựng  nhận  tiếp các  chuỗi  ký  tự của  chương  trình  nhập,  để  nhận  dạng  token,  thì  bảng  danh  biểu  cũng  thường  xuyên  được  truy  xuất.  Hành  vi  truy  xuất  nhằm  hai  mục  đích:  nếu  danh  biểu  vừa  được  nhận  dạng  đã  được  lưu  chứa  trong  bảng  danh  biểu  thì  phần  thứ  hai  của  token là dữ liệu sẽ được cập nhật  bằng chỉ số của danh biểu đó trong bảng  danh biểu.

Thí dụ 4.3:

COST  có  chỉ  số  là  1  trong  bảng  danh  biểu,  COST  lại  xuất  hiện  trong

chuỗi nhập sau:

y:=COST(cid:0) 2.0 Chuỗi xuất ra của bộ phân tích từ vựng là:

(cid:0) id :=id (cid:0) num (id, 5):=(id, 1)(cid:0) (num, 6) 5 1 6

Trong  trường  hợp  này  COST  không  cất  vào  bảng  danh  biểu  nữa,  nhưng bộ phân  tích từ vựng sẽ đẩy ra token (id, 1), 1 là vị trí COST đã được  cất trong bảng danh biểu trước đó.

Bảng  danh  biểu  thường  xuyên  được  truy  xuất  để  thêm  hoặc  truy  xuất

các  token, do đó phải thoả mãn hai điều kiện:

(cid:0) Thực hiện nhanh các thao tác thêm token, hoặc các thông tin của token. (cid:0) Có khả năng truy xuất nhanh các thông tin của một token.

ệ Phát hi n và thông báo l iỗ

Ở mỗi giai đoạn của quá trình biên dịch một chương trình nguồn đều có  thể  có  lỗi.  Như  vậy  sau  khi  phát  hiện  một  lỗi,  trình  biên  dịch  xem  xét  lỗi  đó  xem  có tiếp  tục  quá  trình  dịch  hay  không.  Tất  nhiên,  nếu  một  trình  biên  dịch mà ngay  khi  phát hiện lỗi đầu tiên đã dừng chương trình thì không hữu  hiệu.

Trong  giai  đoạn  phân  tích  từ  vựng  và  cú  pháp  thường  xuất  hiện  nhiều  lỗi  do  trình  biên  dịch  phát  hiện.  Trong  lúc  phân  tích  từ  vựng,  lỗi  được  phát

66

hiện khi phần  còn lại trên băng nhập không thể tạo nên token. Lỗi xảy ra khi  bộ phân tích cú pháp  không  thể  xây  dựng  cấu  trúc  cú  pháp  cho  chuỗi  token  cho  trước.  Lỗi  cũng  có  thể  được  phát  hiện  trong  quá  trình  phân  tích  ngữ  nghĩa,  khi  trình  biên  dịch  kiểm  tra  kiểu  dữ  liệu  của  hai  toán  hạng  thuộc  một  phép  toán  không  phù  hợp.  Chẳng  hạn,  một toán hạng thuộc kiểu dãy,  cộng với một toán hạng là tên của chương trình con.

Phân tích cú pháp (Syntactic analysis parsing)

Chuỗi xuất ra từ bộ phân tích từ vựng là các token có dạng (loại token,  dữ liệu),  sẽ  là  chuỗi  nhập  vào  bộ  phân  tích  cú  pháp.  Bộ  phân  tích  cú  pháp  chỉ  xét thành phần thứ nhất của token là loại token.

Sự phân tích cú pháp là một quá trình, trong quá trình này chuỗi các token  sẽ  được  kiểm  tra  xem  có  thể  được  biểu  diễn  bằng  cấu  trúc  cú  pháp  của  ngôn  ngữ  lập  trình cho trước hay  không, Nếu  tồn  tại một cấu trúc cú  pháp  cho chuỗi nhập thì cấu  trúc  được  sinh  ra  đó  chính  là  kết  quả  của  quá  trình  phân tích cú pháp. Ở giai đoạn  sinh mã, cấu trúc cú pháp sẽ được xem xét để  từ đó sinh ra mã cho chuỗi ký tự của chương trình nguồn.

Phân tích ngữ nghĩa

Sau  giai  đoạn  phân  tích  cú  pháp,  cấu  trúc  cú  pháp  của  chuỗi  nhập  sẽ  được bộ  phân  tích  ngữ  nghĩa  xử  lý.  Bộ  phân  tích  ngữ  nghĩa  sẽ  kiểm  tra lỗi  về  ngữ  nghĩa..  Một  nhiệm  vụ  quan  trọng  mà  bộ  phân  tích  ngữ  nghĩa  thực  hiện là kiểm tra loại dữ  liệu.  Dựa  trên  cây  cú  pháp,  bộ  phân  tích  ngữ  nghĩa  sẽ  xử  lý  từng  phép  toán.  Với  mỗi  phép  toán,  nó  sẽ  xét  các  toán  hạng  xem  loại dữ liệu của chúng có cho phép để  tham  gia  vào  phép  tính  đó  không  (nói  cách  khác  loại  dữ  liệu  của  các  toán  hạng  trong phép toán cụ thể, có được  ngôn ngữ lập trình định nghĩa không).

Thí dụ 4.4:

a  + 1  với  a là  biến  thuộc  loại  dữ liệu số  thực,  1  là  thuộc loại luận lý.  Vậy  phép  cộng  không  thể thực  hiện  với  hai toán hạng  loại  số  thực và  loại  luận lý.

Hoặc: a + n với a là số thực và n là số nguyên

Khi  kiểm  tra  thấy  hai  toán  hạng  của  phép  cộng  một  có  trị  thực,  một  có  trị  nguyên  thì  hầu  hết  các  trình  biên  dịch  sẽ  chuyển  trị  của  toán  hạng  n  sang biểu thức  số  thực, cụ  thể  nếu  n  có trị là  10 thì  trị  10  sẽ  được  chuyển  sang trị thuộc loại thực 10.0 để cộng với trị của a.

67

Hình 4. Cây cú pháp B

Trị  65  sẽ  được  chuyển  sang  số  thực.  Cây  cú  pháp khi xử lý ngữ nghĩa

sẽ có dạng như trên.

Sinh mã trung gian

Sau giai đoạn phân tích cú pháp và ngữ nghĩa, một số trình biên dịch đã  tạo ra  sự  biểu  diễn  trung  gian  của  chương  trình  nguồn.  Sự  biểu  diễn  trung  gian  của  chương  trình  nguồn  được  hiểu  như  là  chương  trình  của  máy  tính  trừu  tượng  (abstract machine).

Ngôn ngữ được dùng cho máy trừu tượng là mã trung gian. Mã trung gian  có  hai  đặc  điểm  quan  trọng:  dễ  được  sinh  ra  và  dễ  chuyển  sang  mã  đối  tượng  của  chương trình đích. Với Thí dụ 4.4, kết quả của giai đoạn sinh mã  trung gian có dạng:

ị ố ằ temp p := intoreal (tr  s  b ng 65) 1

temp p := id + id (4­1) 2 2 3

(cid:0) temp p := temp p (cid:0) temp p 3 1 2

id := temp p 1 3

Tối ưu mã trung gian

Giai đoạn này sẽ thu giảm một số bước trong mã trung gian nhằm làm  cho  khi sinh ra mã đối tượng thì thời gian thực thi mã đối tượng sẽ ngắn hơn.

Bước  sinh  mã  sẽ  dùng  cây  cú  pháp  đã  được  xử  lý  ngữ  nghĩa  (đã  qua

bước phân tích ngữ nghĩa) để sinh mã trung gian.

Cách làm thông thường như sau:cứ ứng với nút là toán tử sẽ sinh ra mã  trung  gian như ở (4­1). Tuy vậy, có cách tốt hơn là với (4­1) chỉ cần hai mã

68

trung gian mà  thôi.

temp p := id + id (4­2) 1 3 2

id := temp p + 65.0 1 1

Việc  thu  giảm  nh  ư trên  sẽ  được  thực  hiện

ở bước  tối  ưu  mã.  Bước  chuyển số  nguyên sang số thực sẽ được thực hiện ngay trong thời gian dịch,  do  đó  phép  toán  intoreal  sẽ  được  bỏ  đi.  Xem  lại  (4­1),  ta  thấy  ở  mã  thứ  tư  , do đó có  id chỉ dùng có một lần là gán trị vào id , với temp p := temp p 1 3 1

3  thể ghép mã thứ 3 và thứ 4 thành mã thứ 2 của (4­2).

Còn rất nhiều trường hợp khác mà trình biên dịch thực hiện tối ưu mã. Ở  đây  một  vấn  đề  nảy  sinh  là  thực  hiện  tối  ưu  mã  trong  thời  gian  biên  dịch  sẽ  làm  thời  gian dịch tăng lên trong giai đoạn này. Tuy nhiên một số trường  hợp tối ưu mã cho  phép  nếu  thời  gian  thực  thi  của  chương  trình  đích  được  rút ngắn mà không làm sự  biên dịch quá lâu.

Sinh mã đối tượng

Giai đoạn cuối của trình biên dịch là sinh mã đối tượng. Mã đối tượng có

thể  là mã máy định vị lại địa chỉ hoặc mã hợp ngữ.

Thí dụ 4.5:

Ta sử dụng hai thanh ghi 1 và 2, để dịch mã trung gian (4­2) sang mã

hợp ngữ:

movF id , R movF id 2 1 , R 2 3

addF R (4­3) , R 1 2

mulF # 65.0, R 1

, id movF R 1 1

Lưu ý rằng movF, addF, mulF là phép tính với số thực. Ch  ỉ thị đầu thực  vào thanh ghi hiện  chuyển trị từ vị trí nhớ có tên PRICE, thuộc loại token id 2

. Ch  ỉ thị  thứ hai  thực  hiện  chuyển  trị  ở  vị  trí nhớ có  tên  TAX  thuộc loại R 1

token id . Chỉ th  ị th  ứ ba thực hiện phép cộng nội dung hai vào thanh  ghi R 2 3

thanh ghi R . Chỉ thị thứ t ư thực và R 2 , kết quả  phép toán được cất trong R 1 1

. Ch  ỉ thị hiện phép nhân hằng có tr  ị s  ố thực 65.0 với trị nằm trong thanh ghi R 1

cuối  cùng  chuyển  nội  dung trong  thanh  ghi  R vào  vị  trí  nhớ  có  tên  COST 1

69

thuộc loại token id . 1

Ứ ụ ủ ữ ớ ị 4.3. ứ ng d ng c a ngôn ng  hình th c và ôtômat v i trình biên d ch

Các  phần  trước  của  chương  này  ta  có  nói  chuỗi  ký  tự  nhập  vào  trình  biên  dịch  là  văn  bản  của  chương  trình  nguồn.  Đúng  vậy,  song  văn  bản  đó  lại  có  thể  là  sản phẩm đầu ra của một hoặc nhiều bộ tiền xử lý  (preprocessor)  và  sản  phẩm  đầu  ra  của  trình  biên  dịch  có  thể  lại  tiếp  tục  được xử lý trước khi trở thành mã máy của  máy tính thật. Trong phần này  ta sẽ nói tới các mối liên quan đó.

Bộ tiền xử lý

ị Bộ  ti nề   xử  lý  sẽ  t oạ   ra  chu iỗ   nh pậ   vào  trình  biên  d ch. Bộ  ti nề   xử  lý

th cự   hi nệ  các ch cứ  năng sau:

Xử  lý  macro  (macro  processing).  Bộ  tiền  xử  lý có  thể  cho  phép  người  sử  dụng  định  nghĩa  các  macro.  Macro  được  hiểu  là  cách  viết  ngắn  gọn  cho  cấu trúc dài hơn.

Chêm t pậ  tin (file inclusion). Bộ tiền xử lý có thể “nhét” các tập tin vào  chương  trình  văn  bản.  Chẳng  hạn,  tiền  xử  lý  ngôn  ngữ  C  sẽ  “nhét”  nội  dung  của  tập  tin  vào thay thế cho phát biểu # include   khi nó xử lý một tập tin có chứa phát biểu trên.

Bộ  xử  lý  hoà  h pợ   (Rational  processor).  Bộ  tiền  xử  lý  loại  này  sẽ  tạo  nên sự hoà  hợp giữa ngôn ngữ cổ điển với những cấu trúc điều khiển, cấu  trúc d  ữ liệu  hiện  đại  hơn..  Chẳng  hạn,  bộ  tiền  xử  lý  giúp  cho  người  sư  dụng  có  thể  dùng  các  phát  biểu  có  cấu  trúc  như  while,  if  trong  ngôn  ngữ  lập  trình,  mà  tự  bản  thân  ngôn  ngữ  đó  không có các phát biểu trên. Thực tế  các   phát  biểu  while,  if   chính  là  các   macro,  khi  người  sử  dụng  viết  một  chương  trình  trong  ngôn  ngữ  cổ  điển  có  dùng  tới  hai  loại  phát biểu có cấu  trúc trên và cần biên dịch ra ngôn ngữ máy thì bộ tiền xử lý sẽ làm việc trước.  Tất cả nơi nào có hai phát biểu while, if sẽ được thay thế bởi chuỗi các  phát  biểu mà ngôn ngữ lập trình cổ điển có.

Mở r ngộ  ngôn ng  ữ (language extension). Bộ tiền x  ử lý tăng kh  ả năng  cho ngôn  ngữ bằng một số các macro nội tại của nó. Thí dụ ngôn ngữ Equel  là ngôn ngữ hỏi  đáp  với  cơ  sở  dữ  liệu  được  nhúng  vào  ngôn  ngữ  C.  Các  phát  biểu  được  bắt  đầu  bằng hai dấu # # ở trong C được bộ tiền xử lý, xử  lý, là các phát biểu truy xuất cơ  sở dữ liệu, không liên quan đến C, được dịch  thành các phát biểu gọi thủ tục, sẽ gọi  các trình con đặc nhiệm trong mã máy  để thực hiện việc truy xuất cơ sở dữ liệu.

Bây giờ ta sẽ nói kỹ hơn về bộ xử lý macro. Bộ xử lý này thường làm

việc với hai loại phát biểu: định nghĩa macro và sử dụng macro.

Định  nghĩa  macro  bao  gồm:  từ  khoá  define  hoặc  macro,  tiếp  theo  là

70

tên  macro.  Theo  sau  là  thân  (body)  của  macro.  Chẳng  hạn,  \define   {}.

Thông  thường  bộ  xử  lý  macro  cho  phép  các  thông  số  hình  thức  (formal  parameter) trong định  nghĩa,  chúng là  các ký  hiệu  sẽ  bị  thay  thế  bởi  các trị (chuỗi các ký tự) sau này khi macro được dùng.

Phát  biểu  dùng  macro  bao  gồm:  tên  macro  và  các  thông  số  thực

(actual parameter), là trị của các thông số hình thức trong thân của macro.

71

Thí dụ 4.5:

H  ệ thóng đánh máy typesetting có phương tiện macro với phát biểu định

nghĩa macro như sau:

\define