# Tag Info

4

Clearly not. Let $A=\{a\}$ and $B=\{aa\}$. Now, $A\cap B = \emptyset$ so $(A\cap B)^* = \{\epsilon\}$ but $A^*\cap B^*=B^*=\{a^{2i} : i \in \mathbb{N}\}$ (all strings consisting of an even number of $a$).

3

It seems you have hit the reasoning correctly: A set $S$ is a subset of another set $A$ if $w\in S\implies w\in A$. Since you are trying to show that $\forall w \in A^+ \implies w \in A^*$, you are proving that $A^+ \subseteq A^*$. One more legant way to formally do this is by finding a bijection between the two sets. Since $|A^*|$ = $|\Bbb N|$ you need to ...

2

Given a language $L$, let $L_0 = \{\epsilon\}$ and, for $i\geq 1$, let $L_i = \{w_1\circ \dots\circ w_i \mid w_j\in L \text{ for each } j\}$, where $\circ$ denotes concatenation. Then the Kleene closure of $L$ is the language $L^* = \bigcup_{i\geq 0} L_i$.

2

The lexicographic order is defined on words, not on regular expressions. An interesting exercise is to describe the restriction of the lexicographic order to the language $a^*b^*$, assuming that $a < b$. Note for instance that $1 < a < a^2 < \dotsm < a^n < \dotsm$, but $\dotsm <a^nb <\dotsm <a^2b < ab < b$.

2

The "$x\in A^{+}$. By definition $x\in A^{+} \wedge x\in A^{*}$ for all $x\neq A^{0}$" is a bit weird. Not even from a computer science point of view but from a set theory or general mathematical point of view. First, you're saying the same thing again with "$x\in A^{+}$" which you shouldn't. Then, you're saying $x\in A^{*}$ which is the desired result. I ...

1

The first step is to clarify what is being asked: do you mean can every infinite regular language be decomposed in this way, or is it possible that some infinite regular language can be decomposed in this way? Your question does not make this clear. For the first version of the question, try considering the following language: $b \cup a^*$. Can this be ...

1

$printf "ab\n" | sed -En 's/b*// p' | od -t c 0000000 a b \n 0000003 This regex expression "$b*$" does match the empty string, which is zero '$b$', at the very front of the input "$ab$". This is in accordance with the definition of Kleene star since$b^*$stands for the language$\{\epsilon, b, bb, \cdots\}$, where$\epsilon\$ stands for the empty ...

Only top voted, non community-wiki answers of a minimum length are eligible