فرض کنید دو زبان زیر روی الفبای a,b,c تعریف شده باشند: L_1 = w ∈ a,b,c ^ middle n_a(w) + n_b(w) = n_c(w) L_2 = w ∈ a,b,c ^ middle n_a(w) + n_b(w) = 2^(n_c(w)) از این دو زبان کدام مستقل از متن است؟

سوال ۸۶ کنکور ارشد علوم کامپیوتر ۱۴۰۵

اهمیت

۰/۵

فرض کنید دو زبان زیر روی الفبای $\{a,b,c\}$ تعریف شده باشند:

$L_1 = \left\{ w \in \{a,b,c\}^* \;\middle|\; n_a(w) + n_b(w) = n_c(w) \right\}$

$L_2 = \left\{ w \in \{a,b,c\}^* \;\middle|\; n_a(w) + n_b(w) = 2^{\,n_c(w)} \right\}$

از این دو زبان کدام مستقل از متن است؟

#context-free-language#parikh-theorem#semilinear-set#one-counter#non-cfl