Регулярные языки и регулярные выражения
Существует два типа регулярных выражений.
Мы помним, что грамматика G1 = (T, N, S, R) является правильным регулярным выражением, если правила R имеют вид: A → aB или A → a, где A, B ∈ N и a ∈ T.
Напомним, что грамматика G2 = (T, N, S, R) является левым регулярным выражением, если правила R имеют вид: A → Ba или A → a, где A, B ∈ N и a ∈ T .
Преимущество различения правильных грамматик справа или слева проявляется при анализе: если мы читаем символы анализируемого слова слева направо, то
- право-регулярная грамматика будет использоваться для нисходящего анализа, от аксиомы к слову
- леворегулярная грамматика будет использоваться для восходящего анализа от слова к аксиоме.
Например, чтобы проанализировать слово aaabb с помощью грамматики G1, мы построим вывод S1 ⇒ aS1 ⇒ aaS1 ⇒ aaaU1 ⇒ aaabU1 ⇒ aaabb; в то время как для анализа этого слова с помощью грамматики G2 мы построим вывод aaabb ⇐ U2aabb ⇐ U2abb ⇐ U2bb ⇐ S2b ⇐ S2.
Язык и выражение
Выражение E является регулярным выражением над алфавитом A тогда и только тогда, когда:
- Е = ∅ или
- Е = ε или
- E = a с a ∈ A или
- Е = Е1 | E2 и E1 и E2 — два регулярных выражения на A или
- E = E1.E2 и E1 и E2 — два регулярных выражения на A или
- Е = Е*1 лето1 является регулярным выражением на A
Операторы ∗, . и | имеют убывающий приоритет. При необходимости можно добавить скобки.
Язык L(E), описываемый регулярным выражением E, определенным в алфавите A, определяется формулой
- L(E) = ∅, если E = ∅,
- L(E) = {ε}, если E = ε,
- L(E) = {а}, если Е = а,
- L(E) = L(E1) ∪ L(E2), если E = E1 | Е2,
- L(E) = L(E1).L(E2), если E = E1.E2,
- L(E) = L(E1)* если Е = Е*1 лето1 является регулярным выражением на A.
Эквивалентность между регулярными выражениями и обычными языками устанавливается следующими двумя импликациями:
- Любое регулярное выражение описывает регулярный язык.
- Любой регулярный язык может быть описан регулярным выражением.
Список тривиальных эквивалентов:
Процесс создания автомата из регулярного выражения
RU 
FR 
EN 
ES