Question

{w| w has equal number of a’s and b’s } is
A. regular
B. context-free but regular
C. context-sensitive but not context-free
D.type-0 but not context-sensitive

Answer 1

Answer on Question#38638 – Math - Other

For a string $w$ in $L = \{w \mid w$ has equal number of a's and b's $\}$, let $j$ and $k$ be the number of $a's$ and $b's$ in $w$ respectively. Then observe that $L$ consists of strings in which $j = k$, so $L$ consists of strings in which $j \neq k$, but that any two of these suffice by transitivity, so in particular we take $j \neq k$.

We can create a $PDA$ (pushdown automaton) and this $PDA$ accepts any string over the alphabet $\Sigma = \{a, b\}$ in which the number of $a's$ does not equal the number of $b's$ by only accepting if $j > k$ or $k > j$. Notice that $j > k$ or $k > j$ if and only if $j \neq k$.

CFLs (context-free languages) are closed under union, so the union of the two languages recognized by these PDAs are context free. We've already argued that the union of these two languages is $L$, so we conclude that $L$ is context free.

Answer: B.