PDA | TOC | Practice Question

Question

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.

Comments

Is the answer [D] Non-CFL ?

---

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.

---

@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.

---

assume I=2, k=3

now j=2 according to your language bt wrt qsn it should be 3(max)

---

@ankitgupta.1729 can u prove this language non-cfl by other methods apart from pumping lemma ?