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

Each string has the shape $w\,o^{\,n}$: a prefix $w$ over $\{a,b\}$ followed by a block of $n$ copies of a third symbol $o$. Since $o \notin \{a,b\}$, any machine can detect exactly where $w$ ends and the $o$-block begins.

$L_1$ — not even context-free. The constraint is $n_a(w)=n_b(w)=n$, i.e. (number of $a$'s) $=$ (number of $b$'s) $=$ (number of $o$'s). Intersect with the regular language $a^* b^* o^*$:

$L_1 \cap a^* b^* o^* = \{\, a^n b^n o^n \mid n \ge 0 \,\},$

the canonical non-CF language. CFLs are closed under intersection with a regular language, so if $L_1$ were context-free then $a^n b^n o^n$ would be too — contradiction. Hence $L_1$ is not context-free (so certainly not deterministic CF).

$L_2$ — deterministic context-free. Here $|w| = n$, i.e. the number of trailing $o$'s equals the length of $w$. A DPDA pushes one marker for every symbol of $w$ (deterministic: $a,b$ are clearly distinct from $o$), and on the first $o$ switches to pop mode, popping one marker per $o$ and accepting iff the stack empties exactly when the input ends. No guessing is needed, so $L_2$ is a deterministic CFL.

$L_3$ — context-free but nondeterministic. $L_3 = A \cup B$ where

$A = \{\, w o^n \mid n_a(w) = n \,\}, \qquad B = \{\, w o^n \mid |w| = n \,\} = L_2.$

Each of $A$ and $B$ is a single matched-count language, so each is a DCFL, and their union is context-free. But while reading $w$ the machine cannot tell whether the upcoming $o$-count will be matched against the number of $a$'s (condition $A$) or against the full length (condition $B$) — these require pushing different amounts, so it must guess. The union of two DCFLs of this form is not deterministic. Thus $L_3$ is context-free but nondeterministic.

Checking the options.

So the correct choice is option 3, matching the official key.

Exam trick: Two equal-count constraints that are interleaved ($n_a=n_b=n_o$) collapse to $a^n b^n o^n$ under intersection with $a^* b^* o^*$ → not CF. A single count match ($|w|=$ #o, or #a $=$ #o) is a DCFL. An OR of two different single-count matches forces a guess → CF but not deterministic.