Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Mở rộng lặp giới hạn {m,n} và đếm trạng thái Thompson

    Mở rộng bài toán dựng Thompson: ngoài ., |, * như quy tắc chuẩn (kí tự →(2,1)\to (2,1)→(2,1) trạng thái/dịch chuyển; nối tiếp →(s1+s2−1, t1+t2)\to (s_1+s_2-1,\ t_1+t_2)→(s1​+s2​−1, t1​+t2​); hội →(s1+s2+2, t1+t2+4)\to (s_1+s_2+2,\ t_1+t_2+4)→(s1​+s2​+2, t1​+t2​+4); lặp ∗→(s+2, t+4)* \to (s+2,\ t+4)∗→(s+2, t+4)), biểu thức còn có thể dùng toán tử lặp giới hạn hậu tố E{m}E\{m\}E{m}, E{m,}E\{m,\}E{m,}, E{m,n}E\{m,n\}E{m,n} áp dụng cho nhân tử EEE ngay trước nó (một kí tự đơn hoặc một biểu thức trong ngoặc), với ngữ nghĩa mở rộng (unroll) chuẩn:

    • E{m}=E⋅E⋯E⏟mE\{m\} = \underbrace{E\cdot E\cdots E}_{m}E{m}=mE⋅E⋯E​​ (nếu m=0m=0m=0, đây là biểu thức ε\varepsilonε: 111 trạng thái, 000 dịch chuyển).
    • E{m,}=E{m}⋅E∗E\{m,\} = E\{m\}\cdot E^{*}E{m,}=E{m}⋅E∗.
    • E{m,n}E\{m,n\}E{m,n} (với n≥mn\ge mn≥m hữu hạn) =E{m}⋅(E∣ε)⋯(E∣ε)⏟n−m= E\{m\}\cdot \underbrace{(E\mid\varepsilon)\cdots(E\mid\varepsilon)}_{n-m}=E{m}⋅n−m(E∣ε)⋯(E∣ε)​​.

    Văn phạm đầy đủ: kí tự a-z là kí tự đơn; . là nối tiếp (bắt buộc viết tường minh giữa hai nhân tử liên tiếp); | là hội; ( ) để nhóm; hậu tố của một nhân tử là * hoặc {m} / {m,} / {m,n} (m,nm,nm,n là số tự nhiên; có thể có nhiều hậu tố lặp liên tiếp áp lên cùng một nhân tử, ví dụ a{2}*).

    Hãy tính tổng số trạng thái và tổng số dịch chuyển của NFA sau khi đã mở rộng hết các lặp giới hạn rồi dựng Thompson theo đúng quy tắc trên.

    • Định dạng đầu vào:

      Một dòng duy nhất chứa biểu thức chính quy (không khoảng trắng, độ dài ≤150\le 150≤150, các số m,nm,nm,n trong {} không vượt quá 202020, hợp lệ theo văn phạm trên).

    • Định dạng đầu ra:

      Một dòng hai số nguyên: tổng số trạng thái và tổng số dịch chuyển.

      Ví dụ: với đầu vào a.b.c (không có lặp giới hạn), kết quả là 4 3; với a{3}, kết quả cũng là 4 3 (tương đương a.a.a).

    Ví dụ:

    Đầu vào:

    a.b{2,3}|(c|d){1,2}.e*

    Đầu ra:

    27 33

    Đầu vào:

    (a.b){0,3}

    Đầu ra:

    16 18

    Đang tải editor...