2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ DFAs have more than one bit of memory. They have $\log n$ bits, where $n$ is the number of states. $\endgroup$ 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$ 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