<p><span class="math-container">$\Sigma$</span> is the alphabet of the grammar and so <span class="math-container">$\Sigma^k$</span> is the set of words of length <span class="math-container">$k$</span> from that alphabet.</p>

<p>Finally <span class="math-container">$L\cap\Sigma^k$</span> is then the set of such words that are in <span class="math-container">$L$</span>, i.e., that are generated by the grammar.</p>

<p>(This should probably be clarified in the Wikipedia entry in some fashion.)</p>

CC BY-SA 4.0
2019-10-08T23:41:01.287Z
2019-10-08T23:41:01.287Z
Bjørn Kjos-Hanssen
<p>I am classically trained in physics, however I have been interested in the use of information theory in studying some classical systems. </p>

<p>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.</p>

<p>I have been interested in the <a href="https://en.m.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem" rel="nofollow noreferrer">Chomsky-Schutzenberger enumeration theorem</a>
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? </p>

<p>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?</p>

<p>I appreciate any responses!</p>

CC BY-SA 4.0
2019-10-09T12:09:11.580Z
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.
Martin Berger
<cc.complexity-theory><co.combinatorics><fl.formal-languages><pl.programming-languages>
Chomsky-Schutzenberg Hierarchies explained for physicist (general)
user54963
# Chomsky-Schutzenberg Hierarchies explained for physicist (general)

(Asked by: username_0 on 2019-10-08)

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](https://en.m.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_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!

**Tags:** cc.complexity-theory, co.combinatorics, fl.formal-languages, pl.programming-languages
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2019-10-08. Score: 3

$\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.)


---

