The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
613 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

asked in Theory of Computation by Veteran (69k points) | 613 views

4 Answers

+15 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 =  option B : language is context- free but not regular.

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

answered by Veteran (55.2k points)
edited ago 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 ..
+6 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

answered by Veteran (31k 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.
answered by Junior (855 points)
+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
answered by Veteran (14.3k points)


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

33,705 questions
40,253 answers
114,352 comments
38,862 users