self made

Question

L={aⁿ bⁿ n>=0;n is not a multiple of 3}

(a) may or may not be a CFL.

(b).Is a DCFL and hence CFL

(c). is a CFL but not a DCFL.

(d). is Recursive but not CFL. Please explain with its solution...

Comments

Ans- B.Is a DCFL and hence CFL.

Answer 1

We want complement of L={a³ⁿ b³ⁿ} n>0

CFL is not closed under complement

So, the language may or may not be CFL

Ans A)

Comments

L={a3n b3n} n>0 is DCFL right. and we need to find complement of this DCFL is closed under Complementation .SO it is DCFL and hence CFL right?

We can do it like this for every 3 a's push an "x" into the stack and for every 3 b's pop out "x" and go to final state. This can be done by a DPDA. Hence DCFL. Complement of DCFL is also a DCFL.

---

Yes, it is DCFL and hence CFL. [B]

Grammar for this is G = ({S}, {a, b}, S, S → ab|aabb|aaaSbbb).

---

@srestha ma'am there is a mistake in the answer, I guess

As the complement of a^3nb^3n will also include the string 'aaaa', but according to the question the string 'aaaa'  should not belong to the language