Automata không có gì khó hiểu!

Automata không có gì khó hiểu!

Khi nhắc đến Lý thuyết tính toán (Theory of Computation) nghĩa là chúng ta đang bàn đến một nhánh của Khoa học máy tính (Coputer Science), lĩnh vực có thể giải quyết các vấn đề tính toán bằng cách sử dụng thuật toán (algorithm) và các mô hình tính toán (model of computation).

Khi cần xử lý một bài toán bằng máy tính, chúng ta sẽ tự hỏi rằng:

- Liệu vấn đề này có thể giải quyết bằng cách sử dụng thuật toán hay không?
- Nếu có thì làm thế nào để cách xử lý được tối ưu nhất?
- Và đáp án cho bài toán này là tuyệt đối hay tương đối?

Từ lý thuyết (theory), thuật toán (algorithm), đến mô hình (model) - hay gọi là tiến trình hoàn hảo để xử lý một vấn đề

Automata là gì?

Chúng ta đều biết, căn bản là máy tính không thể hiểu ngôn ngữ của con người. Bởi vì ngôn ngữ của con người khá phức tạp: từ các quy tắc ngữ pháp rối rắm, đến từ lóng, thổ ngữ địa phương... Và ngay cả một cụm từ, khi nó xuất hiện trong ngữ cảnh này có ý nghĩa khác, còn trong ngữ cảnh kia lại có hàm ý khác hẵn.

Tuy nhiên, sự phát triển của công nghệ, khoa học kỹ thuật đã buộc con người nhảy đến một bước tiến mới: nảy sinh nhu cầu giao tiếp với máy móc và điều khiển máy móc làm việc theo ý mình. Và để giải quyết nhu cầu này, việc tìm kiếm các giải pháp để tự động hóa quy trình sản xuất được nghiên cứu.

Lý thuyết Automata thuộc về trường phái ngôn ngữ hình thức (formal languages), nơi có nhiệm vụ nghiên cứu lĩnh vực lý thuyết về khoa học máy tính và tìm kiếm các giải pháp ứng dụng học máy. Ý tưởng về Automata dược khởi đầu từ 2 nhà thần kinh học người Mỹ Warren McCullough và Walter Pitts trong một bài báo, đại ý rằng, có khả năng mô mình hóa suy nghĩ của con người thành một quy trình và người máy có thể bắt chước theo quy trình này và trở nên thông minh hơn.

Về cơ bản, automata tương đối giống với Lý thyết tính toán (Theory of Computation) nhưng automate phải tuân theo một quy trình có quy tắc. Bên trong automate chứa đựng các thuật toán. Khi có dữ liệu đầu vào, thuật toán chịu trách nhiệm xử lý cho đến khi cung cấp đầu ra (giải pháp).

Nếu nói riêng về lĩnh vực xử lý ngôn ngữ tự nhiên: Automata là quá trình đi từ từ lý thuyết, thử nghiệm thuật toán, thu thập dữ liệu, xử lý dự liệu, đào tạo mô hình cho đến khi hoàn thành các model có thể đưa vào áp dụng trong cuộc sống, như Chat GPT, gọi là automata.

Vài thuật ngữ cơ bản về automata

Sự xuất hiện của lý thuyết Automata trở thành nền tảng quan trọng trong lĩnh vực học máy, giúp máy tính có khả năng tiếp nhận đầu vào, xử lý, chuyển trạng thái và chọn phương án tốt nhất để giải quyết vấn đề.

Trước khi tìm hiểu về 4 giải pháp (mô hình) tính toán automata, chúng ta điểm qua vài thuật ngữ cơ bản như sau: 

(1) Symbols (Các biểu tượng)

Symbols là các biểu tượng, đối tượng, hoặc ký tự, hoặc một hình ảnh nào đó.

Ví dụ: a, A, c, d, e, f

(2) States (Các trạng thái)

Automata luôn tập hợp các trạng thái, một trong những trạng thái của nó là trạng thái khởi động.

(3) Alphabets - Σ (Các ký tự)

Alphabets là một tập hợp của các biểu tượng, trạng thái của nó luôn là HỮU HẠN, viết tắt là Σ.

Ví dụ: 

∑ = {a, b}  
  
∑ = {A, B, C, D}  
  
∑ = {0, 1, 2}  
  
∑ = {0, 1, ....., 5]  
  
∑ = {#, β, Δ}  

(4) Strings (Chuỗi văn bản)

Là một tập hợp hữu hạn được lấy từ bảng chữ cái. Chuỗi String được ký hiệu là |w|.

ví dụ:
w = 010
Number of Sting |w| = 3  

(5) Language (Ngôn ngữ)

Ngôn ngữ là tập hợp của một chuỗi các từ được định sẵn và được nó chấp nhận. Nếu ngôn ngữ của automata là tập hợp "hello", "word" thì khi dữ liệu đầu vào là "hello" thì nó sẽ ở trạng thái chấp nhận, nếu ngôn ngữ ngoài phạm vi thì nó sẽ ở trạng thái từ chối.

(6) Rules (Các quy tắc)

Automate có một bộ quy tắc mô tả cách thức hoạt động của nó. Khi có dữ liệu đầu vào, nó sẽ phản ứng và cho biết trạng thái tiếp theo.

(7) States: Các trạng thái

Bây giờ chúng ta xem xét một ví dụ về đèn giao thông để làm rõ thế nào là <b>trạng thái máy học hữu</b> hạn.

3 trạng thái của đèn giao thông là:

Đèn đỏ: Phải dừng;
Đèn vàng: Chuẩn bị;
Đèn xanh: Phải đi;

Và rõ ràng là tại một thời điểm, đèn giao thông chỉ có một trạng thái duy nhất.

Bây giờ chúng ta xem xét ví dụ được triển khai bằng Java:

public class TrafficLightFSM {
    private enum State { RED, YELLOW, GREEN }
    
    private State currentState;
    
    public TrafficLightFSM() {
        currentState = State.RED; // Khởi tạo trạng thái ban đầu là Đỏ.
    }
    
    public void changeState() {
        switch (currentState) {
            case RED:
                System.out.println("Chuyển từ Đỏ sang Vàng.");
                currentState = State.YELLOW;
                break;
            case YELLOW:
                System.out.println("Chuyển từ Vàng sang Xanh.");
                currentState = State.GREEN;
                break;
            case GREEN:
                System.out.println("Chuyển từ Xanh sang Đỏ.");
                currentState = State.RED;
                break;
        }
    }
    
    public String getCurrentState() {
        return currentState.toString();
    }
    
    public static void main(String[] args) {
        TrafficLightFSM trafficLight = new TrafficLightFSM();
        
        for (int i = 0; i < 10; i++) {
            System.out.println("Trạng thái hiện tại: " + trafficLight.getCurrentState());
            trafficLight.changeState();
        }
    }
}