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

A language of the form $a^{n}b^{m}c^{k}d^{t}$ is regular iff the membership condition does not force the exponent of one block to equal (be a function of) the exponent of a different block. Whenever two separated blocks must share the same counter, a finite automaton cannot remember the count, and the language becomes (at best) context-free, not regular.

Examine each option:

Option 1 — $a^{n}b^{m}c^{n}d^{2n}$. The exponent $n$ is reused for the $a$, $c$, and $d$ blocks ($d^{2n}$). The machine would have to count $a$'s and later check $c^{n}d^{2n}$. Pumping the $a$-block breaks the equality, so this is not regular.

Option 2 — $a^{n}b^{t}c^{k}d^{t}$. The $b$-block and the $d$-block both carry the exponent $t$, with a $c^{k}$ block between them. Matching $b^{t}\dots d^{t}$ across an arbitrary middle is not regular (it is context-free). Not regular.

Option 3 — $a^{n}b^{m}c^{k}d^{t}$ with the single condition $n+m+k+t>5$ and $n,m,k,t>0$. Here $n,m,k,t$ are four independent exponents, so the underlying skeleton is just $a^{+}b^{+}c^{+}d^{+},$ which is regular. The only extra requirement, $n+m+k+t>5$, says the total length must exceed $5$. Because each exponent is at least $1$, the length is at least $4$; the constraint merely removes the finitely many strings of length $\le 5$. A regular language minus a finite set is still regular (finite difference / closure under set difference with a finite, hence regular, set). Therefore option 3 is regular. ✅

Option 4 — $a^{n}b^{m}c^{k}d^{m}$. The $b$-block and the $d$-block share the exponent $m$ across a $c^{k}$ block, exactly the same matching problem as option 2. Not regular.

Only option 3 avoids cross-block counting, so it is the regular language.

Exam trick: For $a^{*}b^{*}c^{*}d^{*}$-style sets, scan the exponents: if a letter's superscript reappears (possibly scaled, e.g. $2n$) on a non-adjacent block, the language is non-regular. A bound that is only a linear inequality on otherwise-independent exponents just trims finitely many strings, keeping the language regular.