GATE CSE 2018 | Question: 35

Question

Consider the following languages:

1. $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$
2. $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$
3. $\{a^mb^nc^pd^q \mid m=n =p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0 \}$
4. $\{a^mb^nc^pd^q \mid mn =p+q, \text{ where } m, n, p, q \geq 0 \}$

Which of the above languages are context-free?

• A. I and IV only
• B. I and II only
• C. II and III only
• D. II and IV only

Comments

$\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$

One of the grammars of above language was given in GATE1997-11.

---

For option (I), it can be written as m-n+p-q=0. This is easy to see as DCFL. Isn’t it?

---

@ rfzahid thanks this really clear my doubt. good work

 

Answer 1

Many might have marked B,but one must be able to rigorously prove it:

Why is 4 false?

Here we must know what m is.Multiplication can only be performed if we know one of its operands.There is no bound on m, and since you cannot count till infinity(counting requires a distinct state for each increment) and you cannot have infinite states counting is not possible.This can be done with the help of LBA

Why is 2 true?

We'll decompose the problem into 2 parts as we don't have to be deterministic.

Case 1:

m-n = p-q .Do,simple push and pop for 'a' and 'b' respectively.Now,if 'b' is one the stack terminate . else do the similar operation for 'c' and 'd' .Now compare the leftover 'a' with leftover 'c',this is again trivial.

Case 2: n-m = p-q can be done similarly.

Answer:b)

Comments

Can I  justify the first as cfl as write m + p = n + q

It can also be written in the form of m - q = n - p

I can interpret it as push a and b then for every c pop b and for every d pop a untill the stack is empty .Therefore it can be called as cfl am I correct

---

How counting requires a distinct state for each increment?

---

a3b4c2d1

 

can any one explain using the logic

Can I  justify the first as cfl as write m + p = n + q

It can also be written in the form of m - q = n - p

Answer 2

II is obviously CFL

for option IV as multiplication symbol is not given there we can consider it as concatenation

lets take example

a^30 b^5 c^200 d^105
now here m=30 n=5 p=200 q=105

mn=p+q is   305=305

now we can design pda as following

1)push 10 'a' for Each input 'a' in stack

2)push all b's in stack

now stack contains 305 a's and b's for above example

3)match all a and b in stack with input c and d

4)if stack is empty and input is null then accept otherwise reject

Hence OPTION D

Comments

Concatenation is defined for Languages (Sets of strings) and for Strings. There is no such thing as Concatenation of Decimal Numbers i.e. Powers.  Correct answer is B.

Answer 3

Check this out for the first language:

Answer 4

I don't think the options are correct(The numbering is wrong). But I can definitely say that I and II, both are CFL as you easily construct PDAs for them. You can easily count the m's, n's & p's, q's in them and them push/pop accordingly.

III is definitely not a CFL. You cannot construct a PDA for it as you have to ensure that m = n = p, that means counting 3 of them and it is also given that p does not equal q, so q can be anything.

So I hope you can figure out the answer(The options are incorrect I think. So, check out!) :)