Tin học lý thuyết - Chương 3

quan hệ giữa cơ chế ôtômát và các biểu thức chính quy dùng ký hiệu cho ngôn ngữ. Vẽ sơ đồ chuyển trạng thái (đơn định hoặc không đơn định) từ một biểu Ôtômát hữu hạn FA là một mô hình tính toán của hệ thống với sự mô tả bởi các input Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn hạn, và lý thuyết về ôtômát hữu hạn là một công cụ thiết kế hữu ích cho các hệ thống Mỗi trạng thái của một mạng chuyển mạch với n cổng bất kỳ sẽ là một phải nhớ một số hữu hạn thông tin như các ký tự bắt đầu hình thành những chuỗi từ Máy tính cũng có thể được xem như một hệ thống trạng thái hữu hạn. bất kỳ là một trong những số rất lớn và hữu hạn của số trạng thái. cũng là một hệ thống trạng thái hữu hạn, vì số các tế bào thần kinh hay gọi là neurons Lý do quan trọng nhất cho việc nghiên cứu các hệ thống trạng thái hữu hạn là tính tự Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -gồm một tập hữu hạn các trạng thái và một tập các phép chuyển từ trạng thái này tới trạng thái khác trên các ký hiệu đúng một phép chuyển khỏi mỗi trạng thái (có thể chuyển trở về chính nó). thái, thường ký hiệu là q0, gọi là trạng thái bắt đầu (trạng thái ôtômát bắt đầu). trạng thái được thiết kế như là các trạng thái kết thúc hay trạng thái chấp nhận. DFA như sau: các đỉnh của đồ thị là các trạng thái của DFA; nếu có một đường chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a chuyển từ tồn tại dãy các phép chuyển tương ứng trên mỗi ký hiệu của x dẫn từ trạng thái bắt Chẳng hạn, sơ đồ chuyển của một DFA được mô tả trong hình 3.1. cũng là q0 trong trường hợp này, được chỉ ra bằng hai vòng tròn. Một cách hình thức ta định nghĩa ôtômát hữu hạn là bộ gồm năm thành phần (Q, Σ, δ, . Q là tập hợp hữu hạn các trạng thái. . δ là hàm chuyển ánh xạ từ Q × Σ → Q, tức là δ(q, a) là một trạng thái được cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a. . F ⊆ Q là tập các trạng thái kết thúc. Ta vẽ DFA như là bộ điều khiển hữu hạn, với mỗi trạng thái thuộc Q, DFA đọc một Trong một lần chuyển, DFA đang ở trạng thái q đọc ký hiệu nhập a trên băng, chuyển sang trạng thái được xác định bởi hàm chuyển δ(q, a), rồi dịch đầu đọc sang phải một Nếu δ(q, a) chuyển đến một trong những trạng thái kết thúc thì DFA chấp nhận Để có thể mô tả một cách hình thức hoạt động của một DFA trên chuỗi, ta mở rộng hàm chuyển δ để áp dụng đối với một trạng thái trên chuỗi hơn là một trạng thái trên Ta định nghĩa hàm chuyển δ như một ánh xạ từ Q × Σ* → Q với ý nghĩa δ(q, w) là trạng thái DFA chuyển đến từ trạng thái q trên chuỗi w. - Q là tập các trạng thái. Ký hiệu q và p (có hoặc không có chỉ số) là các - w, x, y và z (có hoặc không có chỉ số) là các chuỗi ký hiệu nhập. Một chuỗi w được chấp nhập bởi ôtômát hữu hạn M (Q, Σ, δ, q0, F) nếu δ(q0, w) = p Ngôn ngữ được chấp nhận bởi M, ký hiệu L(M) là tập hợp: table) để mô tả các phép chuyển trạng thái của một ôtômát hữu hạn. chuyển, hàng chứa các trạng thái thuộc tập trạng thái của ôtômát và cột là các ký hiệu Một cách tổng quát, ta thấy tập Q của DFA thể hiện các trạng thái lưu trữ của ôtômát trong quá trình đoán nhận ngôn ngữ, và như vậy khả năng lưu trữ của ôtômát là hữu phép chuyển từ một trạng thái trên cùng một ký hiệu nhập. chuỗi các phép chuyển, tương ứng với chuỗi nhập, từ trạng thái bắt đầu đến trạng thái có chuỗi phép chuyển qua các trạng thái q0, q0, q0, q3, q4, q4 có nhãn tương ứng là 0, Chú ý rằng có thể xem ôtômát hữu hạn đơn định - DFA (hay gọi tắt là FA) là một trường hợp đặc biệt của NFA, trong đó mỗi trạng thái chỉ có duy nhất một phép Vì thế trong DFA, với một chuỗi nhập w và trạng thái Khi có sự lựa chọn trạng thái kế tiếp, chẳng hạn như từ trạng thái q0 trên ký Mỗi trạng thái kế tiếp mà ôtômát có thể chuyển đến sẽ tương ứng với Một cách hình thức ta định nghĩa ôtômát hữu hạn không đơn định NFA là một bộ 5 thành phần (Q, Σ, δ, q0, F) trong đó Q, Σ, q0 và F có ý nghĩa như trong DFA, nhưng δ Khái niệm δ(q, a) là tập hợp tất cả các trạng thái p sao cho có phép chuyển trên nhãn 2. δ(q, wa) = { p | có một trạng thái r trong δ(q, w) mà p thuộc δ(r, a)} Ngôn ngữ L(M), với M là ôtômát hữu hạn không đơn định NFA (Q, Σ, δ, q0, F) là tập L(M) = {w | δ(q0, w) có chứa một trạng thái trong F } Vì mỗi DFA là một NFA, nên rõ ràng lớp ngôn ngữ được chấp nhận bởi NFA cũng bao gồm các tập chính quy (đây chính là ngôn ngữ được chấp nhận bởi DFA ). đó cho thấy DFA có thể mô phỏng được hoạt động của NFA, nghĩa là với mỗi NFA, ta có thể xây dựng một DFA tương đương (chấp nhận cùng một ngôn ngữ với nó). Đặt một DFA mô phỏng hoạt động của NFA là cho phép các trạng thái của DFA tương ứng với tập các trạng thái của NFA. điều khiển tất cả các trạng thái mà NFA có thể chuyển đến khi đọc cùng một input ĐỊNH LÝ 3.1 : Nếu L là tập được chấp nhận bởi một NFA thì tồn tại một DFA Đặt M (Q, Σ, δ, q0, F) là NFA chấp nhận L. - Các trạng thái của M’ là tất cả các tập hợp con của tập trạng thái của M, hay Một phần tử trong Q’ được ký hiệu là [q1, q2,..., qi], trong đó các trạng Ta xem [q1, q2,..., qi] là một trạng thái đơn của DFA tương ứng với một tập trạng thái của NFA. - F' là tập hợp các trạng thái của Q’ có chứa ít nhất một trạng thái kết thúc Với ⏐x⏐= 0 , ta có x = ε và q0’ = [q0] nên (1) hiển nhiên đúng Dễ thấy rằng δ’(q0’, x) ∈ F' khi và chỉ khi δ(q0, x) có chứa ít nhất một trạng thái ∈ F. Vì NFA và DFA chấp nhận cùng các tập hợp, nên ta sẽ không phân biệt chúng trừ khi Thí dụ 3.5 : Cho NFA M ({q0, q1}, {0, 1}, δ, q0, {q1}) với hàm chuyển δ như sau : Ta xây dựng DFA tương đương M’ (Q’, {0, 1}, δ’, [q0], F’) chấp nhận L(M) như sau : Thực tế, có rất nhiều trạng thái của NFA không có hàm chuyển đến từ trạng thái bắt đầu từ trạng thái [q0] và thêm vào các trạng thái mới cho DFA chỉ khi có các hàm Bạn có nhận xét gì về kích thước giữa một DFA và một NFA tương đương với nó Ta mở rộng mô hình NFA cho phép các phép chuyển trên nhãn rỗng ε. sau đây của một NFA chấp nhận chuỗi gồm một số bất kỳ (có thể là 0) chữ số 0 sau nói NFA chấp nhận một chuỗi w nếu có đường truyền nhãn w từ trạng thái bắt đầu Định nghĩa: Một cách hình thức ta định nghĩa NFA với ε-dịch chuyển là bộ 5 thành phần (Q, Σ, δ, q0, F) với tất cả các thành phần có ý nghĩa như trên, nhưng hàm chuyển Khái niệm δ(q, a) gồm tất cả các trạng thái p sao cho có phép chuyển nhãn a từ q tới p, trong đó a là một ký hiệu thuộc Σ hoặc là ε. δ*(q,w) chứa tất cả các trạng thái p sao cho có thể đi từ q tới p Ta sử dụng ε-CLOSURE(q) để xác định tập tất cả các đỉnh p sao cho có đường đi từ q Vì đường đi chỉ có một đỉnh q0 (không có cung trên đường đi) là đường đi từ q0 tới q0 Đặt ε-CLOSURE(P) = ∪q∈P ε-CLOSURE(q), trong đó P là một tập các trạng thái và q là một trạng thái. trong đó tập P = {p | có r trong δ*(q, w) sao cho p ∈ δ(r, a)}, ∀w ∈ Σ* và a ∈ Σ Ta mở rộng δ và δ* trên tập hợp các trạng thái R như sau : Nhận xét : δ*(q, a) và δ(q, a) không nhất thiết bằng nhau vì δ*(q, a) gồm tất cả các trạng thái có thể chuyển đến được từ q trên nhãn a gồm cả đường đi nhãn ε, trong khi đó δ(q, a) chỉ gồm các trạng thái có thể đến được từ q chỉ bằng các cung nhãn a. Tương tự δ*(q, ε) có thể cũng không bằng δ(q, ε). Ta định nghĩa L(M), ngôn ngữ được chấp nhận bởi NFAε M = (Q, Σ, δ, q0, F) là tập L(M) = {w | δ*(q0, w) có chứa ít nhất một trạng thái trong F} Theo khái niệm hình thức, ta có NFA M ({q0, q1, q2}, {0, 1, 2}, δ, q0, {q2}) với hàm Do δ*(q0, 012) có chứa trạng thái q2 ∈ F nên chuỗi w ∈ L(M). Tương tự như NFA, khả năng có thể thực hiện phép chuyển trên nhãn ε của NFAε cũng không làm cho NFAε chấp nhận được các tập hợp không chính quy. ĐỊNH LÝ 3.2 : Nếu L được chấp nhận bởi một NFA có ε-dịch chuyển thì L cũng được chấp nhận bởi một NFA không có ε-dịch chuyển. Đặt M (Q, Σ, δ, q0, F) là NFA với ε-dịch chuyển. Ta xây dựng NFA M’(Q, Σ, δ’, q0, F’) tương đương không có ε-dịch chuyển, F ∪ {q0} nếu ε-CLOSURE(q0) chứa một trạng thái thuộc F có thể không đúng với x = ε vì δ’(q0, ε) = {q0} trong khi δ *(q0, ε) = ε-CLOSURE(q0). Với | x | = 1 thì x là một ký hiệu a và δ’(q, a) = δ *(q, a) theo định nghĩa δ’. Để đầy đủ chứng minh ta còn phải chỉ ra rằng δ’(q0, x) chứa một trạng thái trong F’ nếu và chỉ nếu δ *(q0, x) chứa một trạng thái trong F. Nếu δ *(q0, x) chứa một trạng thái trong F thì chắc chắn δ’(q0, x) chứa cùng Ngược lại, nếu δ’(q0, x) chứa một trạng thái trong F’ khác hơn q0 thì δ(q0, x) phải chứa một trạng thái trong F (vì tập F và F’ chỉ chênh lệch nhau Nếu δ’(q0, x) có chứa trạng thái q0 và q0 cũng là một trạng thái thuộc tập trạng thái kết thúc F thì vì δ *(q0, x) = ε-CLOSURE(δ(δ *(q0, w),a)), nên trạng thái chung trong ε-CLOSURE(q0) và trong F phải ở trong δ *(q0, x). Ta xây dựng NFA tương đương M’(Q, Σ, δ’, q0, F’) chấp nhận L(M) với các thành - Với mỗi trạng thái q và ký hiệu nhập a, chỉ có duy nhất một đường truyền Giả sử mỗi trạng thái của DFA là một tập trạng thái của NFA, DFA dùng trạng thái của mình để lưu giữ tất cả các trạng thái của NFA đạt được sau khi NFA đọc một ký con của các trạng thái thuộc NFA, đạt được khi NFA đi từ trạng thái bắt đầu theo một Các trạng thái thực sự được dùng trong sơ đồ chuyển cho một DFA sẽ được xác định theo các phép chuyển trạng thái trên nhãn là mọi ký hiệu từ trạng thái bắt đẩu của DFA, và sau đó lần lượt được bổ sung thêm vào tập trạng thái nếu như nó Ta dùng các tác vụ sau để lưu giữ các tập trạng thái của NFA : (q : là một trạng thái của NFA, T : là tập trạng thái của NFA) a) ε-closure(q) : là tập trạng thái của NFA đạt được từ trạng thái q trên sự b) ε-closure(T) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q c) δ(T, a) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q thuộc Trước khi đọc vào một ký tự nhập, DFA có thể ở một trạng thái bất kỳ trong các trạng thái thuộc ε-closure(q0) với q0 là trạng thái bắt đầu của NFA. Giả sử các trạng thái của T là các trạng thái đạt được từ q0 trên các ký hiệu Khi đọc a, NFA có thể chuyển đến một trạng thể ở bất kỳ trạng thái nào trong ε-closure(δ(T, a)) sau khi đã đọc a. Trạng thái bắt đầu ε-closure(q0) chỉ là một trạng thái trong các trạng thái While Có một trạng thái T của DFA chưa được đánh dấu do If U không có trong tập trạng thái của DFA then Ta xây dựng các trạng thái và bảng hàm chuyển cho DFA theo cách như sau : có thể chuyển đến sau khi đọc một chuỗi ký hiệu nhập gồm: tất cả sự truyền rỗng có - Trạng thái bắt đầu của DFA là ε-closure(q0) - Các trạng thái và hàm chuyển sẽ được thêm vào D bằng giải thuật trên. - Một trạng thái của DFA là trạng thái kết thúc nếu nó là tập các trạng thái của Việc tính toán ε-closure(T) có thể xem như quá trình tìm kiếm một đồ thị của các nút từ các nút cho trước và đồ thị bao gồm toàn những cạnh có nhãn ε của NFA. thuật đơn giản để tìm ε-closure(T) là dùng Stack để lưu giữ các trạng thái mà cạnh Từ các tập trạng thái này, ta xác định được A là trạng thái bắt đầu, E là trạng thái kết thúc (vì trong E có chứa trạng thái 10 là trạng thái kết thúc của NFA) và bảng hàm Từ bảng hàm chuyển như trên, ta xây dựng sơ đồ chuyển trạng thái cho DFA tương được duy nhất từ một chuỗi nhập bất kỳ và trạng thái bắt đầu. Lớp ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn cũng có thể được mô tả thông Kleene trên các tập hợp chuỗi để định nghĩa biểu thức chính quy và chứng tỏ rằng lớp ngôn ngữ được chấp nhận bởi một ôtômát hữu hạn thì thực sự là lớp ngôn ngữ được Biểu thức chính quy trên Σ và các tập hợp mà chúng mô tả 1) ∅ là biểu thức chính quy ký hiệu cho tập rỗng 2) ε là biểu thức chính quy ký hiệu cho tập {ε} 3) ∀a ∈ Σ, a là biểu thức chính quy ký hiệu cho tập {a} 4) Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s), (rs) và ( r*) là các biểu thức chính quy ký hiệu cho các tập hợp R ∪ S, RS, R* tương Trong khi viết biểu thức chính quy ta có thể bỏ bớt các dấu ngoặc đơn với lưu ý rằng Như trên ta nói, biểu thức chính quy dùng ký hiệu cho một lớp ngôn ngữ. hãy thử liệt kê một vài chuỗi và hình dung lớp ngôn ngữ được ký hiệu bởi biểu Nếu cần thiết phân biệt thì ta sẽ dùng ký hiệu r cho biểu thức chính quy r và L(r) cho ngôn ngữ được ký hiệu bởi biểu thức chính quy r; ngược lại một cách tổng quát, ta có Thí dụ 3.11 : Một số biểu thức chính quy ký hiệu cho các ngôn ngữ : . (0+1)*00(0+1)* ký hiệu cho tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 . (1+10)* ký hiệu cho tất cả các chuỗi 0, 1 bắt đầu bằng số 1 và không có hai số . (0+ε)(1+10)* ký hiệu cho tất cả các chuỗi không có hai số 0 liên tiếp. . 0*1*2* ký hiệu cho tất cả các chuỗi có một số bất kỳ các số 0, theo sau là một . 00*11*22* ký hiệu cho tất cả các chuỗi trong tập 0*1*2* với ít nhất một trong Thí dụ 3.12 : Biểu thức chính quy ký hiệu cho tập hợp các chuỗi tên biến đúng trong Pascal nếu như nó bắt đầu bằng ít nhất một chữ cái và theo sau đó là các chữ cái, số, Thí dụ 3.13 : Biểu thức chính quy ký hiệu cho tập hợp các số nguyên trong ngôn ngữ âm (-) hoặc dấu dương (+) hay không chứa ký hiệu dấu, và theo sau đó là một chuỗi các ký hiệu số với ít nhất là một số. Nhận xét : Thông thường, việc tìm một biểu thức chính quy ký hiệu cho một ngôn ngữ khó hơn việc xác định ngôn ngữ được ký hiệu bởi một biểu thức chính quy vì Dễ dàng chứng minh rằng, nếu cho r, s, t là các biểu thức chính quy thì ta có các đẳng Như trên đã nói, các ngôn ngữ được chấp nhận bởi ôtômát hữu hạn cũng là các ngôn gọi ngôn ngữ chấp nhận bởi ôtômát hữu hạn là các tập chính quy. trong) biểu thức chính quy rằng có tồn tại một NFA với ε-dịch chuyển chấp nhận cùng ngôn ngữ; đồng thời với mỗi DFA cũng có một biểu thức chính quy xác định ĐỊNH LÝ 3.3: Nếu r là biểu thức chính quy thì tồn tại một NFA với ε-dịch Ta sẽ chứng minh quy nạp theo số phép toán của biểu thức chính quy r rằng có tồn tại một NFA M với ε-dịch chuyển có một trạng thái kết thúc và không có các phép chuyển khỏi trạng thái này chấp nhận biểu thức chính quy r: L(M) = L(r). Cả hai biểu thức chính quy r1, r2 có ít hơn i phép toán, vậy ta có 2 ôtômát hữu hạn Vì các trạng thái có thể thay đổi tên nên ta giả sử hai tập trạng thái Q1 Đặt q0 là trạng thái bắt đầu mới và {f0} là tập trạng thái kết thúc mới, ta xây dựng NFA M (Q1 ∪ Q2 ∪ {q0, f0}, Σ1 ∪ Σ2, δ, q0, {f0}), trong đó δ được xác Chú ý do giả thiết quy nạp là không có phép chuyển nào ra khỏi f1, f2 trong M1, Vì vậy tất cả các phép chuyển của M1 và M2 đều có trong M. và chỉ khi có đường đi nhãn x trong M1 từ q1 đến f1 hoặc có đường đi nhãn x trong M2 Đặt M1 và M2 là các ôtômát NFA như trong trường hợp trên và ta xây dựng ôtômát M (Q, Σ , δ, {q1}, {f2}), trong đó δ được xác định như sau: có nhãn x từ q1 tới f1 sau đó là một cung từ f1 tới q2 nhãn ε và tiếp đến là đường đi từ Xây dựng M (Q1∪ {q0, f0} Σ1, δ, q0, {f0}), trong đó δ được cho: đường đi từ q0 tới f0 bằng nhãn ε; hoặc đường đi từ q0 tới q1 bằng nhãn ε và sau đó là đi từ q0 tới f0 nhãn là x nếu và chỉ nếu ta có thể viết x = x1 x2 ... đơn 0, 1 và các chuỗi bit nhị phân bắt đầu bằng bit 0, theo sau là một chuỗi bit 1 với Ta sẽ lần lượt xây dựng các NFA cho các biểu thức chính quy con, sau đó dựa vào của các phép toán được sử dụng trong biểu thức chính quy, điều này rất quan trọng Bây giờ, ta cần chứng tỏ rằng mọi tập hợp được chấp nhận bởi một ôtômát hữu hạn thì cũng được ký hiệu bởi một số biểu thức chính quy. Đặt L là tập hợp được chấp nhận bởi DFA M ({q1, q2,..., qn}, Σ, δ, q1, F). Đặt Rkij là tập hợp tất cả các chuỗi x sao cho δ(qi, x) = qj và nếu δ(qi, y) = ql, với y là (Chú ý, khái niệm "đi ngang qua một trạng thái" có nghĩa là có phép chuyển vào và ra khỏi trạng thái đó, nên i hoặc j đều có thể lớn hơn k). trạng thái nên Rnij sẽ là tập hợp tất cả các chuỗi làm ôtômát đi từ qi tới qj. Một cách hình thức, Rkij định nghĩa như trên là các chuỗi nhập hay nguyên nhân đưa M từ qi tới qj không đi ngang qua trạng thái cao hơn qk, nghĩa là xảy ra hoặc một mà không ngang qua qk hoặc một trạng thái nào cao hơn) và cuối cùng là Ta sẽ chỉ ra rằng với mỗi i, j và k tồn tại biểu thức chính quy rkij ký hiệu cho ngôn . k = 0 : khi đó R0ij là tập hợp hữu hạn các chuỗi có một ký hiệu hoặc ε. Trong đó {a1, a2,..., ap} là tập hợp tất cả các ký hiệu a sao cho δ(qi, a) = qj. Cuối cùng ta có nhận xét rằng L(M) = ∪qj ∈ F Rn1j vì Rn1j ký hiệu cho tất cả các nhãn Thí dụ 3.15 : Viết biểu thức chính quy ký hiệu cho ngôn ngữ được chấp nhận bởi Gọi DFA được chỉ ra trong hình 3.10 là M ({q1, q2, q3}, {0, 1}, δ, q1, {q2, q3}). thấy, tập hợp tất cả các chuỗi được chấp nhận bởi DFA trên là các chuỗi làm cho ôtômát chuyển từ trạng thái bắt đầu q1 đến một trong hai trạng thái kết thúc q2 và q3 và không chuyển qua số tối đa là 3 (k = 3) trạng thái của ôtômát. thức chính quy ký hiệu cho tập hợp này như sau : Theo công thức đã được chứng minh trong Định lý, ta có thể tính được các giá trị rkij với i, j là chỉ số các trạng thái từ 1 đến 3 và với k = 0, 1 và 2, như chỉ ra trong bảng Các ký hiệu từ vựng (token) trong một ngôn ngữ lập trình thì hầu hết không có sự Một ví dụ khác, các định danh của FORTRAN có độ dài giới hạn là 6 và các chữ cái chính quy mô tả các ký hiệu từ vựng và phát sinh một ôtômát hữu hạn đơn giản nhận thành một NFA với ε-dịch chuyển và sau đó xây dựng tập hợp con các trạng thái để có thể phát sinh DFA một cách trực tiếp hơn là tìm cách loại bỏ các phép chuyển thế một chuỗi bởi mọi chuỗi kết hợp với một biểu thức chính quy cho trước. cho phép thay thế các chuỗi có dạng bbb* thành chuỗi có một ký tự b. sẽ cho phép xóa đi tất cả các file với tên tập tin bắt đầu bằng tmp, sau đó là một chuỗi Ta có thể chuyển một biểu thức chính quy r sang DFA chấp nhận mọi r. sự hiện diện của ký hiệu * sẽ cho phép ta nhận dạng một thành phần của L(r) bắt đầu cách duyệt qua chúng một lần, tuy DFA có thể có số trạng thái là hàm mũ của độ dài chuyển thành một NFA có ε-dịch chuyển và sau đó NFA này được mô phỏng một Mô tả ngôn ngữ được chấp nhận bởi các ôtômát hữu hạn với sơ đồ chuyển được Xây dựng các sơ đồ chuyển ôtômát hữu hạn chấp nhận các ngôn ngữ sau trên bộ a) Tập các chuỗi trên {0, 1} có chứa một số chẵn các số 0 và một số lẻ các số 1 Tìm NFA không có ε-dịch chuyển nhận dạng cùng ngôn ngữ với các NFA sau : Viết biểu thức chính quy và vẽ NFA đoán nhận các ngôn ngữ sau : a) Tập hợp các chuỗi trên Σ = {1, 2, 3} sao cho ký hiệu cuối cùng đã có xuất b) Tập hợp các chuỗi trên Σ = {0, 1} trong đó có một cặp ký tự 0 cách nhau Chứng tỏ các biểu thức chính quy sau ký hiệu cho cùng một ngôn ngữ : Vẽ NFA với ε-dịch chuyển được cho bởi các biểu thức chính qui sau. Hãy tìm các biểu thức chính qui tương ứng với các sơ đồ chuyển trạng thái sau: Viết chương trình cho ra một FA tương ứng khi đầu vào là một biểu thức chính