Cтраница 1
Расширенное регулярное выражение над алфавитом 2 определяется следующим образом. [1]
Если расширенное регулярное выражение не содержит знаков дополнения, то его называют полурасширенным. [2]
Далее М2 строит расширенное регулярное выражение R2, представляющее правильные вычисления с измерителем Ri для ДМТ М, которая допускает L и требует для этого не более g ( k0Jrl, n) клеток памяти. [3]
Покажите, что задача пустоты для расширенных регулярных выражений, использующих только знаки операций, и - I, неэлементарна. [4]
Постройте алгоритм, выясняющий, представляет ли произвольное расширенное регулярное выражение пустое множество. Какова временная и емкостная сложности вашего алгоритма. [5]
ДМТ MI с памятью, ограниченной функцией g ( k0, n), которая выясняет, пусто ли множество, представленное расширенным регулярным выражением. Предположив, что MI существует, можно построить ДМТ М2, распознающую язык L следующим образом. [6]
Итак, машины Ма не существует, и, значит, не существует Мг. Поэтому проблема пустоты для расширенных регулярных выражений неразрешима никакой машиной Тьюринга с емкостной сложностью, ограниченной элементарной функцией. [7]
Тогда не существует ДМТ с емкостной ( и, следовательно, временной) сложностью, ограниченной сверху функцией S ( n), которая могла бы установить, пусто ли множество, представленное произвольным расширенным регулярным выражением. [8]
Поскольку теперь у нас есть операция дополнения, достаточно рассматривать задачу пустоты, а именно: пусто ли множество, представленное данным регулярным выражением. Мы увидим, что, располагая операцией дополнения, можно представлять регулярные множества еще более короткими выражениями и задача пустоты для расширенных регулярных выражений значительно труднее задачи пустоты дополнения для полу расширенных регулярных выражений. [9]
Поскольку теперь у нас есть операция дополнения, достаточно рассматривать задачу пустоты, а именно: пусто ли множество, представленное данным регулярным выражением. Мы увидим, что, располагая операцией дополнения, можно представлять регулярные множества еще более короткими выражениями и задача пустоты для расширенных регулярных выражений значительно труднее задачи пустоты дополнения для полу расширенных регулярных выражений. [10]