theory of computation

Question

  

L = (a^n b^n a^n | n = 1,2,3)  is an example of a language that is

A.	context free
B.	not context free
C.	not context free but whose complement is CF
D.	both (b) and (c)

Answer 1

If n is only 1,2,3

Then it is regular language as it is finite language therefore it is context free

If n= 1,2,3....

Then

Not context free

Because

We require two stack

Whenever occurence a comes push in one stack

Then occurence b comes push in 2nd stack

And pop one a and one b  from the stack for occurrence of a

Comments

answer was given as option c)

can you also explain how the complement is Context free?

Answer 2

n= 1,2,3 Thats it? or 1,2,3.......?

IF n=1,2,3 then Regular hence Context Free..  Option A

If n=1,2,3...... then  not context free.   Option B

Comments

option c was mentioned as the answer.I understood now that the complement would be n =1,2,3 hence complement is context free. Thanks

---

C was the given ans ?

---

yea edit your answer to avoid confusion

---

But still I am confused.. how the complement of it can be CFL when it is not CFL !
Tell me the logic ... how its complement can be CFL ?

Answer 3

Since n is finite , the language will have finite cases and can be represented by DFA, making it a regular language.

All the regular languages are context free languages.

Complement of a regular language is regular.

Therefore its complement is also context free.

If the question is correctly put , Answer is (a).