Luận án tiến sĩ về đại số khoảng otomat và các ứng dụng thực tiễn

Phân tích toàn diện về đại số khoảng otomat và ứng dụng của nó, đề xuất mô hình mới, nâng cao hiệu quả ứng dụng trong chuyên ngành

• Tác giả: Bùi Vũ Anh
• Người hướng dẫn: TS. Phan Trung Huy
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Bảo đảm Toán học cho máy tính và hệ thống tính toán
• Đề tài: Đại Số Khoảng, Otomat Khoảng Và Một Số Ứng Dụng
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. MỤC LỤC
• 1.1. Lời cam đoan
• 1.2. Danh mục từ viết tắt
• 1.3. Danh sách hình vẽ
• 1.4. Các cách tiếp cận theo hướng otomat
• 1.5. Các cách tiếp cận theo hướng đại số
• 1.6. Mục tiêu của luận án
• 1.7. Các kết quả chính của luận án
• 1.8. Cấu trúc của luận án
• 1.9. Một số khái niệm cơ sở
• 1.10. Quan hệ hai ngôi
• 1.11. Nửa nhóm, vị nhóm
• 1.12. Từ và ngôn ngữ
• 1.13. Otomat hữu hạn
• 1.14. Otomat hữu hạn đơn định
• 1.15. Mối quan hệ giữa otomat đơn định và đa định
• 1.16. Bài toán xác định ngôn ngữ
• 1.17. Otomat tối tiểu
• 1.18. Cấu trúc đại số khoảng
• 1.19. Đại số khoảng
• 1.20. Quan hệ thứ tự trên khoảng
• 1.21. Giao thức chứng thực Zero-Knowledge
• 1.22. Ví dụ về giao thức Zero-Knowledge
• 1.23. Hệ thống Zero-Knowledge dùng tích khoảng
• 1.24. Giao thức Zero-Knowledge kiểm chứng một phía
• 1.25. Ngôn ngữ và otomat khoảng
• 1.26. Ngôn ngữ khoảng
• 1.27. Các phép toán trên d-ngôn ngữ
• 1.28. Otomat khoảng đơn định và đa định
• 1.29. Bài toán đơn định hoá otomat khoảng
• 1.30. Otomat khoảng tối tiểu
• 1.31. Một số ứng dụng
• 1.32. Bài toán tìm d-đường đi nhanh nhất
• 1.33. Mô hình mạng ưu tiên (Priority Network - PN)
• 1.34. Mô hình mạng ưu tiên bằng otomat khoảng
• 1.35. Bài toán đạt được
• 1.36. Ví dụ về PN trong thực tiễn
• 1.37. Mô hình hệ thống máy tính ghép cụm
• 1.38. Lập lịch công việc
• 1.39. Thuật toán lập lịch tổng quát
• 1.40. Các công trình đã công bố
• 1.41. Tài liệu tham khảo

Tóm tắt

I. Giới thiệu về đại số khoảng và otomat

Nghiên cứu về đại số khoảng và otomat là một lĩnh vực quan trọng trong toán học và khoa học máy tính. Đại số khoảng cung cấp một khung lý thuyết để mô hình hóa và phân tích các hệ thống phức tạp. Otomat là công cụ hữu hiệu để mô hình hóa các hệ thống hoạt động dưới dạng chuyển trạng thái. Việc kết hợp giữa đại số khoảng và otomat mở ra nhiều hướng nghiên cứu mới, giúp giải quyết các bài toán trong thực tiễn. Theo nghiên cứu của Bùi Vũ Anh, việc áp dụng đại số khoảng vào otomat không chỉ giúp tăng cường khả năng biểu diễn mà còn mở rộng khả năng tính toán trên các nhãn của otomat.

1.1. Khái niệm cơ bản về đại số khoảng

Khái niệm đại số khoảng được định nghĩa dựa trên các khoảng số thực, cho phép thực hiện các phép toán như cộng, trừ, nhân, chia trên các khoảng. Điều này giúp mô hình hóa các hệ thống có tính chất không chắc chắn và biến đổi. Đại số khoảng không chỉ đơn thuần là một công cụ lý thuyết mà còn có ứng dụng thực tiễn trong các lĩnh vực như khoa học máy tính, lý thuyết thông tin và an toàn thông tin. Việc xây dựng các cấu trúc đại số trên khoảng giúp giải quyết các bài toán phức tạp hơn, từ đó nâng cao hiệu quả của các thuật toán trong thực tiễn.

1.2. Các loại otomat và ứng dụng của chúng

Có nhiều loại otomat khác nhau, bao gồm otomat hữu hạn, otomat thời gian, và otomat khoảng. Mỗi loại có những đặc điểm riêng và ứng dụng trong các lĩnh vực khác nhau. Otomat hữu hạn thường được sử dụng trong lý thuyết ngôn ngữ, trong khi otomat thời gian được áp dụng trong các hệ thống thời gian thực. Otomat khoảng là một mô hình mới, cho phép mô hình hóa các hệ thống phức tạp hơn với các ràng buộc khoảng. Việc nghiên cứu và phát triển các loại otomat này không chỉ giúp hiểu rõ hơn về lý thuyết mà còn có ứng dụng thực tiễn trong việc thiết kế và kiểm chứng các hệ thống phần mềm.

II. Phương pháp nghiên cứu và kết quả chính

Luận án của Bùi Vũ Anh đã áp dụng các phương pháp nghiên cứu hiện đại để phát triển lý thuyết về đại số khoảng và otomat. Các kết quả chính bao gồm việc xây dựng một cấu trúc đại số trên các khoảng, từ đó phát triển các thuật toán mới cho các bài toán trong lĩnh vực này. Đặc biệt, việc áp dụng đại số khoảng vào otomat đã mở ra hướng nghiên cứu mới trong việc mô hình hóa các hệ thống thời gian thực. Các thuật toán được đề xuất không chỉ có tính lý thuyết mà còn có thể áp dụng trong thực tiễn, như trong việc xây dựng giao thức bảo mật Zero-Knowledge.

2.1. Cấu trúc đại số và các phép toán

Cấu trúc đại số được xây dựng trên các khoảng cho phép thực hiện các phép toán phức tạp hơn so với các mô hình truyền thống. Các phép toán này bao gồm phép cộng, trừ, và các phép toán logic, giúp tăng cường khả năng tính toán trên các nhãn của otomat. Việc định nghĩa các quan hệ thứ tự trên khoảng cũng là một điểm nổi bật trong nghiên cứu này, giúp mở rộng khả năng ứng dụng của đại số khoảng trong các lĩnh vực khác nhau.

2.2. Ứng dụng trong thực tiễn

Các ứng dụng của đại số khoảng và otomat trong thực tiễn rất đa dạng. Một trong những ứng dụng quan trọng là trong việc xây dựng các giao thức bảo mật như Zero-Knowledge. Giao thức này đảm bảo tính riêng tư và bí mật của thông tin trong quá trình trao đổi. Ngoài ra, việc sử dụng otomat khoảng trong các bài toán tìm đường nhanh nhất và mô hình mạng ưu tiên cũng cho thấy tính ứng dụng cao của nghiên cứu này trong các hệ thống thực tế.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Đại số khoảng, otomat khoảng và một số ứng dụng" do nghiên cứu sinh Bùi Vũ Anh thực hiện năm 2015 tại Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, thuộc chuyên ngành Bảo đảm Toán học cho máy tính và hệ thống tính toán (mã số: 62 46 35 01), dưới sự hướng dẫn khoa học của cố PGS. TS Phan Trung Huy và TS Nguyễn Thị Hồng Minh.

Về tính cấp thiết và khoảng trống nghiên cứu, văn bản luận án chỉ ra rằng trong việc mô hình hóa các hệ thống thông tin bằng phương pháp hình thức, hai hướng tiếp cận chính là lý thuyết otomat và lý thuyết đại số. Đối với otomat cổ điển, các nghiên cứu gia tăng ràng buộc (như otomat thời gian, otomat mờ, otomat xác suất) chủ yếu bổ sung thông tin lên các cung và trạng thái để phục vụ việc kiểm tra điều kiện chuyển. Tuy nhiên, phép toán cơ bản trên các từ của otomat truyền thống chỉ là phép tích ghép (nối chuỗi ký hiệu), chưa chú trọng đến nội hàm cấu trúc của nhãn. Khi các nhãn không còn là một ký hiệu đơn lẻ mà là các phần tử mang giá trị định lượng, việc thực hiện các phép toán ngữ nghĩa trực tiếp trên nhãn chưa được phát triển đồng bộ. Cụ thể, các mô hình otomat có yếu tố khoảng trước đó chưa được trang bị một cấu trúc đại số hoàn chỉnh đi kèm các phép toán đại số để tính toán trên các khoảng thời gian.

Mục tiêu nghiên cứu của luận án được văn bản xác định cụ thể gồm 3 nội dung:

1. Nghiên cứu việc gán giá trị ràng buộc có dạng khoảng trên các cung của otomat ngoài các nhãn thông thường, cho phép thực hiện các tính toán trên nhãn khoảng. Xây dựng một cấu trúc đại số trên các khoảng và định nghĩa các quan hệ thứ tự trên khoảng nhằm phục vụ các ứng dụng khác nhau.
2. Kết hợp đại số khoảng với lý thuyết otomat Vào/Ra (Input/Output Automata - IOA) để đề xuất mô hình otomat khoảng, nghiên cứu các đặc trưng ngôn ngữ khoảng được đoán nhận, giải quyết hai bài toán lý thuyết nền tảng là đơn định hoá và tối tiểu hoá otomat khoảng.
3. Đề xuất các ứng dụng trong lý thuyết và thực tiễn sử dụng đại số khoảng và otomat khoảng làm công cụ mô hình, xây dựng thuật toán giải quyết các bài toán: thiết kế giao thức bảo mật Zero-Knowledge, tìm đường đi nhanh nhất trên mạng giao thông theo thời gian khoảng, giải bài toán đạt được trên mạng ưu tiên (Priority Network - PN), và lập lịch công việc động cho hệ thống máy tính ghép cụm.

Đối tượng nghiên cứu của luận án là cấu trúc đại số khoảng, các quan hệ thứ tự trên khoảng, mô hình otomat khoảng (kết hợp otomat Vào/Ra với đại số khoảng), ngôn ngữ khoảng, giao thức chứng thực Zero-Knowledge và các thuật toán tối ưu hóa trên đồ thị/lập lịch. Phạm vi nghiên cứu tập trung vào cơ sở toán học cho khoa học máy tính; các khoảng thời gian được xác định với các đầu mút thuộc tập số hữu tỷ hoặc số nguyên nhằm bảo đảm tính hữu hạn và tính dừng của các thuật toán; dữ liệu kiểm nghiệm và các mô hình bài toán ứng dụng được khảo sát trên không gian trạng thái rời rạc và mô phỏng thuật toán tính toán.

Tổng quan tài liệu và vị trí của luận án

Luận án điểm lại các công trình nghiên cứu tiền đề theo hai hướng tiếp cận chính:

Hướng tiếp cận	Tác giả và năm công bố	Công trình / Khái niệm tiêu biểu	Đặc điểm và mối liên hệ với luận án
Tiếp cận theo hướng otomat	Rajeev Alur & David L. Dill (1994)	Otomat thời gian (Timed Automata - TA)	Bổ sung các biến đồng hồ thực; độ phức tạp kiểm tra tính đạt được lớn: $n \cdot 2^{O(k \log(kc))}$.
	Nancy A. Lynch & Mark R. Tuttle (1987, 1989)	Otomat Vào/Ra (IO Automata)	Phân biệt hành động vào (input), ra (output) và nội tại (internal) để mô hình hóa hệ thống dạng hộp đen.
	Deepak D’Souza & P. S. Thiagarajan (1998)	Otomat khoảng (Interval Automata - IA)	Gán khoảng số thực lên cung; chứng minh ngôn ngữ sinh bởi IA là lớp con của ngôn ngữ sinh bởi TA nhưng chưa phân biệt nhãn IO.
	Đặng Văn Hùng & Bùi Vũ Anh (2005)	Otomat khoảng cho hệ thống nhúng	Xét ràng buộc khoảng có đầu mút nguyên; chưa xây dựng cấu trúc đại số và chưa nghiên cứu ngôn ngữ đoán nhận.
	Luca de Alfaro & Thomas A. Henzinger (2001)	Otomat giao diện (Interface Automata)	Phân quyền biến giao diện giữa các trạng thái cho hệ thống thành phần.
	Lotfi A. Zadeh; các tác giả khác	Otomat mờ, xác suất, trọng số, tế bào, $\diamond$-otomat	Ứng dụng trong nhận dạng mẫu, lý thuyết mã, nén ảnh số.
Tiếp cận theo hướng đại số	Robin Milner (1980, 1989)	CCS (Calculus of Communicating Systems)	Đại số quá trình định hướng cho các chương trình tương tranh.
	C. A. R. Hoare (1985)	CSP (Communicating Sequential Processes)	Đại số quá trình làm cơ sở cho ngôn ngữ OCCAM và các công cụ kiểm chứng (SPIN, UPPAAL, HOL Light).
	C. A. R. Hoare & He Jifeng (1998)	UTP (Unifying Theories of Programming)	Bộ ký pháp hợp nhất mô tả cả tiến trình song song và chương trình không kết thúc.
Giao thức Zero-Knowledge	S. Goldwasser, S. Micali, C. Rackoff (1985)	Giao thức chứng minh Zero-Knowledge	Xác lập 3 điều kiện: Completeness, Soundness, Zero-Knowledge.
	Lior Malka (2011); O. Goldreich & L. Teichner (2014)	Perfect và Super-Perfect Zero-Knowledge	Chuẩn hóa mức độ rò rỉ tri thức bằng 0 và thời gian sinh mô phỏng tuyến tính.
	James F. Allen (1983)	13 quan hệ thời gian khoảng	Suy luận định tính thứ tự tuyến tính giữa hai khoảng thời gian.

Khoảng trống nghiên cứu được luận án lựa chọn giải quyết bao gồm:

• Khắc phục tình trạng thiếu một cấu trúc đại số hoàn chỉnh trên tập các khoảng để có thể thực hiện tính toán ngữ nghĩa khi ghép chuỗi các hành động liên tiếp.
• Kết hợp đại số khoảng với mô hình otomat Vào/Ra nhằm mô tả các hệ thống dạng hộp đen có gắn thời gian thực với độ phức tạp tính toán thấp hơn so với otomat thời gian của Alur và Dill.
• Thiết lập các thuật toán chuyển đổi hình thức: đơn định hoá và tối tiểu hoá otomat khoảng dựa trên ngôn ngữ khoảng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Về cơ sở lý thuyết, luận án sử dụng các cấu trúc toán học nền tảng:

• Lý thuyết tập hợp và đại số trừu tượng: Quan hệ hai ngôi, quan hệ tương đương, phân hoạch tập hợp, nửa nhóm, vị nhóm, vị nhóm giao hoán, dàn đại số.
• Lý thuyết ngôn ngữ hình thức và otomat cổ điển: Bảng chữ cái, từ, từ rỗng $\Lambda$, các phép toán ngôn ngữ (tích ghép, đối xứng gương, hợp, giao, phần bù, lặp Kleene, lặp cắt, thương trái và thương phải). Định lý tương đương giữa otomat hữu hạn đơn định (DFA) và otomat hữu hạn đa định (NFA) của Rabin-Scott. Định lý Myhill-Nerode về mối liên hệ giữa ngôn ngữ chính quy và quan hệ tương đương bất biến phải có chỉ số hữu hạn; quan hệ $k$-tương đương giữa các trạng thái.
• Lý thuyết otomat Vào/Ra (IOA) và otomat thời gian (TA).
• Lý thuyết mật mã học và giao thức Zero-Knowledge với 3 tính chất bắt buộc: tính đầy đủ (Completeness), tính đúng đắn (Soundness), và tính không để lộ tri thức (Zero-Knowledge).

Về phương pháp nghiên cứu, luận án sử dụng hướng tiếp cận lý thuyết toán học hình thức kết hợp kiểm chứng thuật toán rời rạc:

• Phương pháp diễn dịch và quy nạp toán học: Sử dụng quy nạp theo độ dài từ và số lượng khoảng để chứng minh các định lý về tính kết hợp yếu của phép tích khoảng, tính duy nhất của kết quả tích dãy khoảng xác định, và sự bảo toàn ngôn ngữ khi biến đổi otomat.
• Phương pháp kiểm tra vét cạn rời rạc bằng chương trình máy tính: Thiết lập đoạn mã giả duyệt qua 14 điểm mút nguyên đại diện để kiểm tra toàn bộ 16 cấu hình tổ hợp thứ tự của tích ba khoảng, khẳng định tính đúng đắn của định lý kết hợp yếu trên vị nhóm khoảng.
• Kỹ thuật phân hoạch và rút gọn đồ thị: Thuật toán tách cung, ghép cung trong đơn định hóa và thuật toán tinh chỉnh phân hoạch lớp tương đương để tối tiểu hóa otomat khoảng.

Về nguồn tư liệu và dữ liệu, luận án kế thừa các định nghĩa chuẩn trong tài liệu chuyên khảo về lý thuyết tính toán của Hopcroft, Ullman, Hoare, Milner; hệ thống ký hiệu viết tắt từ các dự án quốc tế như RAISE (ESPRIT II LaCoS), công cụ SPIN (Bell Labs), UPPAAL (Đại học Uppsala và Đại học Aalborg). Dữ liệu tính toán trong các ví dụ minh họa và thuật toán lập lịch, tìm đường được xây dựng trên tập số thực không âm $\mathbb{R}^+$ và tập số hữu tỷ $\mathbb{Q}$.

Nội dung chính theo từng chương

Chương 1: Một số khái niệm cơ sở

Chương 1 hệ thống hóa các kiến thức toán học nền tảng nhằm chuẩn bị công cụ cho việc mở rộng mô hình ở các chương sau:

• Khảo sát các tính chất của quan hệ hai ngôi trên tập hợp: phản xạ, đối xứng, phản đối xứng, bắc cầu, quan hệ tương đương và quan hệ thứ tự (bộ phận, toàn phần, dàn). Định nghĩa phép toán hai ngôi, phần tử đơn vị trái, đơn vị phải, phần tử trung lập; định nghĩa nửa nhóm, vị nhóm và vị nhóm giao hoán.
• Định nghĩa hình thức về bảng chữ cái $\Sigma$, từ, từ rỗng $\Lambda$, tập các từ $\Sigma^$, ngôn ngữ không chứa từ rỗng $\Sigma^+$. Thiết lập công thức cho các phép toán trên ngôn ngữ: phép tích ghép, phép lấy đối xứng gương, phép hợp, phép giao, phép lấy phần bù $C(L) = \Sigma^ - L$, phép lặp Kleene $L^*$, phép lặp cắt $L^+$, cùng phép chia thương trái $L_2 \setminus L_1$ và thương phải $L_1 / L_2$.
• Trình bày mô hình otomat hữu hạn đơn định $A = (S, \Sigma, s_0, \delta, F)$ và mở rộng hàm chuyển $\hat{\delta}$ cho từ; định nghĩa ngôn ngữ chính quy $L(A)$. Khảo sát otomat hữu hạn đa định $M = (S, \Sigma, \delta, s_0, F)$ với $\delta: S \times \Sigma \to 2^S$. Trình bày chứng minh Định lý Rabin-Scott khẳng định lớp ngôn ngữ đoán nhận bởi otomat đơn định và đa định là trùng nhau, đi kèm thuật toán đơn định hóa với độ phức tạp trường hợp xấu nhất là $2^{|S|} \times |\Sigma|$.
• Trình bày định lý xác định ngôn ngữ đoán nhận là rỗng, hữu hạn hay vô hạn dựa trên việc kiểm tra từ có độ dài nhỏ hơn $n$ hoặc trong đoạn $[n, 2n)$. Khảo sát Định lý Myhill-Nerode, định nghĩa quan hệ tương đương bất biến phải $R_L$ và quan hệ $k$-tương đương giữa các trạng thái ($p \sim_k q$). Trình bày thuật toán tối tiểu hóa otomat bằng kỹ thuật xây dựng dãy phân hoạch mịn dần $\pi_0, \pi_1, \dots, \pi_k$ cho đến khi $\pi_k = \pi_{k+1}$.

Chương 2: Cấu trúc đại số khoảng

Chương 2 là nội dung lý thuyết trọng tâm của luận án, xây dựng cấu trúc đại số trên tập các khoảng:

• Định nghĩa tập các khoảng $D = {\emptyset, \varepsilon} \cup {[l, u], [l, u), (l, u], (l, u) \mid l, u \in \mathbb{Q}}$, trong đó $\varepsilon = [0, +\infty)$ đóng vai trò là phần tử đơn vị và $\emptyset$ là khoảng rỗng. Luận án định nghĩa 4 phép toán cơ bản trên $D$:
  1. Phép giao khoảng: $d_1 \cap d_2 = {t \in \mathbb{R}^+ \mid t \in d_1 \text{ và } t \in d_2}$.
  2. Phép hiệu liên tục: $$d_1 \setminus_m d_2 = \begin{cases} d_1 \setminus d_2 & \text{nếu } d_1 \neq \emptyset, \max{l_1, l_2} \le \min{u_1, u_2} \text{ và } d_2 \not\subseteq d_1 \ \emptyset & \text{ngược lại} \end{cases}$$
  3. Phép hợp liên tục: $$d_1 \sqcup d_2 = \begin{cases} [\min{l_1, l_2}, \max{u_1, u_2}] & \text{nếu } d_1 \cap d_2 \neq \emptyset \ \emptyset & \text{ngược lại} \end{cases}$$
  4. Phép tích khoảng: $$d_1 \otimes d_2 = \begin{cases} d_1 & \text{nếu } d_2 = \varepsilon \ d_2 & \text{nếu } d_1 = \varepsilon \ [l_1, u_2] & \text{nếu } d_1 \cap d_2 \neq \emptyset \ \emptyset & \text{ngược lại} \end{cases}$$
• Chứng minh các tính chất của phép tích khoảng: Phép tích đóng trong $D$, không giao hoán. Phép tích có tính kết hợp yếu (weakly associative): với $d_1, d_2, d_3 \in D$, nếu cả $d_1 \otimes (d_2 \otimes d_3)$ và $(d_1 \otimes d_2) \otimes d_3$ đều xác định (khác $\emptyset$) thì chúng bằng nhau. Hệ quả chỉ ra $(D, \otimes)$ là một vị nhóm yếu. Văn bản đưa ra thuật toán kiểm tra tính kết hợp dựa trên tập 14 điểm mút số nguyên đại diện. Định lý 2.2 chứng minh rằng với một dãy khoảng $d_1, d_2, \dots, d_n$, nếu tích của dãy xác định theo hai cách kết hợp dấu ngoặc $\delta_1$ và $\delta_2$ thì hai kết quả đó hoàn toàn trùng nhau và bằng $[l_1, u_n]$.
• Xây dựng hệ thống quan hệ thứ tự trên $D$: thứ tự biên trái $<l$, biên phải $<r$, độ rộng $<b$, các thứ tự kết hợp $<{lr}, <{rl}, <{bl}, <{br}, <{lb}, <_{rb}$ và thứ tự trung vị ưu tiên trái $<_m$: $$d_1 <_m d_2 \iff \left(\frac{l_1 + u_1}{2} < \frac{l_2 + u_2}{2}\right) \lor \left(\frac{l_1 + u_1}{2} = \frac{l_2 + u_2}{2} \land l_1 \le l_2\right)$$ Chứng minh định lý khẳng định $\le_m$ là quan hệ thứ tự toàn phần và $(D, \le_m)$ là một dàn đại số. So sánh với 13 quan hệ khoảng của James F. Allen.
• Ứng dụng đại số khoảng vào mật mã học: Thiết lập thuật toán sinh dãy khoảng từ một khóa nhị phân cho trước dựa trên quy tắc chia khoảng kết hợp trái và kết hợp phải. Xây dựng giao thức Zero-Knowledge kiểm chứng một phía sử dụng tích khoảng, phân tích ví dụ hang động hình xuyến và chứng minh xác suất người kiểm chứng không phát hiện được sự gian lận giảm theo hàm số mũ $(1/2)^n$ sau $n$ vòng tương tác.

Chương 3: Ngôn ngữ và otomat khoảng

Chương 3 phát triển mô hình otomat khoảng và lý thuyết ngôn ngữ đi kèm:

• Định nghĩa $d$-xâu, $d$-từ là dãy các cặp ký hiệu gồm nhãn hành động thuộc bảng chữ cái và nhãn thời gian là một khoảng thuộc $D$. Tích của hai $d$-xâu được thực hiện bằng cách ghép nhãn hành động và lấy tích khoảng của các nhãn thời gian tương ứng. Định nghĩa $d$-ngôn ngữ và xây dựng các phép toán đóng trên $d$-ngôn ngữ: phép hợp, phép giao, phép tích khoảng, phép chia thương trái và thương phải.
• Xây dựng mô hình otomat khoảng (Interval Automaton - ký hiệu DA), kết hợp các đặc tính của otomat Vào/Ra với nhãn chuyển trạng thái mang thông tin khoảng đại số. Phân loại trạng thái di chuyển được và trạng thái treo theo các ngữ nghĩa thực thi. Định nghĩa otomat khoảng đơn định và otomat khoảng đa định.
• Giải quyết bài toán đơn định hoá otomat khoảng: Do tính chất đa định trong otomat khoảng xuất hiện không chỉ từ nhãn hành động mà còn từ sự giao nhau của các khoảng thời gian trên các cung xuất phát từ cùng một trạng thái, luận án đề xuất thuật toán đơn định hóa thông qua hai kỹ thuật: phép ghép cung (khi các cung có cùng hành động và điều kiện khoảng thỏa mãn hợp liên tục) và phép tách cung (phân rã khoảng thành các khoảng con không giao nhau để loại bỏ tính đa định).
• Giải quyết bài toán tối tiểu hoá otomat khoảng: Xây dựng quy trình rút gọn trạng thái thông qua việc loại bỏ các trạng thái không đạt được từ trạng thái khởi đầu, loại bỏ các trạng thái treo không thể dẫn tới trạng thái kết thúc, và áp dụng quan hệ tương đương mở rộng trên các trạng thái có cùng hành vi đoán nhận $d$-từ để gộp các trạng thái tương đương.

Chương 4: Một số ứng dụng

Chương 4 vận dụng các kết quả lý thuyết của Chương 2 và Chương 3 vào việc giải quyết 3 bài toán kỹ thuật:

• Bài toán tìm $d$-đường đi nhanh nhất trên mạng giao thông: Mô hình hóa mạng giao thông thành đồ thị có trọng số trên các cung là các khoảng thời gian di chuyển thuộc $D$. Đề xuất thuật toán tìm đường đi từ nút nguồn $s$ đến nút đích $t$ sao cho tích khoảng dọc theo đường đi là xác định và đạt giá trị nhỏ nhất theo quan hệ thứ tự trung vị $\le_m$.
• Mô hình mạng ưu tiên (Priority Network - PN): Định nghĩa cấu trúc mạng ưu tiên bằng otomat khoảng, trong đó các ràng buộc ưu tiên giữa các tiến trình được biểu diễn thông qua các ràng buộc nút và ràng buộc cung. Thiết lập thuật toán chuyển đổi tương đương giữa ràng buộc cung và ràng buộc nút. Giải quyết bài toán đạt được trên mạng ưu tiên bằng cách chuyển đổi otomat khoảng sang cây suy dẫn để kiểm tra tính khả thi của việc đạt tới các trạng thái mục tiêu tại một thời điểm $t$ cụ thể.
• Lập lịch công việc cho hệ thống máy tính ghép cụm: Mô hình hóa các nút tính toán và hàng đợi công việc bằng otomat khoảng. Luận án đề xuất thuật toán lập lịch công việc tổng quát theo phương pháp động: trong quá trình hệ thống đang vận hành, căn cứ vào thời gian hoàn thành thực tế được ước lượng dưới dạng khoảng, thuật toán thực hiện tái lập lịch và phân phối lại công việc giữa các nút tính toán, sử dụng thứ tự toàn phần $\le_m$ trên dàn khoảng $(D, \le_m)$ để tối ưu hóa thời gian hoàn thành của toàn hệ thống.

Kết quả và những đóng góp mới

Văn bản luận án tự xác định các đóng góp mới về mặt lý thuyết và thực tiễn như sau:

• Xây dựng cấu trúc đại số khoảng $(D, \otimes)$ với phần tử đơn vị $\varepsilon = [0, +\infty)$, chứng minh tính chất kết hợp yếu và khẳng định $(D, \otimes)$ là một vị nhóm yếu. Chứng minh tính duy nhất của kết quả tích một dãy khoảng xác định bất kể thứ tự ưu tiên kết hợp dấu ngoặc.
• Thiết lập hệ thống các quan hệ thứ tự trên tập các khoảng, chứng minh quan hệ thứ tự trung vị $\le_m$ là quan hệ thứ tự toàn phần và $(D, \le_m)$ lập thành một dàn đại số.
• Đề xuất thuật toán sinh dãy khoảng từ khóa nhị phân và thiết kế giao thức chứng thực Zero-Knowledge kiểm chứng một phía sử dụng đại số khoảng, bảo đảm độ an toàn và tính riêng tư với thời gian triển khai thấp.
• Đề xuất mô hình otomat khoảng là sự kết hợp giữa lý thuyết otomat cổ điển, otomat Vào/Ra (IOA) với cấu trúc đại số khoảng. Xây dựng lý thuyết về $d$-ngôn ngữ và giải quyết thành công hai bài toán lý thuyết cơ bản: thuật toán đơn định hóa (thông qua kỹ thuật ghép cung và tách cung) và thuật toán tối tiểu hóa otomat khoảng.
• Đề xuất các giải pháp ứng dụng thực tiễn: thuật toán tìm $d$-đường đi nhanh nhất theo thời gian khoảng trên mạng giao thông; thuật toán giải bài toán đạt được trên mô hình mạng ưu tiên; thuật toán lập lịch công việc động và tái lập lịch cho hệ thống máy tính ghép cụm dựa trên thứ tự trung vị $\le_m$.

Về kiến nghị và giải pháp đề xuất, tác giả khuyến nghị sử dụng mô hình otomat khoảng làm giải pháp thay thế cho otomat thời gian trong các hệ thống thời gian thực có cấu trúc thành phần hoặc dạng hộp đen nhằm giảm độ phức tạp tính toán của các bài toán kiểm chứng mô hình từ hàm mũ cao xuống mức độ tính toán xử lý được trên đồ thị rời rạc.

Hạn chế và hướng nghiên cứu tiếp

Căn cứ vào nội dung và phạm vi nghiên cứu được trình bày trong văn bản:

• Về phạm vi lý thuyết: Các đầu mút của khoảng trong cấu trúc đại số $D$ chủ yếu được giới hạn trên tập số hữu tỷ $\mathbb{Q}$ hoặc số nguyên để bảo đảm tính đóng hữu hạn và tính kết thúc của các thuật toán. Việc mở rộng hoàn toàn sang tập số thực $\mathbb{R}$ chưa được tối ưu hóa do không làm tăng hiệu quả tính toán thực tế và gặp khó khăn trong việc kế thừa các kết quả kiểm chứng hình thức.
• Về tính chất đại số: Phép tích khoảng không thỏa mãn luật kết hợp hoàn toàn mà chỉ đạt tính kết hợp yếu (chỉ bằng nhau khi các tích đều xác định khác rỗng), do đó cấu trúc $(D, \otimes)$ dừng lại ở mức vị nhóm yếu chứ không phải là một nhóm hay vị nhóm thông thường.
• Về triển khai ứng dụng: Luận án mới dừng lại ở việc đề xuất mô hình toán học, thiết kế thuật toán và chứng minh tính đúng đắn trên mô hình lý thuyết hoặc các ví dụ mô phỏng; văn bản chưa công bố việc đóng gói các thuật toán này thành một bộ công cụ kiểm chứng phần mềm tự động hóa hoàn chỉnh (như các công cụ SPIN hay UPPAAL). Các hướng nghiên cứu tiếp được xác định là hoàn thiện công cụ tự động kiểm chứng và mở rộng lớp bài toán tối ưu hóa đa mục tiêu trên mạng otomat khoảng.

Giá trị tham khảo

Luận án có giá trị tham khảo cụ thể đối với các nhóm đối tượng học thuật và ứng dụng:

• Nghiên cứu sinh và học viên cao học chuyên ngành Bảo đảm toán học cho máy tính, Khoa học máy tính và Toán ứng dụng: Có thể tham khảo phương pháp xây dựng cấu trúc đại số trên các đối tượng hình thức tại Chương 2, cùng kỹ thuật xử lý ngôn ngữ hình thức và thuật toán biến đổi otomat (đơn định hóa, tối tiểu hóa) tại Chương 3.
• Giảng viên và nhà nghiên cứu trong lĩnh vực phương pháp hình thức (Formal Methods): Luận án cung cấp tài liệu tham khảo chi tiết về cách tiếp cận kết hợp giữa đại số quá trình và otomat chuyển trạng thái, bổ sung thêm một công cụ mô hình hóa hệ thời gian thực bên cạnh otomat thời gian cổ điển.
• Kỹ sư phát triển hệ thống phân tán, an toàn thông tin và tính toán hiệu năng cao: Có thể tham khảo thuật toán thiết kế giao thức Zero-Knowledge sử dụng khóa nhị phân và tích khoảng (Chương 2), thuật toán tìm đường trên mạng thông tin và thuật toán lập lịch động cho hệ thống máy tính cụm (Cluster Computing) dựa trên quan hệ thứ tự trung vị (Chương 4).

Câu hỏi thường gặp

Phép tích khoảng trong luận án được định nghĩa như thế nào và tại sao $(D, \otimes)$ chỉ là một vị nhóm yếu?

Phép tích của hai khoảng $d_1 = [l_1, u_1]$ và $d_2 = [l_2, u_2]$ trong tập $D$ được định nghĩa bằng $[l_1, u_2]$ nếu $d_1 \cap d_2 \neq \emptyset$; bằng $d_1$ nếu $d_2 = \varepsilon$; bằng $d_2$ nếu $d_1 = \varepsilon$; và bằng $\emptyset$ (không xác định) nếu $d_1 \cap d_2 = \emptyset$. Phép tích này có phần tử đơn vị là $\varepsilon = [0, +\infty)$ nhưng không có tính kết hợp hoàn toàn trên toàn bộ tập $D$ vì tồn tại các trường hợp tích theo cách nhóm ngoặc trái xác định nhưng nhóm ngoặc phải không xác định (hoặc ngược lại). Do tính kết hợp chỉ xảy ra khi kết quả tích theo cả hai cách đều khác rỗng, nên phép tích chỉ có tính kết hợp yếu và cấu trúc $(D, \otimes)$ được xác định là một vị nhóm yếu.

Quan hệ thứ tự trung vị ưu tiên trái $\le_m$ có ý nghĩa gì và tại sao nó tạo thành một dàn?

Quan hệ thứ tự trung vị $\le_m$ so sánh hai khoảng dựa trên điểm giữa (trung vị) của chúng: khoảng nào có giá trị trung bình cộng hai đầu mút nhỏ hơn sẽ nhỏ hơn; nếu trung vị bằng nhau thì khoảng nào có biên trái nhỏ hơn sẽ nhỏ hơn. Về mặt xác suất thực tế, nếu thời điểm kết thúc công việc phân bố đều trong khoảng thời gian cho phép thì khoảng có trung vị nhỏ hơn phản ánh khả năng hoàn thành sớm hơn. Luận án chứng minh quan hệ này thỏa mãn đầy đủ các tính chất phản xạ, phản đối xứng, bắc cầu và là quan hệ thứ tự toàn phần (mọi cặp khoảng đều so sánh được với nhau), do đó $(D, \le_m)$ tạo thành một dàn đại số.

Điểm khác biệt cơ bản giữa otomat khoảng trong luận án với otomat thời gian của Alur và Dill là gì?

Otomat thời gian của Alur và Dill (1994) sử dụng các biến đồng hồ thực chạy liên tục và độc lập để đặt điều kiện chuyển trạng thái, dẫn đến không gian trạng thái vô hạn và độ phức tạp kiểm tra tính đạt được rất lớn ($n \cdot 2^{O(k \log(kc))}$). Ngược lại, otomat khoảng trong luận án gán trực tiếp các nhãn khoảng thuộc cấu trúc đại số $D$ lên các cung chuyển trạng thái và kết hợp với cơ chế phân loại nhãn Vào/Ra của otomat IO. Nhờ đó, mô hình này cho phép thực hiện các phép toán đại số trực tiếp trên nhãn thời gian và triển khai các thuật toán kiểm tra tính đạt được, đơn định hóa, tối tiểu hóa với độ phức tạp tính toán thấp hơn nhiều so với otomat thời gian.

Giao thức Zero-Knowledge trong luận án sử dụng cấu trúc đại số khoảng như thế nào?

Luận án sử dụng một khóa nhị phân chọn trước (chuỗi các bit 0 và 1) để điều khiển quy tắc chia khoảng (kết hợp trái hoặc kết hợp phải) nhằm sinh ra một dãy các khoảng xác định. Người chứng minh sử dụng dãy khoảng này để thực hiện phép tích khoảng bí mật. Trong các vòng tương tác kiểm chứng, người kiểm chứng đưa ra các yêu cầu ngẫu nhiên; nếu người chứng minh thực sự sở hữu khóa bí mật, người đó sẽ luôn cung cấp được cách kết hợp khoảng để phép tích xác định. Xác suất một người không có khóa đánh lừa được người kiểm chứng trung thực giảm dần theo hàm số mũ $(1/2)^n$ sau $n$ lần kiểm tra.

Thuật toán lập lịch công việc cho máy tính ghép cụm trong Chương 4 vận hành theo nguyên lý nào?

Thuật toán được xây dựng theo cơ chế lập lịch động và tái lập lịch trong thời gian thực. Thời gian thực thi của mỗi công việc trên các nút tính toán được mô hình hóa bằng các khoảng thời gian thay vì các giá trị điểm cố định. Trong quá trình hệ thống hoạt động, căn cứ vào trạng thái tải của các nút và thời gian hoàn thành ước lượng, thuật toán sử dụng quan hệ thứ tự toàn phần $\le_m$ trên dàn khoảng $(D, \le_m)$ để liên tục so sánh, lựa chọn công việc có độ ưu tiên hoàn thành sớm hơn nhằm chia sẻ và phân bổ lại công việc giữa các nút tính toán trong cụm.

Kết luận

Luận án "Đại số khoảng, otomat khoảng và một số ứng dụng" của tác giả Bùi Vũ Anh đã xây dựng một cấu trúc đại số khoảng $(D, \otimes)$ đóng vai trò là một vị nhóm yếu và thiết lập dàn thứ tự toàn phần $(D, \le_m)$. Trên cơ sở đại số này, luận án đề xuất mô hình otomat khoảng kết hợp cơ chế Vào/Ra, thiết lập lý thuyết ngôn ngữ khoảng và giải quyết trọn vẹn hai bài toán hình thức nền tảng là đơn định hóa và tối tiểu hóa otomat. Các kết quả lý thuyết được vận dụng thành công vào việc xây dựng giao thức bảo mật Zero-Knowledge, thuật toán tìm đường đi theo thời gian khoảng trên mạng giao thông, kiểm tra tính đạt được trên mạng ưu tiên và thuật toán lập lịch động cho hệ thống máy tính ghép cụm. Toàn bộ công trình thể hiện hướng tiếp cận kết hợp chặt chẽ giữa đại số trừu tượng, lý thuyết otomat hình thức và thuật toán tối ưu hóa trong bảo đảm toán học cho máy tính.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 MỘT SỐ KHÁI NIỆM CƠ SỞ Chương này trình bày các khái niệm cơ sở sẽ được sử dụng và kế thừa trong luận án như quan hệ hai ngôi, quan hệ thứ tự [3], otomat, ngôn ngữ, các phép toán trên ngôn ngữ và thuật toán trên otomat truyền thống [25]. Những khái niệm này sẽ được định nghĩa mở rộng cho phù hợp với mô hình otomat khoảng và phát triển các thuật toán tương ứng cũng như các ứng dụng trên mô hình otomat khoảng trong các chương sau của luận án. Quan hệ hai ngôi Định nghĩa 1. Giả sử X và Y là những tập hợp.

Một quan hệ hai ngôi từ X đến Y là một bộ phận R của tích Đề các X × Y, tức là R ⊆ X × Y. Với hai phần tử a ∈ X và b ∈ Y, ta nói a có quan hệ R với b nếu và chỉ nếu cặp ( a, b) ∈ R. Ta viết aRb. Cho quan hệ hai ngôi R từ X đến X (gọi là quan hệ hai ngôi trên X).

- Quan hệ R là phản xạ nếu ∀ a ∈ X : aRa. - Quan hệ R là đối xứng nếu ∀ a, b ∈ X, aRb ⇒ bRa. Quan hệ R là phản đối xứng nếu ∀ a, b ∈ X : aRb, bRa ⇒ a = b. - Quan hệ R là bắc cầu nếu ∀ a, b, c ∈ X : aRb, bRc ⇒ aRc.

- Quan hệ R là tương đương nếu R là phản xạ, đối xứng và bắc cầu. Khi đó R thường được ký hiệu là ∼. - Quan hệ R là quan hệ thứ tự nếu R là phản xạ, phản đối xứng và bắc cầu.1: Ánh xạ Nếu R là quan hệ thứ tự và ∀ a, b ∈ X : aRb hoặc bRa thì R là quan hệ thứ tự đầy đủ (toàn phần), trái lại thì nó chỉ là quan hệ thứ tự bộ phận. Nếu R là quan hệ thứ tự thì nó thường được ký hiệu là ≤.

Người ta viết a < b nghĩa là a ≤ b và a 6= b để thể hiện quan hệ thứ tự chặt. Tập S với quan hệ thứ tự ≤ mà với mọi phần tử của S đều có thể so sánh được với nhau thì S được gọi là một dàn theo quan hệ ≤. Để phục vụ cho việc thực hiện các tính toán trên tập hợp, ta định nghĩa các khái niệm ánh xạ và phép toán như sau: Định nghĩa 1. [2, 3] Giả sử X và Y là những tập hợp và f là một quan hệ hai ngôi trên tích Đề các X × Y.

Khi đó f được gọi là một ánh xạ nếu Dom( f ) = X. Lúc đó ta nói đã xác định một ánh xạ f từ X vào Y, viết là f : X → Y và phần tử y ký hiệu là f ( x ) lấy từ cặp ( x, y) ∈ f. Ta gọi phép toán hai ngôi (hay gọi tắt là phép toán) trên tập X là một ánh xạ f : X × X → X. Giá trị f ( x, y) của f tại ( x, y) được gọi là cái hợp thành của x và y.

Cái hợp thành của x và y thường được ký hiệu bằng cách viết x và y theo một thứ tự nhất định với một dấu đặc trưng phép toán đặt ở giữa x và y. Trong các dấu hay dùng nhiều nhất là + (viết theo lối cộng) và. Khi viết theo lối nhân, người ta thường bỏ qua dấu ., xy được hiểu là x.y nếu không gây nhầm lẫn. Trong chương này, nếu x, y ∈ S và S được trang bị phép toán hai ngôi viết theo lối nhân thì dấu phép toán cũng sẽ bị bỏ qua.

- Quan hệ = (bằng) trên tập số nguyên Z là quan hệ phản xạ, đối xứng và bắc cầu nên nó là quan hệ tương đương. - Quan hệ ≤ trên tập số nguyên Z là quan hệ bắc cầu vì ∀ a, b, c ∈ Z, a ≤ b, b ≤ c thì a ≤ c; phản đối xứng vì a ≤ b, b ≤ a suy ra a = b. Do a ≤ a là đúng nên ≤ phản xạ, đồng thời ≤ cũng là một quan hệ thứ tự đầy đủ do với ∀ a, b ∈ Z, ta đều có a ≤ b (đọc là a nhỏ hơn b) hoặc b ≤ a (đọc là b nhỏ hơn a). - Do mọi phần tử trong Z đều so sánh được theo quan hệ ≤ nên (Z, ≤) là một dàn.

Một tính chất quan trọng của quan hệ tương đương xác định trên một tập là nó chia tập đó thành các lớp tương đương. Lớp tương đương này gồm các tập khác rỗng, rời nhau và trong mỗi tập đó chỉ gồm các phần tử có quan hệ tương đương với nhau, đồng thời chúng không có quan hệ tương đương với các phần tử ở các tập khác (còn gọi là một phân hoạch). Nếu R là một quan hệ tương đương trên X và a ∈ X thì tập hợp C ( a) = { x ∈ X | xRa} được gọi là lớp tương đương của a đối với quan hệ tương đương R. Nhận thấy: • Do R là phản xạ nên a ∈ C ( a), tức là C ( a) 6= ∅.

• Do R là bắc cầu nên x, y ∈ C ( a) thì xRy. • Do R là đối xứng nên x ∈ C ( a) và yRx thì y ∈ C ( a) hay ∀ a, b ∈ X, C ( a) = C (b) hoặc C ( a) ∩ C (b) = ∅. Quan hệ modulo m (chia lấy phần dư cho m), ký hiệu bởi ≡m , trên tập số nguyên Z là một quan hệ tương đương do: - Phản xạ: i ≡m i. Đồng thời ≡m tạo ra m lớp tương đương: [0] = {.

Chỉ số của một quan hệ tương đương trên một tập là số lớp tương đương trong phân hoạch mà quan hệ tương đương đó xác lập. Trong ví dụ về quan hệ ≡m , chỉ số của ≡m chính là m. Tuy nhiên, số lớp tương đương có thể vô hạn, chẳng hạn trong quan hệ = trên tập số nguyên Z, mỗi lớp tương đương chỉ gồm một phần tử, tức là ta có các lớp tương đương [0], [1], [2],. và do đó chỉ số của quan hệ tương đương này là vô hạn.

Nửa nhóm, vị nhóm Định nghĩa 1. Giả sử cho tập S và một phép toán hai ngôi. Một bộ phận A của S được gọi là ổn định (với phép toán hai ngôi trong S) nếu và chỉ nếu ∀ x, y ∈ A thì xy ∈ A. Ta dễ thấy tập các số tự nhiên N ổn định với phép toán ” + ” nhưng không ổn định với phép toán ” − ” các số tự nhiên.

Giả sử cho tập S và một phép toán hai ngôi. - Phần tử e ∈ S được gọi là đơn vị trái của phép toán hai ngôi nếu ex = x với mọi x ∈ S. - Phần tử e ∈ S được gọi là đơn vị phải của phép toán hai ngôi nếu xe = x với mọi x ∈ S. Nếu e vừa là đơn vị trái, vừa là đơn vị phải thì e được gọi là phần tử đơn vị (hay phần tử trung lập, phần tử trung hòa).

Mặc dù đều đề cập đến một phần tử đơn vị trong tập hợp nhưng người ta hay dùng thuật ngữ phần tử 0 để nói về phần tử đơn vị của phép cộng (viết theo lối cộng), còn người ta dùng thuật ngữ phần tử 1 để nói về phần tử đơn vị của phép nhân (viết theo lối nhân) để phân biệt chúng trong trường hợp một tập hợp được trang bị cả hai phép toán được viết theo lối cộng và lối nhân. Dễ nhận thấy số 0 là phần tử đơn vị của phép cộng, số 1 là phần tử đơn vị của phép nhân trong tập các số nguyên Z. Nếu một phép toán trong tập S có đơn vị trái e0 và đơn vị phải e00 thì e0 = e00. Phép toán hai ngôi trong một tập có nhiều nhất một phần tử đơn vị.

Một phép toán hai ngôi trong tập S là kết hợp nếu và chỉ nếu ( xy)z = x (yz) với mọi x, y, z ∈ S. Một tập hợp S cùng một phép toán kết hợp trong S được gọi là một nửa nhóm. Nửa nhóm S có phần tử đơn vị được gọi là một vị nhóm. Một nửa nhóm là giao hoán nếu phép toán của nó giao hoán.

Phép cộng cùng với tập Z là một nửa nhóm, đồng thời do có 0 là phần tử đơn vị nên (Z, +) chính là một vị nhóm. Phép cộng trong Z là giao hoán nên (Z, +) đồng thời là một vị nhóm giao hoán. Từ và ngôn ngữ Cho Σ là bảng hữu hạn các ký hiệu, gọi là bảng chữ cái. Một từ x thuộc bảng chữ cái Σ là một dãy các ký hiệu trong Σ viết liên tiếp nhau theo thứ tự từ trái sang phải.

Độ dài của từ x là số ký hiệu có trong x, được ký hiệu là | x |. Ta định nghĩa một từ đặc biệt, có độ dài là 0 gọi là từ rỗng, ký hiệu là ∧. Từ rỗng ∧ không được xây dựng từ bảng chữ cái nào và có thể được chứa trong ngôn ngữ xây dựng trên bảng chữ cái bất kỳ. Tập hợp tất cả các từ thuộc bảng chữ cái Σ được ký hiệu là Σ? và ngôn ngữ (xây dựng) trên bảng chữ cái Σ (hay ngôn ngữ của bảng chữ cái Σ) là một tập con của Σ?.

Ký hiệu Σ+ = Σ? − {∧} là ngôn ngữ xây dựng trên bảng chữ cái Σ nhưng không chứa từ rỗng. Mở rộng bảng chữ cái: Nếu L là một ngôn ngữ trên bảng chữ cái Σ thì nó cũng là ngôn ngữ trên bảng chữ cái chứa Σ nên ta luôn có thể giả thiết hai ngôn ngữ bất kỳ được xây dựng trên cùng bảng chữ cái để sử dụng cho các phép toán trên ngôn ngữ về sau. Ta có một số phép toán: 1. Tích ghép: - Nếu α là một từ trên bảng chữ cái Σ và ∧ là từ rỗng thì tích ghép của α và ∧ được định nghĩa là α • ∧ = ∧ • α = α.

bm là hai từ trên bảng chữ cái Σ thì tích ghép 21 z của α và β, ký hiệu là α • β được định nghĩa là a1 a2. Dễ nhận thấy phép tích ghép hai từ là không giao hoán, nhưng kết hợp và nó trung hòa với từ rỗng ∧. Tích ghép của hai ngôn ngữ L1 , L2 trên bảng chữ cái Σ, ký hiệu bởi L1 • L2 , là tập { x ∈ Σ∗ | ∃y ∈ L1 , z ∈ L2 , x = y • z}, trong đó y • z là phép tích ghép hai từ y và z.