19
With only union and concatenation, you can't describe any infinite language. The union and concatenation can only produce finitely many strings. With only union and the Kleene star, you can't describe a language such as $L = \{ab\}$, because there's no way to concatenate an expression generating only $a$ with an expression generating only $b$. With only ...
19
A language is regular, by definition, if it is accepted by some DFA. (This is at least one common definition.) Can you think of a DFA accepting the language?
A well-known result (that is proved in many textbooks) states that the language of a regular expression is regular. Since $a^* b^*$ is a regular expression, its language must be regular (if you believe ...
14
$\{a^* b^*\}$ is a regular language, since it's generated by a regular expression.
The key difference between $L_* = \{a^* b^*\}$ and $L_= = \{a^n b^n\}$ is that $L_=$ requires counting the $a$'s and $b$'s to check whether there's the same number of them, whereas $L_*$ doesn't require any counting. Counting requires unbounded memory as the number grows ...
answered Apr 28 '16 at 21:25
Gilles 'SO- stop being evil'
37.4k7 gold badges101 silver badges166 bronze badges
13
If you consider now the powers of a language $W$ you have
$W^xW^y=W^{x+y}$ If you want this to be consistent over $\mathbb N_0$,
i.e. the non-negative integers, you have to define
$W^0=\{\epsilon\}$. If you took it to be $\emptyset$ you would have
$W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ including, among others,
for $x=1$. Thus we would have $W^1=W=\...
11
A perhaps more interesting question is that of star height. The other answer mentions that if you can't use star, then you can only generate finite languages. What if you are not allowed to nest stars (so something like $(a^*b^*c)^*$ is not allowed)? What if you are only allowed to nest stars two levels deep? $d$ levels deep? It turns out that for every $d$ ...
8
Short answer: Yes. $10100$ is included.
Long answer:
Let's go through how this particular set is constructed. First, the expression
$$
10^n
$$
(in this context) denotes a single string consisting of a $1$ followed by $n$ $0$s (so the string depends on one variable $n$). Then, the set
$$
\{10^n \mid n \ge 1\}
$$
denotes the set of strings $\{10, 100, 1000, ...
6
As chi pointed out in the comment, since $\varepsilon\in L^*$ and $\varepsilon$ may not belong to the new grammar, so adding $S\rightarrow SS$ does not always generate $L^*$. It makes more sense to ask whether it generates $L^+$, so the following answer focuses on $L^+$.
General Form
Consider the following grammar:
\begin{align}
S&\rightarrow aSb\\
S&...
6
$L^2 = LL = \{uv | u,v\in L\}$. In words, $L^2$ is a set of all strings that formed by concatenation of all strings from $L$. For instance, if $u=a^kb^k \in L$ and $v=a^tb^t \in L$ then $uv = a^kb^ka^tb^t$. That's why $L^2 =\{ a^{n_1}b^{n_1}a^{n_2}b^{n_2}\}$ for all $n_1, n_2 \geq 1$.
Similarly $L^3, L^4,\dots$
Example with a finite set: $L=\{ab, cd\}$. ...
5
A report by Aceto contains an axiomatization of the equational theory of regular expressions, called "classical" by Conway (Table 1 on page 5). One of the axioms is very similar to what you're after: $(a+b)^* = (a^*b)^*a^*$. Using these axioms, we can derive your identity as follows (using associativity (C3, C10) for free):
$$
\begin{align*}
(a+b)^* &= (...
5
Let me solve a simpler question first. Suppose we'd like to know
If $C$ is context-free, must $F(C)=\{w: ww \in C\}$ be context-free?
The answer is no: $F(\{a^i b^i c^j a^j b^k c^k\})=\{a^i b^i c^i\}$.
As for the original problem, consider the context-free language that contains words of the form $\{a^i b^i c^j d a^j b^k c^k d\}$ or those which don't ...
4
Yes, it is true. But the argument to support the conjecture is incorrect.
The correct proof is as follows: $L_1 \cap L_2 \subseteq L_1 $ and therefore $(L_1 \cap L_2)^* \subseteq L_1^*$. (argument: if $A \subseteq B$ then $A^* \subseteq B^*$).
Similarly $(L_1 \cap L_2)^* \subseteq L_2^*$.
Therefore $(L_1 \cap L_2)^* \subseteq (L_1^* \cap L_2^*)$ (argument:...
4
Another interesting case arises by allowing complementation as a possible operation.
Using union, concatenation and complement (but no star), one can obtain the language $A^*$ as the complement of the empty language. One can also obtain languages like $(ab)^*$ and $(a(ab)^*b)^*$ (not so easy to see if you don't know the trick), but there is no way to obtain $...
4
You're wrong about $L^+$:
$L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^* = \{\epsilon\}$
4
Your confusion seems to stem from the incorrect assumption that if a language $L$ has a certain property, then $L^*$ must also have that property. Consider this simpler example. Over the 1-symbol alphabet $\{a\}$ consider the property
$L$ contains no words of length more than three
Then one language with this property is $L=\{a, aaa\}$. Then by the ...
4
$L^*$ always exists. ${}^*$ is an operation on languages, just like ${}^2$ is an operation on numbers – whenever you have a number $x$, there is a number $x^2$ and, similarly, whenever you have a language $L$, there is a language $L^*$. Specifically, $L^*$ is the language of all strings that can be made by concatenating zero ...
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
If $\varepsilon \in L$, then necessarily $\varepsilon \in L^+$ (and the converse as well). This is because $L$ itself is contained in $L^+$ and $L^+$ is defined as the union over the powers $L^i$ of $L$ for $i \in \mathbb{N}_+$. Note $L^+$ is not defined as $L^\ast \setminus \{ \varepsilon \}$; this is a common mistake.
Hence, $\varepsilon \not\in L^+$ ...
3
Let $A$ be the language consisting of the following words:
$$
(u,v)|\Sigma^*|(v,w),
$$
where $u,v,w$ are numbers encoded in binary. This language is in $\mathsf{L}$.
Given a directed graph $G$, we can encode it as a list of edges in the following way:
$$
(x_1,y_1)(x_1,y_1)|(x_2,y_2)(x_2,y_2)|\cdots|(x_m,y_m)(x_m,y_m)
$$
where $x_i,y_i$ are vertex numbers ...
3
The concatenation of zero words from $\emptyset$ is the empty word $\epsilon$, so $\epsilon \in \emptyset^*$. More generally, for a language $L$, the Kleene star $L^*$ consists of all concatenation of any number of words from $L$, any number including zero words.
3
You can always use the current state of the automaton to remember the last three characters you've seen. Now, you can implement two phases. In the first phase, you're happy if you're ever in the situation where the last three characters were $010$. In the second phase, you become unhappy if you ever see $010$ again.
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
Simply saying that $L$ has the alphabet $\{x, y\}$ and that no string in $L$ contains the substring $xx$ doesn't define a single language - there are infinite such languages. What you call expressing $L = \{y, xy, yx\}$ is actually defining such a language $L$ with three words that happens to have the property of no strings containing $xx$. $L^*$ doesn't ...
2
Unless parentheses say otherwise, the customary precedence is ${}^*$ (like exponentiation), then concatenation (like multiplication), then union (like addition).
Your second example is the concatenation of starred expressions, so it does contain the empty string.
2
Kleene stars applies to the character(s) it belongs, so in your example the correct option is the 2° one.
ABB* = {AB, ABB, ABBB, ABBBB, ..}
A(BB)* = {A, ABB, ABBBB, ABBBBBB, ..}
2
What you have written (i.e., $\{ \varepsilon, 01, 0011, 000111, \ldots \}$) is simply $A$ itself.
(Assuming $A^\ast$ is the Kleene star operation) you cannot prove $A = A^\ast$ because it is not correct.
The Kleene star $A^\ast$ is defined as the union of the powers $A^i$, where $A^0 = \{ \varepsilon \}$ and $A^{i+1} = A^i \cdot A = \{ w \cdot w' \mid w \...
2
I figured out the answer and hope this will help anyone with similar confusion in the future.
Since a pushdown automaton is essentially a finite automaton with an extra component called the stack which is used for storage, if we are presented with a regular language like the one given above, we simply need to create a PDA that does not use the stack. This ...
2
I assume that in your definition $a \leq b$ iff $a + b = b$.
First, note that if $a \leq b$ and $b \leq a$, then $a = a + b = b + a = b$.
Therefore, in order to show that $a = b$, it is sufficient to show that $a \leq b$ and $b \leq a$.
Now, you want to show that $(a + b)^\ast = (a + ab + b)^\ast$. As explained in the previous paragraph, it is sufficient ...
2
Your language could be simplified as follows, using $\emptyset^* =\{\epsilon\}$:
$$
\begin{align*}
L(\emptyset\emptyset^*+\emptyset)
&=L( \emptyset . \{\epsilon\} + \emptyset) \\
&=L(\emptyset +\emptyset) & (\emptyset.\{\epsilon\}=\emptyset) \\
&=L(\emptyset) & (\emptyset + \emptyset = \emptyset)
\end{align*}
$$
So the language L ...
2
Here's a hint; your language is, more or less, the concatenation of three languages: the strings not containing 010, the language consisting of the single string 010, and the strings not containing 010.
Can you make a DFA which accepts all and only those strings not containing 010, perhaps as the complement of something?
When I said "more or less" above, I ...
Only top voted, non community-wiki answers of a minimum length are eligible
