The Gateway to Computer Science Excellence
+19 votes

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

in Theory of Computation by Veteran (52.2k points) | 1.2k views

4 Answers

+22 votes
Best answer

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 by
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 ..
+8 votes

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

by Boss (30.8k points)
+3 votes
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.
+2 votes
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 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
by Boss (14.4k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,341 answers
105,210 users