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 ...
12
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
$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\}$. ...
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&...
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
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
You're wrong about $L^+$:
$L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^* = \{\epsilon\}$
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 $...
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
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:...
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.
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 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
You can look at the length of words.
Any element of $A^+$ is a concatenation
$$ a_1 a_2 \ldots a_n $$
where $a_i \in A$ and $n \geq 1$. The length of such a word is
$$ L(a_1 a_2 \ldots a_n) = L(a_1) + L(a_2) + \ldots + L(a_n) $$
But the length is always nonnegative; for example,
$$ 0 \leq L(a_1) \leq L(a_1) + L(a_2) + \ldots + L(a_n)$$
If you're given ...
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
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 ...
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$.
1
It looks like you are on the wrong track.
While it is trivially true that $(L_1^*L_2^*)^{(0)} = \lambda = (L_1\cup L_2)^{(0)}$ where $\lambda$ is the language consisting of the empty word, it is more often than not that $(L_1^*L_2^*)^{(1)}\neq (L_1\cup L_2)^{(1)}$. For example, if either $L_1$ or $L_2$ has a non-empty words, the left side $(L_1^*L_2^*)^{(...
Only top voted, non community-wiki answers of a minimum length are eligible
