1
$\begingroup$

I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet?

Thank you so much!

$\endgroup$
2
  • $\begingroup$ We identify $\Sigma$ with the set of all words over $\Sigma$ of length $1$. Then $\Sigma^n$ is just the $n$-th power of the language $\Sigma$, a definition you must have seen in class. $\endgroup$ Dec 13 '20 at 16:31
  • $\begingroup$ For example, if $\Sigma = \{a,b\}$ then we identify $\Sigma$ with the language consisting of the words $a$ and $b$. $\endgroup$ Dec 13 '20 at 16:31
1
$\begingroup$

By definition $\Sigma^n$ is simply $\underbrace{\Sigma\times \Sigma \times \cdots \times\Sigma}_{n \ \text{times}} = \{(\sigma_1, \sigma_2, \ldots, \sigma_n): \forall \ i\in [n], \sigma_i \in \Sigma \}$ which is the set of ordered tuples of length $n$ over $\Sigma$. Usually, when we refer to a tuple $w = (\sigma_1, \sigma_2, \ldots, \sigma_n)$, we omit the commas "," and the parenthesis "(" and ")", so the tuple $w$ is written as $\sigma_1\cdot \sigma_2\cdots \sigma_n$ to which we refer as a word of length $n$ over $\Sigma$. In other words, $\Sigma^n$ is the set of all words of length $n$ over $\Sigma$.

Formally, the map that maps a tuple in $\Sigma^n$ to the word that we get by omitting the commas and the parenthesis from the tuples, is a bijection from $\Sigma^n$ to the words of length $n$ over $\Sigma$.

$\endgroup$
2
  • $\begingroup$ Thank you for the answers! If $n = 5$, could I have any words of length 2? $\endgroup$
    – Alireza
    Dec 13 '20 at 16:47
  • $\begingroup$ No. $\Sigma^5$ contains all words of length $5$, and only them. $\endgroup$ Dec 13 '20 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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