Trong lý thuyết trình biên dịch, biểu thức chính quy (regular expression) là công cụ đặc tả các loại token. Xét một biểu thức chính quy R chỉ được xây dựng từ:
|,*,( ) để nhóm, với thứ tự ưu tiên chuẩn: * > nối tiếp > |.Biểu thức rỗng (chuỗi R rỗng) chỉ khớp với chuỗi rỗng ε.
Cho biểu thức R và n chuỗi ký tự, với mỗi chuỗi hãy xác định chuỗi đó có thuộc ngôn ngữ do R sinh ra hay không (khớp toàn bộ chuỗi, không phải khớp một phần).
Ví dụ: R= (a|b)*c khớp với c, abc, aabbc, nhưng không khớp với abcd hay chuỗi rỗng.
Dòng 1: biểu thức chính quy R (có thể là dòng rỗng, biểu diễn ε; độ dài tối đa 200 ký tự, chỉ gồm chữ thường a-z và các ký tự | * ( )).
Dòng 2: số nguyên n (1≤n≤200).
n dòng tiếp theo, mỗi dòng là một chuỗi cần kiểm tra (có thể là dòng rỗng, biểu diễn chuỗi rỗng; chỉ gồm chữ thường a-z, độ dài tối đa 200).
In ra n dòng, dòng thứ i là YES nếu chuỗi thứ i thuộc ngôn ngữ của R, ngược lại in NO.
Ví dụ:
Đầu vào:
3
a
b
Đầu ra:
YES
NO
NO
Đầu vào:
(a|b)*c
5
c
abc
aabbc
abcd
Đầu ra:
YES
YES
YES
NO
NO
Đang tải editor...