0 votes 0 votes Identify the type of the given language and draw the corresponding automata for the language. $L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$ A] Regular B] DCFL C] CFL but not DCFL D] Non-CFL Please describe your selection. Theory of Computation regular-grammar context-free-grammar npda dpda theory-of-computation + – anupamsworld asked Sep 2, 2022 anupamsworld 537 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply abhinowKatore commented Sep 2, 2022 reply Follow Share Is the answer [D] Non-CFL ? 0 votes 0 votes ankitgupta.1729 commented Sep 2, 2022 reply Follow Share Yes, It is not a Context – Free Language and it can be proved by Pumping Lemma for CFL. $L = \{a^i b^jc^k \ | \ j = \max (i,k), \ i,k >0\}$ Suppose, $L$ is context-free. Now, consider an element of set $L$ as $z=a^nb^{2n}c^{2n}$. Here $z \in L$ and $|z| \geq n; \ n >0$ Now, try to decompose $z$ as $z= uvtxy = a^{n-1}ab^{n-2}bb^{n+1}c^{2n}$ with $u=a^{n-1}, \ v=a, \ t=b^{n-2}, \ x=b, \ y = b^{n+1}c^{2n}$ Here, you can see, $|vtx| \leq n$ and $|vx| > 0$ Now, pump this string two times i.e. for $i=2,$ $uv^itx^iy = uv^2tx^2y = a^{n-1}a^2b^{n-2}b^2b^{n+1}c^{2n} = a^{n+1}b^{2n+1}c^{2n} \notin L$ So, Contradiction. Hence, L is not context-free. 1 votes 1 votes anupamsworld commented Sep 3, 2022 reply Follow Share @abhinowKatore @ankitgupta.1729 answer given is option D Not sure where exactly I am going wrong but I was thinking the given language as $L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=i \space\ or \space\ j=k \right \}$ Could you please correct why it is wrong to think like this. 0 votes 0 votes afroze commented Sep 3, 2022 reply Follow Share assume I=2, k=3 now j=2 according to your language bt wrt qsn it should be 3(max) 1 votes 1 votes shikhar500 commented Oct 20, 2022 reply Follow Share @ankitgupta.1729 can u prove this language non-cfl by other methods apart from pumping lemma ? 0 votes 0 votes Please log in or register to add a comment.