GATE CSE 2004 | Question: 87

Question

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

• A. regular

• B. context-free but not regular

• C. context-sensitive but not context free

• D. type-0 but not context sensitive

Comments

It's DCFL -> CFL

Answer 1

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]

Comments

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 ...

---

you are right. there was a mistake at my end

did the required correction

$\delta (q_2,c,b) = (q_2,\epsilon )$

---

oK ... Sir try to give answers more quickly ... i mean gate is near ..

---

Ok .. I will try to ..

Answer 2

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.

answer = option B

Answer 3

It is a context free language as PDA is possible for this language.

Push a on to the stack push b on to the stack and then pop c as c = a+b after all pop stack should be empty.

Answer 4

Keep on pushing a and b to the stack until you encounter a c.when a c is encountered then just start poping elements from stack if the stack gets emptied then this string is accepted by the machine which is called pda it accepts cfl..it is not regular because we will never come up with a dfa for this language and this is also context sensitive because cfl is a subset of csl so b is the correct option