2022 Developer Survey is open! Take survey.
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 ...
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 ...
user avatar
  • 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\}$. ...
user avatar
  • 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 ...
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 ...
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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^...
user avatar
  • 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: $...
user avatar
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^...
user avatar
  • 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 ...
user avatar
  • 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, ...
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: ...
user avatar
  • 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 ...
user avatar
  • 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\}$
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
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 ...
user avatar
  • 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 =...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
  • 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, ..}
user avatar
  • 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 ...
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 ...
user avatar
  • 560

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