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

    solution

    Đề bài: [Automat & NN hình thức] Phân biệt aⁿbⁿ và a*b*

    Một điểm mấu chốt phân biệt ngôn ngữ chính quy với ngôn ngữ phi ngữ cảnh (CFL): a*b* là chính quy, còn {aⁿbⁿ} (số a bằng số b, mọi a đứng trước mọi b) là CFL không chính quy (chứng minh bằng bổ đề bơm).

    Cho chuỗi w trên {a, b}, hãy phân loại:

    • AN_BN nếu w có dạng aⁿbⁿ (khối a rồi khối b, số lượng bằng nhau; n = 0 tức chuỗi rỗng cũng tính).
    • A_STAR_B_STAR nếu w ∈ a*b* nhưng số a khác số b.
    • OTHER nếu w ∉ a*b* (có a sau b).

    Ví dụ: aaabbb → AN_BN, aab → A_STAR_B_STAR, abab → OTHER.

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

      Một dòng: chuỗi w trên {a, b} (có thể rỗng).

    • Ràng buộc đầu vào:

      0 ≤ |w| ≤ 200, w ∈ {a,b}*.

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

      Một dòng: AN_BN, A_STAR_B_STAR hoặc OTHER.

    Ví dụ:

    Đầu vào:

    aaabbb

    Đầu ra:

    AN_BN

    Giải thích:

    Có dạng a³b³ (số a = số b = 3) → AN_BN.

    Đang tải editor...