Регулярна мова

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Регулярна мова (регулярна множина) - це формальна мова третього (найвужчого) класу з класифікації Чомскі.

Регулярна мова може задаватись регулярною граматикою, регулярним виразом, та розпізнаватись ДСкА чи НДСкА.

Для визначення приналежності мови класу регулярних існує Лема про накачку для регулярних мов та теорема Майхілла-Нероде.

Означення[ред.ред. код]

Нехай \Sigma - скінченний алфавіт. Регулярна мова в цьому алфавіті визначається рекурсивно:

  1. \emptyset - пуста множина – це регулярна множина в алфавіті \Sigma
  2. \varepsilon - пусте слово – це регулярна множина в алфавіті \Sigma
  3. \{a\},\ a \in \Sigma – однолітерна множина – регулярна множина в алфавіті \Sigma
  4. Якщо P та Q – регулярні множини, то такими є наступні множини:
    • P \cup Q (операція об‘єднання);
    • P * Q (операція конкатенації);
    • \{P\} = {\varepsilon} \cup P \cup P*P \cup \ldots (операція ітерації).
  5. Ніякі інші множини, окрім побудованих на основі ПП 1-4 не є регулярними множинами.

Посилання[ред.ред. код]

  1. Волохов. Системне програмування.