The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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.
asked in Theory of Computation by (169 points)
edited by | 60 views

2 Answers

+1 vote
Best answer

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.
answered by (147 points)
selected by
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.
0 votes
  • 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.
answered by Boss (34.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,793 questions
54,514 answers
75,183 users