Theory Of Computation Doubt.

Question

I saw some where that a language which accepts $a^{n^{2}} | n \geq1$ is not context free Language and not regular language.

is it not a language that has at least one $'a'$ as the string?. It should be regular as well according to this Logic right. Please correct me if wrong.

Answer 1

Hi,

I got your confusion. You might be thinking that since 'a' is the only element in the Language. So any power 'a' is raised to must result in either Regular Language or CFL.

But please check for other values of n for L = a ^ (n^2) / n >=1

n=1  L = a

n=2 L = aaaa

n=3 L = aaaaaaaaa

: : : : : : : :: : : : :: : : : :

Thus I don't think there will be any pattern for Regular Expression to be created. Means you can't create the Regular expression as a* which you might be thinking of or neither of any other Regular expression justifies it.

Also for CFL, we need to push the 'a' to the push into the stack but we are not sure when to pop the 'a' from the stack or in simple terms we are not sure how to compare them.

Take the example of 'aaaa' you will push 2 a's then pop 2 a's to compare that they are equal but when the string is 'aaaaaaaaa' for n = 3 this logic fails.

 

I think this Language must be implemented by LBA(Linear Bounded Automata thus it is CSL)

Hope you might have got it.

Please ask if require more clarification.

Comments

If any pattern which is not in A.P.(arithmetic progression) can't be in regular.

$a^{n^2}$ =($a^2,a^4,a^9...$ ) as we can see pattern not in AP so can't be regular.

---

Yes, that is correct logic but only for finding whether it is regular or not.

Answer 2

• It is not CFL. It is CSL.

• Regular expression for atleast one a is " aa*". And it gives string like aa,aaa . But given language is not genrate .So how can you say is is atleast one a.