Given the following two statements: (i) \(L=\{w\mid n_{a}(w)=n_{b}(w)\}\) is…

Answer: Both statements are true.

Statement (i): L = { w | number of a's in w = number of b's in w } is deterministic context-free but not linear.

• Deterministic PDA construction (idea): use the stack to store the current surplus symbol and count. When reading an 'a':

• If the top-of-stack indicates a surplus of a's (or stack is empty), push a marker for an a. If the top indicates a surplus of b's, pop one marker instead. Symmetrically handle reading a 'b'.

• All actions are determined by the current input symbol and the stack top (no nondeterministic choice). Accept if and only if the input is exhausted and the stack is empty. Thus a deterministic PDA recognizes the language.

Not linear (sketch):

• Linear grammars restrict productions to at most one nonterminal on the right-hand side, which limits the ways symbols can be interleaved. Using the pumping properties for linear languages one can derive a contradiction for suitably chosen long words that require arbitrary interleavings of a's and b's to preserve equal counts. Hence the language is not linear.

Statement (ii): L = { a^n b^n } ∪ { a^n b^{2n} } is linear, but not deterministic context-free.

• Linear grammar producing the language (schematic): give two linear components and take their union via the start rule.

• For example, use nonterminals S, A, B with productions: S -> A | B, A -> a A b | ε (generates a^n b^n), B -> a B b b | ε (generates a^n b^{2n}). Each production has at most one nonterminal on the right, so the grammar is linear.

• Not deterministic context-free (intuition): a deterministic PDA reading a^n b^m must decide at the point it starts seeing b's whether m should equal n or 2n. That requires guessing which component of the union applies; a DPDA cannot in general make that global choice deterministically for all inputs, so the language is not recognized by any deterministic PDA.

Conclusion: Both statements are true — (i) is a deterministic CFL but not linear, and (ii) is linear but not deterministic context-free.