FORMAL LANGUAGE & AUTOMATA THEORY

Answer

Correct Option: (ii) Context-free but not regular

Explanation

$L = \{ a^m b^n c^{m+n} \mid m,n \ge 1 \}$.

Not Regular

Use Pumping Lemma. Let $p$ be pumping length, $w = a^p b^p c^{2p} \in L$. Pumping $y$ in $a$ segment breaks $m+n$ balance.

Context-Free

PDA construction:

1. Push $a$’s (m times) → stack $= A^m$.
2. Push $b$’s (n times) → stack $= A^m B^n$ (or same symbol).
3. For each $c$, pop one symbol. Accept if empty after $m+n$ $c$’s and no extra input.

Alternatively grammar:
$S \rightarrow a S c \mid a T c$
$T \rightarrow b T c \mid b c$

This generates $a^m b^n c^{m+n}$.

Not context-sensitive requirement beyond; CFL suffices, but not regular. Not Type-0/1 only.

Final Answer

Context-free but not regular → Option (ii).

Answer

Correct Option: (iii) Context-sensitive but not context-free (and hence not regular)

Explanation

$L = \{ a^n b^n c^{n+m} \mid m,n \ge 1 \} = \{ a^n b^n c^{k} \mid k = n+m > n \}$.

Not Context-Free

Assume $L$ is CFL, let $p$ be pumping length. Take $w = a^p b^p c^{p+1} \in L$ ($n=p, m=1$). By pumping lemma for CFL, $w = uvxyz$ with $|vxy|\le p$, $|vy|>0$. Pumping must stay within first $p$ $a$'s or $b$'s or $c$'s. Any pumping changes counts and breaks condition $\#_c > \#_a = \#_b$ (or breaks $a^n b^n$). Formal proof shows $L$ not CFL. Equivalent to $a^n b^n c^n$ (which is not CFL) with extra $c^m$ tail; intersection with regular $a^*b^*c^*$ does not help but $L \cap a^*b^*c^p$ style shows non-CFL.

Context-Sensitive

It is accepted by Linear Bounded Automaton. Grammar is context-sensitive:

$S \rightarrow a S B C \mid a B C$
$CB \rightarrow BC$
$a B \rightarrow a b$
$b B \rightarrow b b$
$b C \rightarrow b c$
$c C \rightarrow c c$

This is Type-1 (CSG) but not Type-2. It is decidable but not CFL.

Final Answer

CSL but not CFL → Option (iii). Also not regular; ultimately Type-1 in Chomsky hierarchy.

Answer

Correct Option: (ii) $A \rightarrow \epsilon$

Explanation

Context-Sensitive Grammar (CSG, Type-1): Production $\alpha \rightarrow \beta$ where $\alpha,\beta \in (V\cup T)^*$ and $|\alpha| \le |\beta|$ (non-contracting), except possibly $S \rightarrow \epsilon$ with $S$ not appearing on RHS.

Check each:

• (i) $AB \rightarrow BA$ : $|\alpha|=2$, $|\beta|=2$ → $2 \le 2$ allowed (context-sensitive, length-preserving).
• (ii) $A \rightarrow \epsilon$ : $|\alpha|=1$, $|\beta|=0$ → $1 \le 0$ false, contracting, not allowed in CSG (unless $A=S$ and $S$ is start with special $\epsilon$ rule).
• (iii) $A \rightarrow a$ : $1 \le 1$ allowed.
• (iv) $aB \rightarrow ab$ : $2 \le 2$ allowed (context $a$).

Hence only $A \rightarrow \epsilon$ violates the monotonicity condition.

Final Answer

Not allowed: $A \rightarrow \epsilon$ → Option (ii).