edited by
20,984 views
50 votes
50 votes

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?

  1. I and IV only
  2. I and II only
  3. II and III only
  4. II and IV only
edited by

9 Answers

1 votes
1 votes
For I to be cfl one more condition need to be satisfied along with m+p=n+q that is m>=n

Reference:

https://www.cs.utexas.edu/~cline/ear/automata/CS341-Fall-2004-Packet/3-SupplementaryMaterials/D-SuppContextFree.pdf

check page no 10 of pdf

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

Related questions

40 votes
40 votes
1 answer
3