mathematics:languagesandgrammar

Languages and Grammar

If $L$ is a language, then the product $L \cdot L$ is denoted by $L^2$. The language product $L^n$ for every $n \in \{0,1,2,…\} is defined as follows:

$$ \begin{aligned} L^0 &= \{\Lambda\} \\ L^n &= L \cdot L^{n-1}, \text{if} \ n > 0 \end{aligned} $$

Example. If $L = \{a,bb\}$ then the first few powers of $L$ are… $$ \begin{aligned} L^0 &= \{\Lambda\} \\ L^1 &= L = \{a,bb\} \\ L^2 &= L \cdot L = \{aa,abb,bba,bbbb\} \\ L^3 &= L \cdot L^2 = \{aaa,aabb,abba,abbbb,bbaa,bbabb,bbbba,bbbbbb\} \end{aligned} $$

If L is a language over $\Sigma$ (i.e. $L \subset \Sigma^{\ast}$) then the closure of $L$ is denoted $L^{\ast}$, and the positive closure of $L$ is denoted $L^+$.

$$ \begin{aligned} L^{\ast} &= L^0 \cup L^1 \cup L^2 \cup ... \\ L^+ &= L^1 \cup L^2 \cup L^3 \cup ... \end{aligned} $$

The closure of $\Sigma$ coincides with out definition of $\Sigma^{\ast}$ as the set f all string over $\Sigma$. In other words, we have a nice representation of $\Sigma^{\ast}$ as follows:

$$ \Sigma^{\ast} = \Sigma^0 \cup \Sigma^1 \cup \Sigma^1 \cup ... $$

Where $\Sigma^k$ denotes the set of strings of length $k$, each of whose symmbols in $\Sigma$.

  • mathematics/languagesandgrammar.txt
  • Last modified: 2024/10/09 15:12
  • by tami