Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have the following context-free grammar:

$ S = A \\ A = aA $

Will the resulting language be context-free?

If it is, this would also mean a Turing machine should be able to produce it, since it's higher in the hierarchy. But how? Wouldn't it infinite loop?

If it is not, does that mean that there are certain context-free grammars that do not produce a context-free language? This seems bizarre.

share|cite|improve this question
The resulting language is empty, hence regular. – Brian M. Scott Feb 10 '13 at 23:39
Empty? Does it not contain the string aaaaa.... of infinite length? – Georgios Bitzes Feb 10 '13 at 23:42
No: languages in this sense are subsets of $\Sigma^*$, where $\Sigma$ is some finite alphabet, and $\Sigma^*$ is by definition the set of finite strings over $\Sigma$. People have dealt with languages of infinite words, and there are generalizations of the hierarchy, but that’s not what’s meant when one talks simply of regular or context-free languages, or languages recognized by Turing machines. – Brian M. Scott Feb 10 '13 at 23:45
This makes sense. Thank you! – Georgios Bitzes Feb 10 '13 at 23:51
You’re welcome! – Brian M. Scott Feb 10 '13 at 23:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.