dfa

0зной

1ответ

Пусть Σ = {a}, предположим, что язык L = {a^(2012.K)/K> 0}, что минимальное количество состояний, необходимых в DFA для распознавания L

По-моему, это должно быть 2012 год, но Я не уверен. Спасибо за помощь.

0зной

1ответ

Теория вычислений GATE 2012

4) Рассмотрим набор строк на {0,1}, в котором каждая подстрока из 3 символов имеет не более двух нулей. Например, 001110 и 011001 находятся на языке, но 100010 - нет. Все строки длиной менее 3 также н

0зной

2ответ

Компилятор DFA (a + b) * vs (a | b) * любая разница между обоими?

do (a + b) * и (a | B) * производят тот же DFA и тот же выход? В математике, где используется слово «или», мы используем оператор сложения. Значит ли это, что оба выражения эквивалентны?

0зной

1ответ

Можно ли определить количество состояний в минимальном DFA без его явного построения?

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

0зной

1ответ

Докажите, что DFA над двоичным алфавитом с k состояниями может распознавать максимум k^(2k +1) * 2^k языков

Мне дали этот вопрос в тесте, и я не мог этого сделать. Попытавшись немного, я все еще не могу этого сделать. Я думаю, что я что-то упускаю, но не знаю, что. Кто-нибудь может мне помочь?

0зной

1ответ

Понимание алгоритма закрытия epsilon pseudocode

Следующий псевдокод от Введение в построение компилятора в мире Java книга. Предполагается, что этот алгоритм выводит epsilon-замыкание множества состояний недетерминированной конечной машины (в конеч