The Gateway to Computer Science Excellence

+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]

+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**

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,341 answers

198,451 comments

105,210 users