0
$\begingroup$

I'm currently reading through Aho's "Theory of parsing, translation and compiling" on my own and I got a bit confused about the closure operator on language $L$ with alphabet $\Sigma$ ($L^*$). The book defines it recursively as follows:

\begin{align*} 1)\ L^0&=\{e\}\\ 2)\ L^n&=LL^{n-1}\quad \text{for } n\ge1\\ 3)\ L^*&=\bigcup_{n\ge0}{L^n} \end{align*}

What sort of set does this operation define? It seemed to me that it defines something like "the set of all possible concatenations of strings of language $L$". There wasn't an actual example in the chapter, I can't figure it out.

$\endgroup$
1
$\begingroup$

It does exactly what you describe: $L^*$ contains all possible finite concatenations of words in L, including the empty word. This operator is known as the Kleene star, it is fundamental in the theory of regular languages and more generally of grammars.

$\endgroup$
0
$\begingroup$

Yes, you're right. As an example, suppose your alphabet was $\sum = \{a,b\}$ and and you wanted to represent the set of all strings over $\sum$ where every $a$ is immediately followed by a $b$. Then $\{ab , b\}^*$ would give you such a set of strings since it contains exactly all the possible finite concatenations of $ab$ and $b$. If you're familiar with regex expressions, then it is very similiar to the $*$ operator used in that context.

$\endgroup$

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.