# Questions tagged [kleene-star]

The tag has no usage guidance.

54 questions
Filter by
Sorted by
Tagged with
1 vote
37 views

### Is the class of star-free languages just the complement to counter languages within the regular language class?

So I'm kind of confused as I'm not that deep into the algebraic theory of languages. The wikipedia article states: Another way to state Schützenberger's theorem is that star-free languages and ...
1 vote
78 views

### Is (a*b) or (a*b)* star-free?

Here is the proof of a∗ being star-free: $\Sigma* = \bar{\emptyset}$ $A∗= \overline{Σ∗(Σ∖A)Σ∗}$ Would this be a proof for $a * b$? : $A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)}$ For $(A * B )*$ it seems more ...
30 views

### Languages: Prove or Disprove that $A^* = B^* \rightarrow A=B$

A colleague and I with pretty low-grade practical backgrounds decided it's time to try learning theory. This question is asked in a slide-deck he tracked down somewhere or another online without an ...
49 views

### Why does "NP is closed under Kleene star" proof reject correct word? [duplicate]

Show that P and NP are closed under Kleene star. I found possible solutions to these problems, more specifically: P - finding all subwords from a giving word and looking if there is a connection ...
352 views

### Are regular expression a* and a.a* equal?

a* = {λ, a, aa, aaa, aaaa.....} a.a* = a.{λ, a, aa, aaa, aaaa.....} = {a, aa, aaa, aaaa, aaaaa....} Then these two regular expressions above should not be equivalent. Please correct me if i am wrong.
151 views

• 21
3k views

### Regular languages that can't be expressed with only 2 regex operations

I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular ...
• 383