CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?

  • $\begingroup$ DFAs have more than one bit of memory. They have $\log n$ bits, where $n$ is the number of states. $\endgroup$ – Yuval Filmus Feb 5 '14 at 2:45
  • $\begingroup$ I don't think your first sentence provides any useful intuition or fact. Regarding counting, see the linked question. $\endgroup$ – Raphael Feb 5 '14 at 8:02
  • 4
    $\begingroup$ I don't think this is a duplicate of a question about counting. I think 'structure of sentences' is meant to express syntactic structure (i.e. nested structures) while 'string structure' is flat. A possible answer is indeed that in derivations of a regular grammar we can only use one 'bit' of memory about what we've read thus far (the nonterminal we're rewriting). This is not quite the same as saying that we cannot count (which is a consequence). $\endgroup$ – reinierpost Feb 5 '14 at 10:01
  • 1
    $\begingroup$ @Raphael I do not think the two questions are related. I also think that, despite its error, this question is meaningful and useful to understand the role of grammars, why they were introduced, as opposed to what their mathematical properties are. In a nutshell, I do not think it should be on hold and I would like to answer it. $\endgroup$ – babou Feb 20 '14 at 10:51
  • $\begingroup$ let us continue this discussion in chat $\endgroup$ – Raphael Feb 21 '14 at 9:24