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] Đối sánh regex bằng đạo hàm Brzozowski

    Đạo hàm Brzozowski (Brzozowski derivative) là một kỹ thuật xây dựng động cơ regex không cần dựng tường minh NFA hay DFA: đạo hàm Dc(R)D_c(R)Dc​(R) của biểu thức RRR theo ký hiệu ccc là một biểu thức chính quy mô tả đúng phần còn lại cần khớp, sau khi giả sử ký hiệu đầu tiên đã đọc được là ccc. Một chuỗi w=c1c2…ckw = c_1 c_2 \ldots c_kw=c1​c2​…ck​ được RRR chấp nhận khi và chỉ khi biểu thức Dck(…Dc1(R)…)D_{c_k}(\ldots D_{c_1}(R) \ldots)Dck​​(…Dc1​​(R)…) là nullable (chấp nhận được chuỗi rỗng).

    Bảng chữ cái chỉ gồm hai ký hiệu 0 và 1. Biểu thức chính quy RRR được xây dựng từ:

    • 0, 1: hai ký hiệu đơn.
    • @: ký hiệu đặc biệt biểu diễn ngôn ngữ {ε}\{\varepsilon\}{ε} (chỉ chấp nhận chuỗi rỗng).
    • #: ký hiệu đặc biệt biểu diễn ngôn ngữ rỗng ∅\emptyset∅ (không chấp nhận bất kỳ chuỗi nào, kể cả chuỗi rỗng).
    • Phép nối liền kề, phép hợp | (ưu tiên thấp nhất), các toán tử hậu tố *, +, ? (ưu tiên cao nhất), và dấu ngoặc đơn ( ) để nhóm — ngữ nghĩa như thông thường trong lý thuyết ngôn ngữ hình thức.

    Cho RRR và qqq chuỗi truy vấn (mỗi chuỗi chỉ gồm ký tự 0/1, có thể là chuỗi rỗng), với mỗi chuỗi hãy xác định chuỗi đó có thuộc ngôn ngữ L(R)L(R)L(R) hay không.

    Ví dụ: R=R = R= 0?1+ (không có hoặc có một ký tự 0, theo sau bởi một hoặc nhiều ký tự 1). Với truy vấn 1: thuộc L(R)L(R)L(R). Với truy vấn 01: thuộc L(R)L(R)L(R).

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

      Dòng 1: biểu thức chính quy RRR (độ dài từ 111 đến 100100100 ký tự, không chứa khoảng trắng).

      Dòng 2: số nguyên qqq (1≤q≤201 \le q \le 201≤q≤20) — số chuỗi truy vấn.

      qqq dòng tiếp theo, mỗi dòng là một chuỗi truy vấn chỉ gồm ký tự 0/1 (có thể là dòng rỗng nếu truy vấn là chuỗi rỗng), độ dài mỗi truy vấn không quá 303030.

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

      Với mỗi chuỗi truy vấn theo đúng thứ tự xuất hiện trong input, in ra một dòng YES nếu chuỗi đó thuộc L(R)L(R)L(R), ngược lại in ra NO.

      Với ví dụ ở trên (R=R=R= 0?1+, truy vấn 1 rồi 01), kết quả in ra là:

      YES
YES

    Ví dụ:

    Đầu vào:

    0*1(0|1)*
5

1
01
00
111

    Đầu ra:

    NO
YES
YES
NO
YES

    Đầu vào:

    (0|1)*
2

0110

    Đầu ra:

    YES
YES

    Đang tải editor...