Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

# Tag Info

## Hot answers tagged kleene-star

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 ...
• 277k
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
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 ...
• 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 ...
• 7,088
6 votes
Accepted

• 277k
6 votes
Accepted

• 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 ...
• 277k
3 votes
Accepted

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 ### 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 ... • 277k 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 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.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 ... • 81.8k 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 ... 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,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 ... • 41 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 \... • 277k 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.8k 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

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