Какое максимальное количество состояний вам необходимо в DFA для языка L_A *?
«Наибольшее количество состояний, в которых вы нуждаетесь» - это еще один способ попросить количество классов эквивалентности в соответствии с отношением неразличимости теоремы Михилла-Нерода. Предположим, что L_A "нуждается в" x состояниях (в минимальном DFA), где x меньше или равно n_A. Сколько состояний может L_A * «нужно»?
Конечно, бывают случаи, когда L_A * «нуждается» в меньшем количестве состояний, чем L_A. Рассмотрим язык {0, 1} над {0, 1}; минимальный DFA для этого имеет три состояния, тогда как минимальный DFA для {0, 1} * имеет одно состояние.
Кроме того, нетрудно представить себе языки, где L_A * «нуждается» в том же числе состояний: например, при L = L *. Предположим, что L_A = {0, 1} . Тогда L_A = {0, 1} ** = {0, 1} * = L и L_A * "требуется" столько же состояний.
Я думаю, что ваш вопрос действительно касается случаев, когда нам нужно больше и, в частности, сколько еще мы могли бы когда-либо понадобиться в худшем случае. Предположим, что классы эквивалентности L_A являются c_1, c_2, ..., c_x. Рассмотрим их как набор строк, которые берут строки в классе в строку в L_A. Тогда классы L_A * являются (c_1) (L_A *) + e, (c_2) (L_A *), ..., (c_w) (L_A *). Таким образом, максимальное число различных классов w; мы не можем создавать новые классы, применяя звезду Клейн. Но мы сможем их развалить! Возможно, что (c_a) (L_A) * = (c_b) (L_A) * для a! = B. Рассмотрим L_A = {0, 1}. Тогда c_1 = {0, 1}, c_2 = {e}, c_3 = {}.Тогда (c_1) (L_A) * + e = {e, 0, 1, ...}, (c_2) (L_A) * = {e, 0, 1, ...}, (c_3) (L_A) * знак равно Мы получаем два разных кандидата, используя этот метод, и мы можем еще больше его оценить, заметив, что в классе эквивалентности (c_3) (L_A) * нет строк.
Но важно то, что у нас никогда не будет больше; поэтому теоретический максимум числа «необходимых» состояний равен x, где x - «необходимое» количество состояний L_A.
Какое максимальное количество состояний вам нужно в NFA для языка L_A (пересечение) L_B?
< Пусть х = N_A быть числом "необходимо" для L_A и у < = N_B быть числом "необходимо" для N_B. Пересечение может легко привести, например, к пустующему языку, поэтому должно быть ясно, что «необходимые» состояния в пересечении могут быть намного ниже, чем x и y. Это будет то же самое, если L_A = L_B, так как L_A (пересечение) L_B = L_A (пересечение) L_A = L_A в этом случае.
Обратите внимание, что нам никогда не понадобится больше, чем x * y, поскольку мы можем всегда использовать декартовую конструкцию машины для построения DFA с числом состояний, равным произведению чисел состояний в DFA для L_A и L_B, и DFA - это NFA. Естественным вопросом является ли этот предел для некоторого класса языков L_A и L_B. Ответ в том, что это так.
Рассмотрим L_A = {a^nk} и L_B = {a^mk}, где n и m взаимно простые и больше единицы. Тогда L_A (пересечение) L_B = {a^(nm)}. Минимальный DFA для L_A имеет n состояний, а минимальный DFA для L_B имеет m состояний. Минимальный DFA для L_A (пересечение) L_B имеет состояния nm. Ни один из этих DFA не имеет соответствующих эквивалентных NFA с меньшим количеством состояний. DFA для a^2k имеет таблицу перехода:
q e q'
q0 a q1
q1 a q2
С принятием q0. Поэтому максимальный (достижимый) - это x y < = n_A n_B.