Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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 (...
Hendrik Jan's user avatar
  • 30.8k
1 vote
Accepted

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

$a^*b = (a^*)\cdot b$ $(a^*b)^* = \{\varepsilon\} \cup \{a,b\}^* b$
Hendrik Jan's user avatar
  • 30.8k
1 vote

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

If $A$ and $B$ are indeed meant to be alphabets here, they would contain only symbols, and your counterexample isn't valid. In fact, if $A$ and $B$ are alphabets, the claim is true. However, I would ...
Arno's user avatar
  • 3,103

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