Dạng 1: Xét chuỗi nhập của DFA

Dạng 2: Xét chuỗi nhập của NFA

Dạng 3: Xét chuỗi nhập của NFA3

Dạng 4: Xây dựng DFA tương đường với  NFA

– Cho bảng

– Nếu cho hình thì lập bảng, tính N(…) rồi vẽ hình

Dạng 5: Xây dựng DFA tương đường với  NFA3
 

Dạng 6: Mô tả ngôn ngữ được kí hiệu bằng các biểu thức chính quy

1. r=a(a+b+c)*c ——-> L={ac, acbabcc, aaabcbcac, ….} ———-> ngôn ngữ bắt đầu bằng a, kết thúc là c.

2. r=(0+3)(1+10)* ——> L={3, 0, 1, 010, 0111, 10110, 0101010, ….} ———-> ngôn ngữ không chứa hai số 0 liên tiếp.

3. r=00*11*22*——-> L={012, 0012222, 001222, ….} ———-> ngôn ngữ chứa các kí tự a,b,c theo thứ tự.

—-> r=o+1+2+

Dạng 7: Viết BTCQ kí hiệu cho các lớp ngôn ngữ

1. Tập các chuỗi tên biến hợp lệ trong Pascal

  • 256 kí tự, bắt đầu là chữ cái

—–> r=(A+..+Z+a+..+z)(A+..+Z+a+..+z+0+..+9+_+3)^255

2. Tên Tiếng Việt không dấu

  • Tối đa 7, chữ đầu viết hoa

—-> r=(A+..+Z)(a+..+z+3)^6

3. SĐT được gọi từ TPCT đi toàn quốc

  • 3 mạng : 3, 6, 2. Trong 6 số cuối, số đầu không có số 0, từ 1-9. Các tỉnh tách ra 3 số đầu có thể thêm 0 hoặc 1

– Gọi hạt : r1=(3+6+2)(1-9)(0-9)^5

– Liên tỉnh : r2=0(1-9)(0-9)(0+1+3)r1

– TP lớn : 0(8+4)(3+6+2)(1-9)(0-9)^6

– Di động : 0(1-9)(0-9)^8(0-9+3)

– Dịch vụ : 11(3-9)+108+1900(1221+1575…)+…

—–> r=r1+r2+r3+r4+r5

4. Biển số xe

  • 65N1-3680
  • 28KT-355
  • 67A1-047.19

—–>r=(1-9)(0-9)(A-Z)(A-Z+1-9)(-)(0-9)^3(0-9+3+.(0-9)^2)

Dạng 8:  Vẽ NFA3 chấp nhận các BTCQ
 – r=01*+1

 – Dạng 9: Sự tương đương giữa DFA và RE