Построение временной сложности DFA непосредственно из регулярного выражения

Я хотел узнать временную сложность построения DFA из регулярного выражения непосредственно с помощью алгоритма 3.36 в книге драконов.

Я был сбит с толку относительно того, сколько раз будет выполняться внешний цикл while? Как и в Dstates, как указано в алгоритме, будут ли они равны количеству операндов в регулярном выражении?

Также сколько работы будет выполнено внутри цикла for, который выполняется равным |Σ| раз?

Спасибо.


regex runtime time-complexity compiler-construction dfa
person Shubham Asthana    schedule 18.02.2014    source источник
comment
Это ужасно построенный вопрос для SO, пока   -  person gwillie    schedule 18.02.2014
comment
en.wikipedia.org/wiki/   -  person nhahtdh    schedule 18.02.2014
comment
@nhahtdh данная сложность заключается в использовании NFA для построения, что в худшем случае приведет к 2 ^ n состояниям, следовательно, O (2 ^ n) . я попросил построить из регулярного выражения напрямую   -  person Shubham Asthana    schedule 18.02.2014
comment
Проще говоря, @gwillie я хочу знать временную сложность построения dfa непосредственно из регулярного выражения с использованием алгоритма 3.36 в книге Dragon: |   -  person Shubham Asthana    schedule 18.02.2014
comment
@nhahtdh Нет необходимости проходить NFA, так как мы можем построить синтаксическое дерево из регулярного выражения и, следовательно, использовать его ..... для получения дополнительной информации я рекомендую вам пройти алгоритм 3.36 в книге драконов .... я знаю, что это в худшем случае сложность будет 2 ^ n, но хотелось бы знать точное выражение..   -  person Shubham Asthana    schedule 18.02.2014
comment
@gwillie, я не думаю, что у тебя сейчас есть ответ на этот вопрос ... :/   -  person Shubham Asthana    schedule 18.02.2014

Ответы (1)


arrow_upward
1
arrow_downward

Сложность конструкции по-прежнему будет O(2n). Рассмотрим наихудший пример, как описано в этом посте:

L = {w ∈ {0,1}*: |w| ≥ n и n-й символ от последнего равен 1}

Регулярное выражение, соответствующее языку, имеет вид (0+1)*1(0+1)...(0+1), где конечная часть повторяется n - 1 раз. Временная сложность по-прежнему будет O(2n), поскольку количество состояний в построенном DFA равно O(2n) (соответствует количеству суффиксов слово на Л).

person nhahtdh    schedule 18.02.2014
comment
да, я согласен, что это 2 ^ n в худшем случае, но, как я уже упоминал, я хотел знать, есть ли какая-либо связь между Dstates, упомянутыми в алгоритме, и операторами в регулярном выражении ... также я спросил, сколько работы будет выполнено в цикле for - person Shubham Asthana; 18.02.2014
comment
@Shubham: Независимо от работ, проделанных в другом месте, если конечный результат требует построения всего DFA, общая сложность будет O (2 ^ n). Мой ответ неполный, поскольку на самом деле он не отвечает на ваши другие вопросы. - person nhahtdh; 18.02.2014