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 ...
Yuval Filmus's user avatar
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 ...
DylanSp's user avatar
  • 865
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 ...
Gilles 'SO- stop being evil''s user avatar
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 ...
Yuval Filmus's user avatar
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 ...
vonbrand's user avatar
  • 14k
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 ...
Caleb Stanford's user avatar
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^...
sdcvvc's user avatar
  • 3,491
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 ...
xskxzr's user avatar
  • 7,455
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^...
fade2black's user avatar
  • 9,837
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: $...
Yuval Filmus's user avatar
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: ...
Sarvottamananda's user avatar
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 ...
J.-E. Pin's user avatar
  • 6,159
4 votes
Accepted

Kleene star Empty language

You're wrong about $L^+$: $L = \emptyset \rightarrow L^+ = \emptyset$, but $L = \emptyset \rightarrow L^* = \{\epsilon\}$
Mike B.'s user avatar
  • 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 ...
rici's user avatar
  • 12k
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 ...
David Richerby's user avatar
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 $...
dkaeae's user avatar
  • 5,017
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 ...
Yuval Filmus's user avatar
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 ...
Yamar69's user avatar
  • 1,073
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 =...
chi's user avatar
  • 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, ..}
Ack.'s user avatar
  • 591
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 ...
Andrey Tyukin's user avatar
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 ...
Sean's user avatar
  • 570
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 ...
Yuval Filmus's user avatar
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 ...
dkaeae's user avatar
  • 5,017
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(\...
rballiwal's user avatar
  • 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 ...
Rick Decker's user avatar
  • 14.8k
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 ...
David Richerby's user avatar
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 &...
J.-E. Pin's user avatar
  • 6,159
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 ...
yankovs's user avatar
  • 41

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