Регулярные языки и регулярные выражения

Сложность
Легкий 25%

Регулярные языки и регулярные выражения

Существует два типа регулярных выражений.

Мы помним, что грамматика 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_RURU