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 ...
- 14.1k
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 ...
- 7,158
6
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,501
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,564
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: $...
- 278k
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,877
4
votes
Accepted
Kleene star Empty language
You're wrong about $L^+$:
$L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^* = \{\epsilon\}$
- 1,368
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 ...
- 12.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,073
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 ...
- 82.1k
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 $...
- 5,027
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 ...
- 278k
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.6k
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, ..}
- 591
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 ...
- 570
2
votes
Accepted
Find the number of strings in the language $(∅∅^∗ + ∅)$
Your language could be simplified as follows, using $\emptyset^* =\{\epsilon\}$:
$$
\begin{align*}
L(\emptyset\emptyset^*+\emptyset)
&=L( \emptyset . \{\epsilon\} + \emptyset) \\
&=L(\...
- 329
2
votes
DFA & RE from descriptive definition of given regular language
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 ...
- 14.9k
2
votes
Accepted
Meaning of L* if L is a language
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 ...
- 82.1k
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
Accepted
DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
The DFA starts by reading the first two characters. If they happen to be the same, then it goes to an accepting state and just stays there. Otherwise, it keeps track of the last two characters of the ...
- 278k
2
votes
Proving $A^\ast = A$ on a given set
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 ...
- 5,027
2
votes
Prove, that $A^+\subseteq A^*$ where $A$ is a formal language
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 ...
- 41
2
votes
Accepted
Lexicographic Order of Expression [Automata Theory]
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 &...
- 6,189
2
votes
Accepted
Characterization about Kleene Closure, when is a language $L=L^*$?
What your argument actually shows is
$$
L = L^* \Rightarrow L=L^2 \Rightarrow L = L^+.
$$
Indeed, suppose that $L = L^*$. On the one hand, $L^2 \subseteq L^* = L$. On the other hand, since $\epsilon \...
- 278k
2
votes
Accepted
Is the class of star-free languages just the complement to counter languages within the regular language class?
These languages families are related by similar names only, both formalisms have their own relation to the concept of counting.
The beauty of regular languages is that they can be defined using (...
- 30.9k
1
vote
Can an infinite regular language be decomposed in this way?
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 ...
- 7,158
1
vote
Kleene star operations
Hint:
You are right on (a). The proof involves key results for Kleene star as follows.
$$
\Sigma^{*}=\bigcup_{n\geqslant1}\Sigma^{n}\quad\text{and}\quad L\Sigma^{*}=\bigcup_{n\geqslant1}L\Sigma^{n}\...
- 148
1
vote
Accepted
Kleene Star regex question, sed behavior?
$ 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 ...
- 39.1k
Only top scored, non community-wiki answers of a minimum length are eligible