NHẬP MÔN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC . KHÁI NIỆM NGÔN NGỮ. . Mở đầu: Từ ngàn xưa con người muốn giao tiếp với nhau phải dùng ngôn ngữ. Ngôn ngữ để con người có thể giao tiếp với nhau được gọi là ngôn ngữ tự nhiên, chẳng hạn như tiếng Anh, tiếng Nga, tiếng Việt là các ngôn ngữ tự nhiên. Con người muốn giao tiếp với máy tính tất nhiên cũng thông qua ngôn ngữ. Con người muốn máy tính thực hiện công việc, phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy. | CHƯƠNG I NHẬP MÔN VỀ VĂN PHẠM VÀ NGÔN NGỮ HÌNH THỨC . KHÁI niệm ngôn ngữ. . Mở đầu Từ ngàn xưa con người muốn giao tiếp với nhau phải dùng ngôn ngữ. Ngôn ngữ để con người có thể giao tiếp với nhau được gọi là ngôn ngữ tự nhiên chẳng hạn như tiếng Anh tiếng Nga tiếng Việt là các ngôn ngữ tự nhiên. Con người muốn giao tiếp với máy tính tất nhiên cũng thông qua ngôn ngữ. Con người muốn máy tính thực hiện công việc phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy hiểu được. Việc viết các yêu cầu ta gọi là lập trình. Ngôn ngữ dùng để lập trình được gọi là ngôn ngữ lập trình. Cả ngôn ngữ lập trình lẫn ngôn ngữ tự nhiên đều có thể xem như những tập các từ tức là các xâu hữu hạn các phần tử của một bộ chữ cái cơ sở nào đó. Khái niệm ngôn ngữ được đưa vào trong mục này rất tổng quát. Chắc chắn bao hàm cả ngôn ngữ lập trình lẫn tự nhiên và cả mọi ngôn ngữ vô nghĩa mà ta có thể nghĩ đến. Về mặt truyền thống lý thuyết ngôn ngữ hình thức liên quan đến các đặc tả cú pháp của ngôn ngữ nhiều hơn là đến những vấn đề ngữ nghĩa. Một đặc tả về cú pháp của một ngôn ngữ có hữu hạn từ ít nhất về nguyên tắc có thể được cho bằng cách liệt kê các từ. Điều đó không thể áp dụng đối với các ngôn ngữ có vô hạn từ. Nhiệm vụ chính của lý thuyết ngôn ngữ hình thức là nghiên cứu các cách đặc tả hữu hạn của các ngôn ngữ vô hạn. Lý thuyết cơ sở của tính toán cũng như của nhiều ngành khác nhau của nó chẳng hạn mật mã học có liên quan mật thiết với lý thuyết ngôn ngữ. Các tập vào và ra của một thiết bị tính toán có thể được xem như các ngôn ngữ và nói một sâu sắc hơn thì các mô hình tính toán có thể được đồng nhất với các lớp các đặc tả ngôn ngữ theo nghĩa mà sau này sẽ nêu chính xác hơn. Chẳng hạn các máy Turing có thể được đồng nhất với các văn phạm cấu trúc câu và các ôtômat hữu hạn có thể đồng nhất với các văn phạm chính quy. . Định nghĩa Một bảng chữ cái là một tập hữu hạn khác rỗng. Các phần tử của một bảng chữ cái s được gọi là các chữ cái hay các ký hiệu. Thí dụ 1 Dưới đây là .
