7,030 views

4 Answers

Best answer
31 votes
31 votes

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]

edited by
14 votes
14 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
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
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
Answer:

Related questions

59 votes
59 votes
4 answers
2
go_editor asked Apr 24, 2016
19,515 views
Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$\begin{array}{|l|l|c|} \hline \text {Instruction} & \text...
26 votes
26 votes
5 answers
4
Kathleen asked Sep 18, 2014
6,900 views
Choose the best matching between the programming styles in Group 1 and their characteristics in Group 2.$$\begin{array}{|ll|ll|}\hline \rlap{\textbf{Group 1}} & & \rlap{...