Регулярное выражение может быть рекурсивно определено следующим образом:
ε является регулярным выражением, обозначающим язык, содержащий пустую строку. (L (ε) = {ε})
φ является регулярным выражением, обозначающим пустой язык. (L (φ) = {})
x — это регулярное выражение, где L = {x}
Если X является регулярным выражением, обозначающим язык L (X), а Y является регулярным выражением, обозначающим язык L (Y) , то
X + Y является регулярным выражением, соответствующим языку L (X) ∪ L (Y), где L (X + Y) = L (X) ∪ L (Y) .
ИКС . Y является регулярным выражением, соответствующим языку L (X). L (Y) где L (XY) = L (X). L (Y)
R * является регулярным выражением, соответствующим языку L (R *), где L (R *) = (L (R)) *
Если мы применяем какое-либо из правил несколько раз от 1 до 5, это регулярные выражения.