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

1.1 Giới thiệu

Vào những năm 1930, Alan Turing đã nghiên cứu các máy trừu tượng có khả năng thực hiện các tỉnh toán như máy tính ngày nay. Các máy trừu tượng này được gọi là máy Turing. Vào những năm 1940 và 1950, các máy trừu tượng đơn giản hơn, mà chúng ta gọi là ôtômát hữu hạn, đã được nghiên cứu bởi các nhà khoa học.

Sau đó, vào những năm 1950, nha ngôn ngữ học Chomsky đã thực hiện các nghiên cứu về vẫn phạm hình thức, Văn phạm nay có mối quan hệ chặt chẽ với ôtômát và ngày nay văn phạm là một phần nền tảng của việc xây dựng một số phần mềm, đặc biệt mà các chương trình dịch.

Ôtômát là mô hình hữu ích cho nhiều phần mềm quan trọng. Chẳng hạn dưới đây là một số ứng dụng:

• Phần mềm thiết kế và kiểm tra các mạch điện tử số. • Bộ phân tích từ vựng của một chương trình dịch. • Dịch từ ngôn ngữ bậc cao sang ngôn ngữ bậc thấp. • Dịch từ ngôn ngữ tự nhiên này sang ngôn ngữ tự nhiên khác (Anh, Pháp, Việt, .).

• Tìm kiếm từ trong văn bản. Ba khái niệm cơ bản của môn học này là ngôn ngữ, văn phạm và ôtômát sẽ được trình bày từ các lớp đơn giản đến các lớp phức tạp và mối quan hệ mật thiết giữa chúng. 1.2 Khái niệm về ngôn ngữ

Một ngôn ngữ, cho dù là ngôn ngữ tự nhiên hay ngôn ngữ lập trình, thì đều được xem là một tập hợp các câu. Tuy nhiên, trước khi có định nghĩa chính xác về ngôn ngữ, chúng ta sẽ tìm hiệu một số các quan niệm hình thức về ngôn ngữ. 1.2.1 Bảng chữ (alphabet) | Bảng chữ hay còn gọi là bộ i tự là một bảng hữu hạn các i hiệu (symbol). Bảng chữ thường được hiệu là: Vẻ đụ 1.1. Cho các bảng chỉ sau:

{a, b, c, ., z}: bảng chữ cái Latin {0, 1, .,9} : bảng chữ số thập phân {0, 1} : bảng chữ số nhị phân