Может ли регулярное выражение быть бесконечным?

Я знаю, что языки, которые можно определить с помощью регулярных выражений, и языки, распознаваемые DFA / NFA (конечными автоматами), эквивалентны. Также не существует DFA для языка . Но все это можно записать с помощью регулярных выражений (в этом отношении любого нерегулярный язык может быть) , как . Но мы знаем, что каждый язык с регулярным выражением имеет DFA, который его распознает (противоречие с моим предыдущим утверждением). Я знаю, что это тривиальная вещь, но включает ли определение регулярного выражения условие, что оно должно быть конечным? $\{0^n1^n|n \ge 0\}$ $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$

formal-languages regular-languages regular-expressions SashaS
источник

Вы уже ответили на свой вопрос: если REG CFL, такие термины не могут быть регулярными выражениями.

⊊

$\subsetneq$

Рафаэль

Еще одно замечание: если мы отбросим требование конечности DFA / NFA, мы сможем построить автомат для приема

{0^{n} 1^{n} ∣ n \geq 0}

$\{0^n1^n\mid n\geq0\}$ .

Как пункт терминологии, слово «автомат» является множественным числом слова «автомат». Нет слова «автоматы» - вы не можете сделать его более множественным, чем оно есть. (автоматы правильны как притяжательные, но не как множественное число)

целомудренно из Великобритании

Ответы:

Если бы регулярным выражениям было разрешено быть бесконечными, то любой язык был бы регулярным.

Учитывая язык , мы всегда можем определить регулярное выражение , который точно определяет . (Пример: регулярное выражение определяет .) $L=\{w_1, w_2, \ldots\}$ $R = w_1 + w_2 + \cdots$ $L$
$R_1 = \epsilon+0+1+00+01+10+11+\cdots$ $L_1=\{0,1\}^*$

Мы знаем, что некоторые языки не являются регулярными, поэтому это показывает, что бесконечные регулярные выражения описывают больший класс языков, чем конечные регулярные выражения.

Ран Г.
источник

Мне нравится этот ответ, потому что он не только говорит о том, что бесконечные регулярные выражения отличаются, но что концепция в целом не имеет смысла.

jmite

Более краткое изложение того, что я скрыл во втором абзаце, и, следовательно, более ясное.

Дэвислор

Но это заканчивается чистой тавтологией. Тогда почему мы не считаем все языки обычными, если они имеют эту форму? То, что мы делаем с регулярными выражениями, больше не работает. Мы не можем построить конечный автомат с помощью индуктивного алгоритма, потому что он никогда не заканчивается и имеет бесконечные состояния. Мы не можем сравнивать все в списке и отклонять, если ничего не найдено. И мы не можем физически представлять список в любом случае. (Списки, которые мы можем сгенерировать с помощью компьютера, являются разрешимыми языками.) Мы можем доказать что-то, используя тот факт, что у каждого языка есть эта форма, но не то, что мы знаем о регулярных выражениях.

Дэвислор

@jmite "не имеет смысла" или особый случай?

BAR

@BAR Не имеет смысла, так как в классе языков над описываемых бесконечными регулярными выражениями, просто т. Е. Множество всех языков. Мы не получаем такой класс языков, как вы с конечными RE, CFG или даже машинами Тьюринга.

Σ

$\Sigma$

2^{Σ}

$2^{\Sigma}$

jmite

Да, это должно быть конечно. Представьте, что у вас есть этот бесконечный набор возможных совпадений, и ваш вклад есть 011. Сможете ли вы когда-нибудь отказаться от этого? Вы когда-нибудь закончили матчи, чтобы проверить?

Есть ли язык, который по этому определению не был бы регулярным ? Как насчет набора всех пар программ и входов, так что данная программа останавливается на данном входе?

Теперь, если у вас была программа, которая перечисляла строки на языке в лексикографическом порядке -

Обновить

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

Почему мы определяем «обычный» язык таким образом? Поскольку каждый формальный язык является подмножеством строк в алфавите, и каждый набор строк может быть выражен как объединение синглетонов, поэтому, если бы мы назвали любой набор строк «обычным» языком, обычный язык был бы просто синонимом для язык . Это не очень полезное определение, тем более что мы не можем реализовать его на аппаратном или программном уровне. Мы нигде не можем хранить произвольный бесконечный список или строить машину с бесконечным состоянием.

Как я уже говорил, если у вас есть способ перечислить все строки в языке по порядку, вы можете построить решающее значение из этого (принять, когда вы видите эту точную строку, отклонить, если вы встретите строку, которая идет после той, которую вы ищите) и наоборот (для каждой строки по порядку, пропустите ее через решатель и выведите ее тогда и только тогда, когда она принята). Таким образом, если бы мы считали каждый перечисляемый язык регулярным , каждый разрешимый язык был бы «регулярным», и нам потребовался бы новый термин для языков, распознаваемых конечными автоматами и их эквивалентными кодировками в качестве конечных выражений.

Davislor
источник

Этот ответ неверен. Один только факт, что некоторое представление языка не позволяет наивно строить алгоритмическое решение, не означает, что это представление неверно; могут быть другие подходы. Фактически, каждый решаемый язык имеет представление той формы, которую предлагает Саша! Короче говоря, вы совершаете ошибку «я не вижу как, поэтому это должно быть невозможно».

Рафаэль

@ Рафаэль: Пожалуйста, примите во внимание последствия вашего заявления: « Каждый решающий язык имеет представление той формы, которую предлагает Саша!» Вот, собственно, то, о чем я говорил в своем ответе. Вопрос был в том, все ли языки этой формы определены как обычные? Хорошо, каждый решаемый язык регулярен? (И, как я показал, некоторые неразрешимые тоже?) Это было бы полезным определением «обычный»?

Дэвислор

Кроме того, далеко не ошибочно полагая, что решение для бесконечного списка строк не может быть сделано, мое последнее предложение было подсказкой о том, как это можно сделать: если список строк упорядочен, вы можете отклонить его, как только когда вы встретите строку в заказе. Тем не менее, конечный автомат не может сделать это, потому что он не может представить все состояния сравнения с каждой строкой в бесконечном списке, а также не могут регулярные выражения. Если бы они могли, они были бы достаточно сильны, чтобы распознавать все решаемые языки.

Дэвислор

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

Таким образом, язык, определяемый {ϵ} ∪ {01} ∪ {0011} ... будет регулярным. Для каждого обычного языка существует NFA. Один из способов получить этот NFA состоит в том, чтобы иметь отдельные NFA для каждого из {ϵ}, {01}, {0011} ... и объединять их, используя переходы ϵ. Поскольку существует бесконечное количество различных регулярных выражений, нам нужно объединить бесконечные под-NFA. Однако NFA может иметь только конечное число состояний (определение NFA).

Таким образом, не существует NFA, который может определять язык, определенный объединением бесконечных регулярных выражений, что подразумевает, что язык не является регулярным.

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

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

Анураг Пешне
источник

Ваши «бесконечные регулярные выражения» затем определяют другой класс языков, а не регулярные языковые стандарты. Фактически, они способны определять любой язык, и это совершенно неинтересно (они не конечны, поэтому с ними трудно работать; и они могут делать все, что угодно, поэтому не нужно ничего изучать с точки зрения ограничений).

vonbrand