1.2k views

The language $\left\{a^mb^nc^{m+n} \mid m, n \geq1\right\}$ is

1. regular

2. context-free but not regular

3. context-sensitive but not context free

4. type-0 but not context sensitive

| 1.2k views

Language is not regular bcoz we need to match count of $c$'s is equal to count of $b$'s $+$ count of $a$'s

and that can implement by PDA.

$\delta(q_0,a,\epsilon)= (q_0,a)$     [ push a in stack, as per language a comes first]

$\delta(q_0,a,a)= (q_0,aa)$     [push all $a$'s into stack]

$\delta(q_0,b,a) = (q_1,ba)$   [push $b$ in stack, state change to $q_1$ that sure b comes after $a$]

$\delta(q_1,b,b)=(q_1,bb)$   [push all $b$'s in stack]

$\delta(q_1,c,b) = (q_2,\epsilon)$   [ pop one $b$ for one $c$]

$\delta(q_2,c,b) = (q_2,\epsilon)$   [ pop one $b$'s for each $c$ and continue same ]

$\delta(q_2,c,a) = (q_3,\epsilon)$   [ pop one $a$ for one $c$ , when there is no more $b$ in stack]

$\delta(q_3,c,a) = (q_3,\epsilon)$   [pop one $a$ for each $c$ and continue same]

$\delta(q_3,\epsilon,\epsilon) = (q_f,\epsilon)$    [ if sum of $c$'s is sum of $a$'s and $b$'s then stack will be empty when there is no $c$ in input]

Answer is option B : language is context- free but not regular.

Note :1state changes make sure $b$'s comes after $a$ and $c$'s comes after $b$'s]

by Veteran (57k points)
edited
0
Sir what is the working of these step "∂(q2,c,b) = (q2,c)   [ pop one b's for each c and continue same ] " ?? i am not getting it as replacing b's with c ...
+1
you are right. there was a mistake at my end

did the required correction

$\delta (q_2,c,b) = (q_2,\epsilon )$
0
oK ... Sir try to give answers more quickly ... i mean gate is near ..
0
Ok .. I will try to ..

we can write this language as $$\left\{a^mb^nc^nc^m \mid m, n \geq1\right\}$$

this shows us clearly that we are performing only one comparison at a time. first between b and c then between a and c. Only one comparison at a time thing can be done easily using a PDA.

Hence, the language is Context Free but not regular. by