bài tập chương III otomat hữu hạn và biểu thức chính quy

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 cho như sau :

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ộ chữ cái Σ = {0, 1}

1. Tập các chuỗi kết thúc là 00.
2. Tập các chuỗi có 3 ký hiệu 0 liên tiếp.

c) Tập các chuỗi mà ký hiệu thứ 3 kể từ cận phải của chuỗi là 1.

d) Tập mọi chuỗi mà bất cứ chuỗi con nào có độ dài bằng 5 đều có chứa ít nhất 2 con số 0.

Tìm các sơ đồ chuyển ôtômát hữu hạn đoán nhận các ngôn ngữ sau :

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

b) Tập các chuỗi trên {0, 1} có độ dài chia hết cho 3.

c) Tập các chuỗi trên {0, 1} không chứa 101 như một chuỗi con.

Xây dựng DFA tương đương với mỗi NFA sau :

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 :

1. 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 hiện trước đó .
2. Tập hợp các chuỗi trên Σ = {0, 1} trong đó có một cặp ký tự 0 cách nhau bởi một chuỗi con có độ dài 4i, với i ≥ 0 nào đó.

Viết biểu thức chính quy cho mỗi ngôn ngữ sau trên Σ = { 0, 1} :

a) Tập hợp các chuỗi trong đó mọi cặp 0 liên tiếp đều xuất hiện trước mọi cặp 1 liên tiếp.

b) Tập hợp các chuỗi chứa nhiều nhất một cặp 0 liên tiếp và nhiều nhất một cặp 1 liên tiếp.

Mô tả (bằng lời) ngôn ngữ được các biểu thức chính quy sau đặc tả :

1. 0(0 + 1)^* 0
2. (0+ 1)^*0(0 + 1) (0 + 1)
3. (11+ 0)^*(00+ 1)
4. (1+ 01+ 001)^*(ε + 0 + 00)
5. [ 00 + 11 + (01+ 10) (00+ 11)^*(01+ 10)]^*

Chứng tỏ các biểu thức chính quy sau ký hiệu cho cùng một ngôn ngữ :

(aa)^* , (aa)^* + (∅a) , (aa + aaaa)^* , (aa)^* (aa)^*

Vẽ NFA với ε-dịch chuyển được cho bởi các biểu thức chính qui sau. Sau đó, hãy chuyển sang DFA tương đương :

1. ( a^* + b^*)^*
2. ((ε + a) b^*)^*
3. (a + b)^* abb (a + b)^*
4. ab + (a + bb) a^*b
5. (a + ab + aab)^*(ε+ a+ aa)
6. 10 + (0 + 11)0^*1
7. 01 [ (( 10)^*+ 111)^* + 0]^*1

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 trong Pascal / C mô phỏng một FA chấp nhận ngôn ngữ được biểu diễn bởi biểu thức chính quy 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 quy.

Viết chương trình cho ra DFA khi đầu vào là một NFA.