0
$\begingroup$

For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has?
For example a DFA that accepts $\{w \in \{a,b\}^* : w \text{ contains } bbb\}$ should it reject the actual string $bbb$ because it does not contain an $a$?

$\endgroup$
  • 3
    $\begingroup$ What definition of $*$ do you use? $\endgroup$ – greybeard Feb 5 at 8:39
0
$\begingroup$

$\{a,b\}$ is set notation. The alphabet of a language is the set of all possible symbol used in the language. You can substitute the typical $\Sigma$ for the full set every time.

$\Sigma^*$ (where $^*$ is the kleene star) is the set of all possible strings you can make with that alphabet. That includes strings that happen to not use a certain character.

Therefor $\{w \in \{a,b\}^* : w \text{ contains } bbb\}$ is equivalent to $\{w \in \Sigma^* : \Sigma = \{a,b\} \text{ and } w \text{ contains } bbb\}$. But it skipped defining $\Sigma$ for terseness reasons.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.