Ngôn ngữ hình thức

Chương1. Văn Phạm và ngôn ngữ
$1. Các khái niệm cơ bản.
Các khái niệm chung.
Bảng chữ cái. Bảng chữ cái là một tập hợp hữu hạn các phần tử, các phần tử của nó ta gọi là các chữ cái hoặc các ký tự.
b. Ví dụ. - Tập các ký tự La tinh {a,b,…,z, A,B,…,Z}
- Tập các số{0,1}
- Tập các các ký tự La tinh {(,(,(,…}.
- Tập các số {0,1,2,3,4,5,6,7,8,9}.
Chú ý răng bảng chữ cái là một tập hợp nên ta ta vẫn dùng các ký hiệu thuộc như trong lý thuyết tập hợp.
Xâu sinh ra trên bảng chữ cái.
Xâu. Xâu hay từ được sinh ra trên bảng chữ cái là một dãy bất kỳ các phần tử thuộc dãy đó. Gọi xâu là x , độ dài xâu được ký hiệu là (x(. Như vậy khái niệm xâu cũng đồng nghĩa với khái niệm chuỗi ký tự. Xâu rỗng là xâu không chứa phần tử nào thường ký hiệu e.
Tập Các xâu. Cho V là một bảng chữ cái, gọi V+ là tập tất cả các xâu sinh ra từ V trừ xâu rỗng, V* là tập tất cả các xâu sinh ra từ V kể cả xâu rỗng. V*= V+({e}.
Ví dụ: V={a,b,c} X+={abc,cab,…}
V={0,1} V*={e,00,1,0,100,…}
Ta quy ước rằng an:=aa…a, n lần ký tự a.
Các phép toán trên xâu.
Ghép 2 xâu. Cho xâu x=abc…k, y=rp..q phép ghép 2 xâu là xâu nối 2 xâu với nhau xy:= abc…krp..q.
Đảo ngược 2 xâu. Cho x=x1x2…xk gọi xâu x’:= xkxk-1…x1 là xâu đảo của x.
Khái niệm ngôn ngữ.
a. Ngôn ngữ trên bảng chữ cái. Cho V là tập chữ cái gọi tập con bất kỳ của V* là ngôn ngữ trên bảng V.
Như vây ngôn ngữ là một tập hợp ký hiệu là L .Số phần tử của L là lực lượng của nó, nếu hữu hạn thì ta nói L là ngôn ngữ hữu hạn và vì nó là tập hợp nên mọi phép toán trên L cũng giống như trên tập hợp
L1(L2:={x: x thuộc L1 hoặc x thuộc L2}
L1(L2:={x: x thuộc L1 và x thuộc L2}
L1L2:={x=uv: u thuộc L1 và v thuộc L2}
L0:={e}; Ln:=Ln-1L; L+:=L1L2..Ln n>=1 gọi là tập các xâu có độ dài nhỏ hơn hoặc bằng n. L*:=L+(
{e}.
1.3. Văn phạm và ngôn ngữ sinh bởi văn phạm.
Định nghĩa. Văn phạm G là một bộ gồm các thành phần G:=(N,T,S,P) trong đó:
N là một tập hữu hạn các ký tự không kết thúc.
T là một tập hữu hạn các ký tự kết thúc và N(T=(.
P là tập các luật sinh(luật sản xuất, quy tắc dẫn xuất) , nói cách khác P là các ánh xạ từ (N(T)* vào (N(T)*. Nếu q((N(T)* là ảnh của p qua luật sản xuất P ta ký hiệu p(q và gọi