Рубрики

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

Как обсуждалось в иерархии Хомского , регулярные языки являются наиболее ограниченными типами языков и принимаются конечными автоматами.

Регулярные выражения
Регулярные выражения используются для обозначения регулярных языков. Выражение является регулярным, если:

  • ɸ регулярное выражение для регулярного языка ɸ.
  • ɛ — регулярное выражение для регулярного языка {ɛ}.
  • Если a ∈ Σ (Σ представляет входной алфавит ), a является регулярным выражением с языком {a}.
  • Если a и b являются регулярным выражением, a + b также является регулярным выражением с языком {a, b}.
  • Если a и b являются регулярным выражением, ab (объединение a и b) также является регулярным.
  • Если a является регулярным выражением, a * (0 или более раз a) также является регулярным.
  • Regular ExpressionRegular Languages
    set of vovels( a ∪ e ∪ i ∪ o ∪ u ){a, e, i, o, u}
    a followed by 0 or more b(a.b*){a, ab, abb, abbb, abbbb,….}
    any no. of vowels followed by any no. of consonants v*.c* ( where v – vowels and c – consonants) { ε , a ,aou, aiou, b, abcd…..} where ε represent empty string (in case 0 vowels and o consonants )

    Обычная грамматика: грамматика является регулярной, если она имеет правила формы A -> a или A -> aB или A -> ɛ, где ɛ — специальный символ с именем NULL.

    Обычные языки: язык является регулярным, если он может быть выражен в терминах регулярного выражения.

    Свойства закрытия регулярных языков
    Объединение: если L1 и L2 являются двумя регулярными языками, их объединение L1 ∪ L2 также будет регулярным. Например, L1 = {a n | n ≥ 0} и L2 = {b n | n ≥ 0}
    L3 = L1 ∪ L2 = {a n ∪ b n | n ≥ 0} также регулярно.
    Пересечение: если L1 и L2 — два регулярных языка, их пересечение L1 ∩ L2 также будет регулярным. Например,
    L1 = {a m b n | n ≥ 0 и m ≥ 0} и L2 = {a m b n ∪ b n a m | n ≥ 0 и m ≥ 0}
    L3 = L1 ∩ L2 = {a m b n | n ≥ 0 и m ≥ 0} также регулярно.
    Конкатенация: если L1 и L2 являются двумя обычными языками, их конкатенация L1.L2 также будет регулярной. Например,
    L1 = {a n | n ≥ 0} и L2 = {b n | n ≥ 0}
    L3 = L1.L2 = { м . б н | m ≥ 0 и n ≥ 0} также регулярно.
    Замыкание Клини: если L1 регулярный язык, замыкание Клини L1 * также будет регулярным. Например,
    L1 = (a ∪ b)
    L1 * = (a ∪ b) *
    Дополнение: если L (G) регулярный язык, его дополнение L '(G) также будет регулярным. Дополнение к языку можно найти, вычитая строки из L (G) из всех возможных строк. Например,
    L (G) = {a n | n> 3}
    L '(G) = {a n | n <= 3}

    Примечание: два регулярных выражения эквивалентны, если сгенерированные ими языки одинаковы. Например, (a + b *) * и (a + b) * генерируют один и тот же язык. Каждая строка, которая генерируется (a + b *) *, также генерируется (a + b) * и наоборот.

    Как решить проблемы с регулярными выражениями и регулярными языками?

    Вопрос 1: Какой из следующих языков над алфавитом {0,1} описывается регулярным выражением?
    (0 + 1) * 0 (0 + 1) * 0 (0 + 1) *
    (A) Набор всех строк, содержащих подстроку 00.
    (B) Множество всех строк, содержащих не более двух нулей.
    (C) Множество всех строк, содержащих как минимум два 0.
    (D) Множество всех строк, которые начинаются и заканчиваются либо 0, либо 1.

    Решение:
    опция A говорит, что она должна иметь подстроку 00. Но 10101 также является частью языка, но она не содержит 00 в качестве подстроки. Так что это не правильный вариант.
    Вариант B говорит, что он может иметь максимум два 0, но 00000 также является частью языка. Так что это не правильный вариант.
    Опция C говорит, что она должна содержать как минимум два 0. В регулярном выражении присутствуют два 0. Так что это правильный вариант.
    Вариант D говорит, что он содержит все строки, которые начинаются и заканчиваются либо 0, либо 1. Но он может генерировать строки, которые начинаются с 0 и заканчиваются 1 или наоборот. Так что это не правильно.

    Вопрос 2: Какой из следующих языков генерируется данной грамматикой?
    S -> aS | BS | ε
    (A) {a n b m | n, m ≥ 0}
    (B) {w ∈ {a, b} * | w имеет одинаковое количество а и б}
    (C) {a n | n ≥ 0} ∪ {b n | n ≥ 0} ∪ {a n b n | n ≥ 0}
    (D) {a, b} *

    Решение: Вариант (A) говорит, что он будет иметь 0 или более a, а затем 0 или более b. Но S -> bS => baS => ba также является частью языка. Так что (А) не правильно.
    Вариант (Б) говорит, что он будет иметь равное нет. а и б. Но Но S -> bS => b также является частью языка. Так что (Б) не правильно.
    Вариант (C) говорит, что у него будет 0 или более a или 0 или более b или a, за которыми следуют b. Но, как показано в варианте (A), ba также является частью языка. Так что (с) не правильно.
    Вариант (D) говорит, что он может иметь любое количество а и любое количество б в любом порядке. Так что (D) правильно.

    Вопрос 3: Регулярное выражение 0 * (10 *) * обозначает тот же набор, что и
    (А) (1 * 0) * 1 *
    (B) 0 + (0 + 10) *
    (С) (0 + 1) * 10 (0 + 1) *
    (D) ни один из них

    Решение:
    два регулярных выражения эквивалентны, если сгенерированные ими языки одинаковы.
    Опция (A) может генерировать все строки, сгенерированные 0 * (10 *) *. Так что они эквивалентны.
    Option (B) string null не может генерироваться данными языками, но 0 * (10 *) * может. Так что они не эквивалентны.
    Опция (C) будет иметь 10 в качестве подстроки, но 0 * (10 *) * может или не может. Так что они не эквивалентны.

    Вопрос 4: Регулярное выражение для языка, имеющего входные алфавиты a и b, в котором два a не объединяются:
    (A) (b + ab) * + (b + ab) * a
    (B) a (b + ba) * + (b + ba) *
    (С) оба варианта (А) и (Б)
    (D) ничего из вышеперечисленного

    Решение:
    Вариант (C) с указанием обоих вариантов (A) и (B) является правильным регулярным выражением для поставленного вопроса.
    Язык в вопросе может быть выражен как L = {& epsilon, a, b, bb, ab, aba, ba, bab, baba, abab,…}.

    В варианте (A) «ab» считается строительным блоком для нахождения требуемого регулярного выражения. (B + ab) * охватывает все случаи сгенерированных строк, заканчивающихся на «b». (B + ab) * a охватывает все случаи сгенерированные строки, заканчивающиеся на.

    Применяя аналогичную логику для опции (B), мы можем видеть, что регулярное выражение получено, рассматривая 'ba' как строительный блок, и охватывает все случаи строк, начинающихся с a и начинающихся с b.

    Эта статья предоставлена Sonal Tuteja.

    Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

    Рекомендуемые посты:

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

    0.00 (0%) 0 votes