Описание тега regular-language

Описание тега Вопросы с тегом
Регулярный язык - это язык, который может быть представлен регулярным выражением, и, таким образом, каждая строка на языке может быть принята соответствующим детерминированным конечным автоматом. Примечание. Регулярный язык не следует путать с регулярными выражениями. Если у вас возник вопрос о сопоставлении с образцом в строках, используйте вместо него тег [regex].

Для данного алфавита (конечного набора символов) Σ язык - это набор всех последовательностей таких символов в этом алфавите. Язык является регулярным языком именно тогда, когда он может быть выражен в терминах (формального) регулярного выражения, а принадлежность любой строки может быть определена конечным автоматом.

Регулярные языки принадлежат к высшей иерархии Иерархии Хомского и также называются грамматиками типа 3. Они находятся над контекстно-свободными языками типа 2, которые распознаются автоматами выталкивания, которые находятся над контекстно-зависимыми языками типа 1, распознаваемыми линейно ограниченными автоматами, и над рекурсивно перечисляемыми языками типа 0, которые могут быть распознаны Тьюрингом. Машины. Все обычные языки контекстно-зависимы, контекстно-зависимы и рекурсивно перечисляемы. Формальные регулярные выражения могут быть преобразованы в детерминированные конечные машины и в недетерминированные конечные машины, и при этом они будут представлять тот же регулярный язык.

Пожалуйста, не путайте это с регулярным выражением. Большинство механизмов регулярных выражений гораздо выразительнее формальных регулярных выражений, конечных автоматов и могут представлять нерегулярные языки.

Построение регулярного языка

Множество всех регулярных языков над заданным алфавитом Σ может быть получено точно таким образом:

  • Пустой язык {}, отклоняя все строки.
  • Язык, содержащий только пустую строку ε
  • Все языки, содержащие только один символ s ∈ Σ.
  • Каждый язык создан путем объединения, конкатенации или клейни-звезды обычных языков. Предположимv а также w строки обычного языка A а также B соответственно:
    • Союз (v|w)также является регулярным. Он принимает языки на любом изA или B.
    • Конкатенация vw также является регулярным.
    • Клини-звезда v*также является регулярным. Это означает любые копии строк вA конкатенированные, включая 0.

Примеры и не примеры обычных языков

  • Учитывая простой алфавит Σ = {0, 1}, где | представляет союз, * представляет собой звезду клини, все эти формальные регулярные выражения представляют собой обычный язык:

    • Регулярное выражение "0", "1", "(0|1)", "01", "11", "0*" все обычные.
    • Регулярное выражение "(0(0|1)*1)", представляющий все двоичные строки, начинающиеся с 0 и заканчивающиеся на 1, является регулярным.
    • Учитывая регулярное выражение R, язык "R+" а также "R?" все представляют собой обычный язык, тогда как +представляет собой один или несколько, и?представляет ноль или один. А именно,"R+" эквивалентно "RR*", а также "R?" эквивалентно "(R|ε)".
    • Учитывая регулярное выражение R, язык "R{m,n}" регулярно для всех естественных m,n, где {m,n} представляет "от m копии в n копий ". Это связано с тем, что он также включает объединение и объединение: "R{1,3}" расширяется до "(R|RR|RRR)".

  • Учитывая алфавит, используемый механизмами регулярных выражений, обычно это алфавит ASCII или Unicode, содержащий все символы ASCII или Unicode соответственно:

    • Регулярное выражение /^.+$/регулярно. Он включает в себя все непустые последовательности любого символа.
    • Регулярное выражение /^#[A-Za-z]{1,3}[0-9]{2,4}$/ представляет собой обычный язык, состоящий из всех строк с хэштегом, затем от одной до трех букв ASCII, за которыми следуют от двух до четырех десятичных цифр.
    • Регулярное выражение /^([\d][\w])*$/представляет собой обычный язык. Он состоит из всех строк, в которых чередуются символы цифр и символы слова. Стенография\d а также \w примеры союза.

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

    • Регулярное выражение "(.+)\1"представляет собой нерегулярный язык. Вовлечение обратной ссылки для захвата первой группы.+, он принимает все последовательности прописных латинских букв, повторяющиеся ровно дважды. В формальной теории языка они называются квадратами.
      • "ABCABC", "1234.1234." принимаются
      • "ABCAB", "1234567891234567890" отклоняются.

Дальнейшее чтение