I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems.

As someone who is somewhat unfamiliar with the language of the subject, the entry level explanations are often useless and more specific ones I frankly am unable to totally grasp.

I have been interested in the Chomsky-Schutzenberger enumeration theorem and its implications (in an analogue classical system), however the definition of “word length” (say, from Wikipedia) is lost on me: the expression for “the number of words of length k in L” is the “intersection of a context free L and”... what exactly is sigma in k-powers?

Furthermore, how is word length understood from the context of information theory (shannon entropies, message lengths, lossless encoding, etc.) and what are the implications of context free language and grammar in computer sciences?

I appreciate any responses!

  • 2
    $\begingroup$ It's a bit unclear what you are asking. Things like length of strings, grammars and CFGs have clear-cut, trivial and easily accessible definitions in introductory text on computer science. $\endgroup$ – Martin Berger Oct 9 '19 at 12:09

$\Sigma$ is the alphabet of the grammar and so $\Sigma^k$ is the set of words of length $k$ from that alphabet.

Finally $L\cap\Sigma^k$ is then the set of such words that are in $L$, i.e., that are generated by the grammar.

(This should probably be clarified in the Wikipedia entry in some fashion.)


Not the answer you're looking for? Browse other questions tagged or ask your own question.