Ace Book closed

Question

The complement of the language L containing an equal number of a's , b's and c's is

a)regular

b)context free

c)context sensitive but not context free

d)recursive and not a CFL

Comments

my ans is  c but the correct ans is b.

my approach : since the language is CSl . CSL is closed under Complementation. Therefore , it must be CSL only.

---

the complement of the given language can be think as

number of a=number of b OR number of b=number of c OR number of c = number of a

OR all three can be anything

All these are CFL ,hence CFL!

---

himgta your complementation is incorrect 

Complement of L is

(number of a's $\neq$ number of b's) OR (number of c's $\neq$ number of b's) OR (number of a's $\neq$ number of c's)

---

himgta But how can we ensure that all 3 are not of equal number?

---

abhishek1995_cse complement of CSL is CSL that's true but every CFL is also a CSL. So that's not the right way to do it. 

 

---

@Mk Utkarsh

Yes right.. But how can we have a PDA for this? :/ Please show

---

@Mk Utkarsh

sir in the language all three are equal....in its complement either two of them can be equal

isin't it?

for ex: if aabbcc belong to L

then abbcc belongs to complement of L?

please clarify!

---

himgta yes all strings where (number of a's ≠ number of b's) OR (number of c's ≠ number of b's) OR (number of a's ≠ number of c's) is true. 

on seeing first symbol push 2 symbols for that symbol and pop just one on seeing other 2 symbols

for ex : aabbc
 

aabbc , stack:
aabbc , stack: aa
aabbc, stack : aaaa
aabbc, stack : aaa
aabbc, stack : aa
aabbc, stack : a

if stack is empty after parsing the string then string is not in language.

if stack becomes empty while parsing the string then the next symbol seen will be pushed two times and other 2 symbols will pop.