Self Doubt

Question

L= {a*b*c* – (a^nb^nc^n : n>=0)}

Explain whether it is Regular, CFL,DCFL.,CSL

Comments

csl i think

---

@Deepanshu

I think it should be CFL

---

how cfl ??
my view -----------regular- CSL = csl -csl =csl

---

yes it is CFL but not DCFL ===> CSL also

---

CSL ?

L = {a^p b*q c^r | p = q or q = r or p = r} + {a^p b^q c^r | p != q != r}

---

it is not cfl i think, please check

---

the question indirectly asking,

L = {$a^m . b^n .c^p \;|\; m = n\; and\; n = p$} ===> CSL

then L' is _______

---

csl

---

I think it is CSL

L={a^i.b^j,C^k | i=j and j!=k or i!=j and j=k or i!=j!=k}

to recognize this language we will need 2 stacks at least thus it in not CFL

---

IT WILL BE CSL   REG $\cap$ (CSL)${}'$

CSL IN COMPLEMENT IS CSL SO REG $\cap$ (CSL)  IT WILL BE CSL

---

no, will be NCFL

---

@srestha mam, will you please explain a bit more

---

$\text{CFL but not DCFL}.$

Check what kind of strings are present in the language-
$L = L_1 \cup L_2 \cup L_3\\L_1 = \{a^ p b^ q c^r | p\neq q \ and \ p,q,r \geq 0 \}\\L_2 = \{a^ p b^ q c^r | p\neq r \ and \ p,q,r \geq 0 \}\\L_3 = \{a^ p b^ q c^r | q\neq r \ and \ p,q,r \geq 0 \}$
All are $CFL's$ so their $union$ is also $CFL.$

---

Good point @Soumya29 👍

---

Soumya29 if it is cfl then it is csl also na.......

---

@Deepanshu

brother strongest answer should be CFL

if it is CFL ,then it is CSL,recursive, recursive enumerable also!

---

hmm :)