Bài tập lý thuyết ngôn ngữ hình thức và automata

Bài tập Lý thuyết Ngôn ngữ Hình thức và Automata

Trường ĐH Bách Khoa - Khoa CNTT - Người soạn: Hồ Văn Quân 1/5

BÀI TẬP LÝ THUYẾT NNHT&AUTOMATA

PHẦN NGÔN NGỮ CHÍNH QUI

1. Tìm các dfa cho các ngôn ngữ sau:

L1 = {w ∈ {a, b}*: na(w) mod 2 = 0, nb(w) mod 2 = 1}

L2 = {w ∈ {0, 1}*: mỗi chuỗi 00 được theo ngay sau bởi một số 1}

L3 = {tập tất cả các danh hiệu của Pascal}

Mô tả danh hiệu: bắt đầu bằng một kí tự chữ (a đến z, A đến Z) hoặc dấu gạch dưới

(_) sau đó là một chuỗi bất kỳ bao gồm các kí tự chữ, số (0 đến 9) và dấu gạch dưới.

L4 = {tập tất cả các số nguyên của Pascal}

Mô tả số nguyên: 12, +12, -12

{tập tất cả các số thực của Pascal}

Mô tả số thực: 12.5, +12.5, -12.5, 12E3, +12E3, -12E3, 12E-3, +12E+3, -12E+3,

+12E3, -12E3, 12E-312.5, +12.5, -12.5, ... Có thể có bao nhiêu số 0 đi đầu đều được,

ví dụ: 012, 0012, +012, -012, 012.5, ... Có thể được viết dưới dạng khoa học như sau:

12E3, 12.5E3, +12.5E3, -12.5E3, 12.5E+3, 12.5E-3, -12.5E-3, ...

2. Tìm các dfa cho các tập sau trên Σ = {a, b} bao gồm:

L5 = {tất cả các chuỗi có đúng một kí hiệu a}

L6 = {tất cả các chuỗi có ít nhất một kí hiệu a}

L7 = {tất cả các chuỗi có không nhiều hơn ba kí hiệu a}

3. Một “run” trong một chuỗi là một chuỗi con có chiều dài tối thiểu 2 kí tự, dài nhất có thể và bao

gồm toàn các kí tự giống nhau. Chẳng hạn, chuỗi abbbaabba chứa một “run” của b có chiều dài 3,

một “run” của a có chiều dài 2 và một “run” của b có chiều dài 2. Tìm các nfa và dfa cho mỗi

ngôn ngữ sau trên {a, b}.

L9 = {w: w không chứa “run” nào có chiều dài nhỏ hơn 3}

L10 = {w: mỗi “run” của a có chiều dài hoặc 2 hoặc 3}

L11 = {w: có tối đa hai “run” của a có chiều dài 3}

4. Tìm các dfa cho các tập trên Σ = {0, 1} được định nghĩa như sau:

L12 = {kí hiệu trái nhất khác với kí hiệu phải nhất.}

L13 = {mỗi chuỗi con bốn kí hiệu có tối đa hai kí hiệu 0. Chẳng hạn, 001110 và 011001 là

thuộc ngôn ngữ, còn 10010 thì không.}

L14 = {kí hiệu thứ tư từ bên phải khác với kí hiệu trái nhất.}

5. Xây dựng một dfa mà chấp nhận các chuỗi trên {0, 1} nếu và chỉ nếu giá trị của chuỗi, được diễn

dịch như là biểu diễn nhị phân của một số nguyên, là bằng 0 trong modulo của 5. Chẳng hạn,

0101 và 1111, biểu diễn tương ứng các số nguyên 5 và 15, là được chấp nhận.

6. Tìm dfa chấp nhận ngôn ngữ sau trên {a, b}:

L15 = {vwv: w ∈{a, b}*

, v= 2};

7. Tìm các nfa cho các ngôn ngữ sau:

L1 = {vwv

R

∈ {a, b}*: |v| = 2}

L2 = {ababn

: n ≥ 0} ∪ {aban

: n ≥ 0} (với điều kiện nfa có không nhiều hơn 5 trạng thái)

L3 = {an

bm : (n+m) mod 3 = 0}

L4 = {w ∈ {a, b}*: na(w) chẵn, nb(w) lẽ}

L5 = {w ∈ {0, 1}*: giá trị thập phân của w chia hết cho 6}

L6 = {w ∈ {a, b}*: số kí tự a trong chuỗi là một số lẽ}

L7 = {ab, abc}*

(với điều kiện nfa chỉ có 3 trạng thái)

L8 = {an

: n ≥ 0} ∪ {bn

a: n ≥ 1} (với điều kiện nfa chỉ có 4 trạng thái)

8. Biến đổi các nfa sau, được cho dưới dạng đồ thị và/hoặc dạng bảng truyền, thành các dfa tương

đương: