Automata và Ngôn ngữ hình thức

Có bao giờ bạn tự hỏi rằng máy tính và ngôn ngữ lập trình được thiết kế như thế nào? Bài viết này đưa ra những khái niệm rất quan trọng trong việc thiết kế máy tính và ngôn ngữ lập trình.

Khái niệm cơ bản

Tất cả cả sản phẩm trong đời sống này đều phải trải qua một quá trình hình thành ý tưởng. Máy tính nói chung thì gồm 2 phần chính là phần cứng và phần mềm. Ý tưởng thiết kế của phần cứng đó chính là automata. Phần mềm được viết và dịch từ ngôn ngữ lập trình, và formal languages (ngôn ngữ hình thức) chính là ý tưởng thiết kế của nó.

Automata là gì?

Nói theo định nghĩa của từ điển tiếng Anh Oxford, automaton (số nhiều: automata/automatons) là máy tự động hay robot. Tuy nhiên, automata đang nói đến không phải là một chiếc máy thật sự. Automata là cách mô phỏng (model) một chiếc máy tính điện tử.

Máy tính điện tử gồm nhiều thành phần (features). Và automata chính là thứ mang chúng đến nhau. Automata là kiến trúc bao gồm những features không thể tách rời.

Automata nhận input, và cho ra output. Automata cũng có thể có bộ nhớ tạm thời (temporary storage). Automata đưa ra những quyết định (decision) để chuyển input thành output mong muốn.

Formal Languages là gì?

Hiện nay, có rất nhiều ngôn ngữ lập trình. Mỗi ngôn ngữ có thể mang tính chất khác nhau, sử dụng cho mục đích khác nhau. Có thể kể đến như C++, Java, Python, ... Trong quá khứ, việc xây dựng một trình biên dịch (compiler) là một công việc rất nặng nhọc, cần nguồn nhân lực và thời gian rất lớn. Tuy nhiên, hiện tại thì việc tạo ra một compiler đã đỡ nặng nhọc hơn rất nhiều.

Câu hỏi đặt ra là tại sao lại rút ngắn được thời gian và công sức? Và làm thế nào một ngôn ngữ lập trình được xây dựng?

Câu trả lời chính là sự hoàn thiện dần của lý thuyết về compiler. Mà ngôn ngữ hình thức (formal languages) đóng vai trò không nhỏ.

Formal Language là trừu tượng hóa (abstraction) của ngôn ngữ lập trình. Nó bao gồm biểu tượng (symbol), và quy luật kết hợp chúng lại để tạo thành câu (sentences). Hãy tạm tưởng tượng symbol là từ vựng, và sentences là câu trong tiếng Việt. Ngữ pháp (grammar) chính là quy luật để tạo câu từ những từ vựng.

Automata hữu hạn

DFA - Automata hữu hạn đơn định 

Một automata hữu hạn là một mô hình tính toán có kích thước hữu hạn cố định, không thể mở rộng trong suốt quá trình tính toán. 

Deterministic Finite Automata - DFA là một bộ gồm 5 thành phần như sau:

A = <Q, Σ, δ, q0, F>

Trong đó:

• Q là một tập hữu hạn khác rỗng, được gọi là tập các trạng thái
• Σ là một bảng chữ cái, được gọi là bảng chữ vào
• δ: D → Q, là một ánh xạ từ D vào Q, trong đó D ⊆ Q × Σ , được gọi là hàm chuyển trạng thái (hay hàm chuyển)
• q₀ ∈ Q, được gọi là trạng thái khởi đầu
• F ⊆ Q được gọi là tập các trạng thái kết thúc

NFA - Automata hữu hạn không đơn định

Nondeterministic Finite Automata - NFA là một bộ gồm 5 thành phần như sau:

A = <Q, Σ, δ, q0, F>

Trong đó:

• Q là một tập hữu hạn khác rỗng, được gọi là tập các trạng thái
• Σ là một bảng chữ cái, được gọi là bảng chữ vào
• q₀ ∈ Q, được gọi là trạng thái khởi đầu
• F ⊆ Q được gọi là tập các trạng thái kết thúc
• δ: Q × Σ → 2Q, ở đây 2Q (hay P(Q), là ký hiệu tập hợp các tập con của Q) gọi là ánh xạ chuyển.

Ngôn ngữ hình thức

RL - Ngôn ngữ chính quy 

Regular Language - RL được định nghĩa đệ quy như sau:

Cho bảng chữ cái Σ = {a₁, a₂, …, a_n}

1. Các ngôn ngữ ∅ và {a_i} (i = 1, 2, …, n) được gọi là các ngôn ngữ chính quy trên bảng chữ cái Σ.
2. Nếu R và S là hai ngôn ngữ chính quy trên bảng chữ cái Σ thì R ∪ S; R.S; R+ (hay S+ ) là các ngôn ngữ chính quy trên bảng chữ cái Σ.
3. Không có các ngôn ngữ chính quy nào khác trên bảng chữ cái Σ ngoài các ngôn ngữ chính quy được định nghĩa như trên.

RE - Biểu thức chính quy 

Regular Expression - RE được định nghĩa đệ quy như sau:

Cho bảng chữ cái Σ = {a₁, a₂, …, a_n}

1. ∅ và a (với a ∈ Σ) là các biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ ∅ và ngôn ngữ {a} 
2. Nếu r và s là hai biểu thức chính quy biểu diễn các ngôn ngữ chính quy R và S trên bảng chữ cái Σ thì:
   • r + s là biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ R ∪ S
   • r.s là biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ R.S
   • r + (hay s+) là biểu thức chính quy trên bảng chữ cái Σ biểu diễn ngôn ngữ R+ (hay S+)
3. Không có các biểu thức chính quy nào khác trên bảng chữ cái Σ ngoài các biểu thức chính quy được định nghĩa như trên.

PA - Automata đẩy xuống không đơn định

Pushdown Automata - PA hay Nondeterministic Pushdown Automata - NPA là một bộ 7 gồm:

M = <Q, Σ, Δ, δ, q0, z0, F>

Trong đó:

• Σ là tập hữu hạn khác rỗng các ký hiệu, gọi là bảng chữ cái vào, mỗi ký hiệu trong Σ gọi là ký hiệu vào
• Q là một tập hữu hạn, khác rỗng các trạng thái sao cho Σ ∩ Q = ∅
• Δ là tập hữu hạn khác rỗng các ký hiệu, gọi là bảng chữ cái ngăn xếp, mà các ký hiệu của nó gọi là các ký hiệu của ngăn xếp
• z₀ ∈ Δ là ký hiệu đặc biệt, gọi là ký hiệu đáy của ngăn xếp (còn gọi là ký hiệu đầu tiên của danh sách đẩy xuống)
• q₀ ∈ Q gọi là trạng thái khởi đầu
• F ⊂ Q gọi là tập các trạng thái kết thúc
• δ: Q × (Σ ∪ {ε})×Δ → 2^{(Q × Δ*)} gọi là hàm chuyển của M, 2^{(Q × Δ*)} là tập các tập con của Q×Δ*

Máy Turing 

Máy Turing đơn định là một bộ 7 gồm:

M = <Q, Σ, Δ, δ, s0, B, F>

Trong đó:

• Q là tập hữu hạn khác rỗng, gọi là tập các trạng thái
• Σ là một bảng chữ cái, gọi là bảng chữ vào hay bảng chữ trong
• Δ là một bảng chữ cái, Δ ⊃ Σ, gọi là bảng chữ ngoài hay tập các ký hiệu có thể ghi được lên băng
• δ: D → Q × Δ × {R, L}, với D ⊂ Q x Δ và R, L ∉ Q × Δ, gọi là ánh xạ chuyển
• s₀ ∈ Q, gọi là trạng thái khởi đầu
• B ∈ Δ \ Σ, gọi là ký hiệu trắng
• F ⊂ Q, gọi là tập các trạng thái kết thúc