– Phi ngữ cảnh : …chưa kết thúc nào đó

– DFA, duy nhất 1 phép chuyển trên kí hiệu nhập

– {q1,q2}

– L(M1)*

– V(G,T,P,S) : A -> alpha, A thược V

– r511 + r512 + r513

– q0: 0 chẵn 1 chẵn. q phải: 0 chẵn 1 lẻ. q dưới: 0 lẽ 1 chẵn. q chéo: 0 lẽ 1 lẽ

– (,)

Chương 1: Bổ túc toán

1. Phép toán trên tập hợp

2. Quan hệ

– Tính chất:

– P có 2 lớp tương đương là {0, 2} và {1, 3}

3. Bao đóng quan hệ

4. Đồ thị

– Đồ thị G=(V, E) với V là tập các đỉnh, E là tập các cạnh

Chương 2: Ngôn ngữ và sự phân phối Chomsky

1. Khái niệm

Ký hiệu : Thực thể trừu tượng không định nghĩa được cách thức

Bộ chữ cái : Tập không rỗng các ký hiệu đó + Bộ chữ cái Latinh

Chuỗi : Dãy hữu hạn các ký hiệu + Có thể xuất hiện nhiều lần

Độ dài chuỗi : số ký hiệu tạo thành chuỗi

Chuỗi  rỗng : ét-xi-lon. |3|=0

Tiền/Hậu tố : chuỗi con bất kỳ nằm ở đầu/cuối chuỗi

Nối kết : 3w=w3=w

Chuỗi đảo ngược :

    • w=abcd —-> w^R = dcba
    • 3^R = 3
Văn phạm : cơ chế sản sinh ra mọi chuỗi của ngôn ngữ
Automata : cho phép nhận một chuỗi bất kì có thuộc ngôn ngữ L hay không

2. Ngôn ngữ

– Một ngôn ngữ L là tập hợp các chuỗi của các ký hiệu từ một bộ chữ cái ZE nào đó

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

3. Văn phạm

– Theo từ điển : Văn phạm là … quy tắc cấu tạo và quy tắc cách thức liên kết

– Gồm 4 thành phần: Biến + Ký hiệu + Luật sinh + KH bắt đầu

– Văn phạm tương đương : Văn phạm cũng sinh ra một ngôn ngữ

– Phân loại : Không hạn chế-Cảm ngữ cảnh-Phi ngữ cảnh-Chính quy.

4. Automata

ĐN: là máy trừu tượng có cơ cấu và hoạt động đơn giản nhưng có khả năng đón nhận ngôn ngữ.

– Đơn định (DFA) và không đơn định (NFA)

Chương 3: Automata hữu hạn và biểu thức chính quy

1. Sơ đồ liên hệ: 

2. Các định lý :

– Định lý 1:

– Định lý 2:

– Định lý 3:

– Định lý 4:

3. 3 Otômát :

4. Biểu thức chính quy

– Định nghĩa:

– Các tính chất

5. Các giải thuật