STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

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

    Giới thiệu về Automata và Ngôn ngữ hình thức.
    23/09/2014 06/09/2020 6 phút đọc
    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)
    • q0 ∈ 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
    • q0 ∈ 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 Σ = {a1, a2, …, an}

    1. Các ngôn ngữ ∅ và {ai} (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 Σ = {a1, a2, …, an}

    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
    • z0 ∈ Δ 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)
    • q0 ∈ 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
    • s0 ∈ 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
    0 Bình luận
    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021