20
votes
Accepted
Will $L = \{a^* b^*\}$ be classified as a regular language?
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 ...
- 269k
19
votes
Accepted
Regular languages that can't be expressed with only 2 regex operations
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 ...
- 875
15
votes
Accepted
Kleene star operation on the empty language
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\}$. ...
- 19.1k
14
votes
Will $L = \{a^* b^*\}$ be classified as a regular language?
$\{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 ...
11
votes
Regular languages that can't be expressed with only 2 regex operations
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 ...
- 269k
11
votes
Accepted
Is it true that if L* is recursive, L is also recursive?
No.
Take any language $L$ over $\Sigma = \{0, 1\}$ that contains 0 and 1. Then $L^* = \Sigma^*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively ...
- 13.6k
8
votes
Does the set $\{10^n \mid n\geq1\}^*$ include $10100$?
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 ...
- 5,144
6
votes
Does adding S->SS in a context-free grammar change the language to its Kleene star?
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 ...
- 7,249
6
votes
Accepted
Finding $L^*$ when $L=\{a^nb^n | n \geq 1\}$
$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^...
- 9,592
6
votes
Accepted
Proving $(a+b)^* = b^*(ab^*)^*$ equationally
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: $...
- 269k
5
votes
Accepted
Is a kind of reverse Kleene star of a context-free language context-free?
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^...
- 3,461
4
votes
Accepted
How to determine if a regular language L* exists
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 ...
- 14.5k
4
votes
How to determine if a regular language L* exists
$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, ...
- 80.1k
4
votes
Is the Kleene star of an intersection contained in the intersection of Kleene stars?
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: ...
- 4,697
4
votes
Regular languages that can't be expressed with only 2 regex operations
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 ...
- 5,925
4
votes
Accepted
Kleene star Empty language
You're wrong about $L^+$:
$L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^* = \{\epsilon\}$
- 1,348
4
votes
Is the Kleene star of an intersection always equal to the intersection of kleene stars?
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 ...
- 11k
3
votes
Accepted
How is $L^* - \{\epsilon \} \neq L^+$?
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 $...
- 4,889
3
votes
Accepted
Prove that $L$ is closed under Kleene star iff $L=NL$
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 ...
- 269k
3
votes
Accepted
Kleene star differences
Unless parentheses say otherwise, the customary precedence is ${}^*$ (like exponentiation), then concatenation (like multiplication), then union (like addition).
Your second example is the ...
- 13.6k
3
votes
Kleene star operation on the empty language
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 ...
- 269k
3
votes
Accepted
DFA & RE from descriptive definition of given regular language
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 ...
- 80.1k
3
votes
Accepted
Prove, that $A^+\subseteq A^*$ where $A$ is a formal language
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 ...
- 1,035
3
votes
Accepted
Why do we need two variables for implementing kleene star operation on a language using context free grammars?
In the general case, your grammar generates more words than those in $L^*$. Consider this grammar:
$$
\begin{array}{l}
S \to A
\\
A \to (S)\ |\ a
\end{array}
$$
The above grammar generates $L =...
- 14.1k
2
votes
Is the set of all strings over a finite alphabet finite?
The star operator is a unary operator known as Kleene star (or Kleene closure) and the result of its application on $\Sigma$ (an arbitrary set of strings) is another set that contains all possible ...
- 220
2
votes
Prove the language of all concatenations of words in a regular language is regular
I have to guess about your definition of a regular language (I can't comment to ask yet...), so I will assume the following:
A language $L$ is regular over an alphabet $\Sigma$ if and only if it ...
- 121
2
votes
How to determine if a regular language L* exists
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 $...
- 875
2
votes
Accepted
To which character or characters does a Kleene star apply?
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, ..}
- 581
2
votes
Accepted
How to Apply Elementary Axioms from Kleene Star to an Inequality
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 ...
- 196
2
votes
Nondeterministic PDA for the following language with Kleene star
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 ...
- 560
Only top scored, non community-wiki answers of a minimum length are eligible