Результаты поиска по запросу "computation-theory"

1 ответ

Самая низкая вычислительная сложность (Big-O)

Из этих алгоритмов я знаю, что Alg1 - самый быстрый, так как он равен n в квадрате. Далее будет Alg4, так как это n куб, а затем Alg2, вероятно, самый медленный, поскольку он равен 2 ^ n (который, как предполагается, имеет очень низкую ...

1 ответ

Насосная лемма для обычного языка

У меня есть небольшая путаница в проверке, является ли данный язык регулярным или нет, используя лемму прокачки.Предположим, мы должны проверить:L. Язык, при...

1 ответ

Устранение немедленной левой рекурсии

Я понимаю, что для того, чтобы исключить немедленную левую рекурсию из грамматики, содержащей произведение формы A⇒Aα, мне нужно заменить ее на A⇒βA'and A'⇒αA / ∈ У меня есть следующие производства, мне нужно устранить немедленную ...

ТОП публикаций

1 ответ

Тьюринг во время компиляции C # 4.0 завершен?

Существует общеизвестный факт, чтоШаблоны C ++ завершены по Тьюрингу, CSS завершен (!) и чтоC # разрешение перегрузки является NP-сложным (даже без дженерико...

1 ответ

Пример нелинейного, недвусмысленного и недетерминированного КЛЛ?

В классификации формальных языков Хомского мне нужны некоторые примеры

4 ответа

Является ли * b * регулярным?

2 ответа

Каким будет DFA для регулярного выражения 0 (0 + 1) * 0 + 1 (0 + 1) * 1?

Это DFA, который я нарисовал Это правильно? Я смущен, потому чтоq4 государство имеет2 различные переходы для одного и того же входного символа, который нарушает правилоDFA, но я не могу придумать другого решения.

2 ответа

Лево-линейная и праволинейная грамматика

Мне нужна помощь в построении лево-линейной и праволинейной грамматики для языков ниже? a) (0+1)*00(0+1)* b) 0*(1(0+1))* c) (((01+10)*11)*00)*Для а) у меня есть следующее: Left-linear S --> B00 | S11 B --> B0|B1|011 Right-linear S --> 00B | 11S ...

1 ответ

Это подразумевает, что языки CFG не закрыты в дополнении.

CFG дополнения к L = {ww | w принадлежит {0,1} *}?

2 ответа

Лево-линейная и праволинейная грамматика