Skip to main content
made r0 formally more precise
Source Link
blk
  • 351
  • 1
  • 8

You can define the semantics of the Kleene star $r^*$ of a regular language $r$ as a least fixed point. The carrier set $L$ would be the set of all languages (over a fixed alphabet $\Sigma$), i.e. $\textrm{Pow}(\Sigma)$, the partial order would be subset/language inclusion. The least element in this order is $\emptyset$.

Then your function $f$ would map languages to languages as follows: $$f(s) ~{}={}~ s \cup \{\varepsilon\} \cup s \cdot r$$ That is, $f$ takes as input a language $s$ and adds to it the empty word $\varepsilon$ as well as $s$ concatenated with $r$.

Now if you start the Kleene iteration of $f$ from the least element $\emptyset$, you get \begin{align*} f^0(\emptyset) &~{}={}~ \emptyset\\ f(\emptyset) &~{}={}~ \emptyset \cup \{\varepsilon\} \cup \emptyset \cdot r ~{}={}~ \{\varepsilon\}\\ f^2(\emptyset) &~{}={}~ \{\varepsilon\} \cup \{\varepsilon\} \cup \{\varepsilon\} \cdot r ~{}={}~ \{\varepsilon\} \cup r\\ f^3(\{\varepsilon\} \cup r) &~{}={}~ \{\varepsilon\} \cup r \cup \{\varepsilon\} \cup \bigl(\{\varepsilon\} \cup r\bigr) \cdot r ~{}={}~ \{\varepsilon\} \cup r \cup r\cdot r\\ \vdots\\ f^n(\emptyset) &~{}={}~ \bigcup_{0 \leq k \leq n} r^k \end{align*} where $r^0 = \varepsilon$$r^0 = \{\varepsilon\}$.

You can define the semantics of the Kleene star $r^*$ of a regular language $r$ as a least fixed point. The carrier set $L$ would be the set of all languages (over a fixed alphabet $\Sigma$), i.e. $\textrm{Pow}(\Sigma)$, the partial order would be subset/language inclusion. The least element in this order is $\emptyset$.

Then your function $f$ would map languages to languages as follows: $$f(s) ~{}={}~ s \cup \{\varepsilon\} \cup s \cdot r$$ That is, $f$ takes as input a language $s$ and adds to it the empty word $\varepsilon$ as well as $s$ concatenated with $r$.

Now if you start the Kleene iteration of $f$ from the least element $\emptyset$, you get \begin{align*} f^0(\emptyset) &~{}={}~ \emptyset\\ f(\emptyset) &~{}={}~ \emptyset \cup \{\varepsilon\} \cup \emptyset \cdot r ~{}={}~ \{\varepsilon\}\\ f^2(\emptyset) &~{}={}~ \{\varepsilon\} \cup \{\varepsilon\} \cup \{\varepsilon\} \cdot r ~{}={}~ \{\varepsilon\} \cup r\\ f^3(\{\varepsilon\} \cup r) &~{}={}~ \{\varepsilon\} \cup r \cup \{\varepsilon\} \cup \bigl(\{\varepsilon\} \cup r\bigr) \cdot r ~{}={}~ \{\varepsilon\} \cup r \cup r\cdot r\\ \vdots\\ f^n(\emptyset) &~{}={}~ \bigcup_{0 \leq k \leq n} r^k \end{align*} where $r^0 = \varepsilon$.

You can define the semantics of the Kleene star $r^*$ of a regular language $r$ as a least fixed point. The carrier set $L$ would be the set of all languages (over a fixed alphabet $\Sigma$), i.e. $\textrm{Pow}(\Sigma)$, the partial order would be subset/language inclusion. The least element in this order is $\emptyset$.

Then your function $f$ would map languages to languages as follows: $$f(s) ~{}={}~ s \cup \{\varepsilon\} \cup s \cdot r$$ That is, $f$ takes as input a language $s$ and adds to it the empty word $\varepsilon$ as well as $s$ concatenated with $r$.

Now if you start the Kleene iteration of $f$ from the least element $\emptyset$, you get \begin{align*} f^0(\emptyset) &~{}={}~ \emptyset\\ f(\emptyset) &~{}={}~ \emptyset \cup \{\varepsilon\} \cup \emptyset \cdot r ~{}={}~ \{\varepsilon\}\\ f^2(\emptyset) &~{}={}~ \{\varepsilon\} \cup \{\varepsilon\} \cup \{\varepsilon\} \cdot r ~{}={}~ \{\varepsilon\} \cup r\\ f^3(\{\varepsilon\} \cup r) &~{}={}~ \{\varepsilon\} \cup r \cup \{\varepsilon\} \cup \bigl(\{\varepsilon\} \cup r\bigr) \cdot r ~{}={}~ \{\varepsilon\} \cup r \cup r\cdot r\\ \vdots\\ f^n(\emptyset) &~{}={}~ \bigcup_{0 \leq k \leq n} r^k \end{align*} where $r^0 = \{\varepsilon\}$.

Source Link
blk
  • 351
  • 1
  • 8

You can define the semantics of the Kleene star $r^*$ of a regular language $r$ as a least fixed point. The carrier set $L$ would be the set of all languages (over a fixed alphabet $\Sigma$), i.e. $\textrm{Pow}(\Sigma)$, the partial order would be subset/language inclusion. The least element in this order is $\emptyset$.

Then your function $f$ would map languages to languages as follows: $$f(s) ~{}={}~ s \cup \{\varepsilon\} \cup s \cdot r$$ That is, $f$ takes as input a language $s$ and adds to it the empty word $\varepsilon$ as well as $s$ concatenated with $r$.

Now if you start the Kleene iteration of $f$ from the least element $\emptyset$, you get \begin{align*} f^0(\emptyset) &~{}={}~ \emptyset\\ f(\emptyset) &~{}={}~ \emptyset \cup \{\varepsilon\} \cup \emptyset \cdot r ~{}={}~ \{\varepsilon\}\\ f^2(\emptyset) &~{}={}~ \{\varepsilon\} \cup \{\varepsilon\} \cup \{\varepsilon\} \cdot r ~{}={}~ \{\varepsilon\} \cup r\\ f^3(\{\varepsilon\} \cup r) &~{}={}~ \{\varepsilon\} \cup r \cup \{\varepsilon\} \cup \bigl(\{\varepsilon\} \cup r\bigr) \cdot r ~{}={}~ \{\varepsilon\} \cup r \cup r\cdot r\\ \vdots\\ f^n(\emptyset) &~{}={}~ \bigcup_{0 \leq k \leq n} r^k \end{align*} where $r^0 = \varepsilon$.