2022 Developer Survey is open! Take survey.

# Tag Info

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
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
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

### 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 ...

### 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
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

### 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

### 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
Accepted

• 269k
Accepted

• 4,889
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
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

### 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
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
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
Accepted

• 875
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
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 ...