Giáo trình Lý thuyết ngôn ngữ hình thức và ô tô mát

Kill nghiên cửu ngôn ngừ cấn một cơ chế mò tà ngôn ngừ đó là văn phạm (grammar). Một cách không hình thức, văn phạm là các quy tắc sinh câu đúng.

Đối với ngôn ngừ tự nhiên, văn phạm là hệ thống ngừ pháp. Đối với ngôn ngừ lập trình, văn phạm là các quy tắc cú pháp viết chương trinh.

Ví dụ ỉ, 7. Định nghía một câu tiếng Việt đơn giàn bời văn phạm sau:

—>

I

—> <động hr=""> I <động hr="">

I

Văn phạm trên sinh ra các câu đúng sau:

- Con hố ăn con bò đen.

- Học sinh nói chuyện nhiều.

Định nghía 1.1. Văn phạm G được định nghía như là bộ bốn:

G = (N, I, R, S)

trong đó:

- N là tập họp hừư hạn các kí hiệư không kết thúc (non terminal symbol) hay còn được gọi là các biến:

- z là bâng chừ, tập các kí hiệư kết thúc (terminal symbol), Nn z = 0:

- s E N là kí hiệu đầu hay biến khởi đấu;

- R là tập các quy tắc (rule) hoặc các sân xuất/luật sinh (production), các luật sinh có dạng:

a —> p

trong đó a G (Nu Z)~ có chửa ít nhất một biến. PG (N u Z) .