Set Theory, Kleene Star & DNF

The questions for this tutorial are available here.

Powersets

The powerset is the set of all subsets. The number of elements in the powerset is: $2^n$.

This is all the different strings that can be produced with the characters in the alphabet. This includes the empty-string.

This is all binary strings including the empty-string:
- $\{0,1\}^*$
This is any number of the letter a including the empty-string:
- $a^n\vert n\geq 0$
This is only the empty-string:
- $\{\epsilon\}$

If we have the option to choose an element we must choose at least one. This is the same as the Kleene star operation but without the empty-string.

For $\{0,1\}^+$ this would be formally written as:

\[\\{0,1\\}\\{0,1\\}^*\]

One element followed by any number of elements.

Assume that we have $\{0,1\}^*$ and remove everything under the line:

stateDiagram-v2
direction LR
[*] --> A
A --> B:0
B --> D:1
D:D
D --> B:1
A --> C:1
C --> D:0
D --> A:0

0111010 - Accept
010011 - Reject
100 - Reject
11001 - Reject

If we are given a transition that doesn’t exist, this leads to a “dead” state. If it is not drawn acknowledge it’s existence.

$L1$ is a set of all words containing exactly three occurrences of $a$.

 stateDiagram-v2
 direction LR
 [*] --> A
 A --> B:a
 A --> A:b
 B --> C:a
 B --> B:b
 C --> D:a
 C --> C:b
 D --> D:b
 D:D

$L2$ is a set of all words containing at least three occurrences of $a$.

 stateDiagram-v2
 direction LR
     [*] --> A
 A --> B:a
 A --> A:b
 B --> C:a
 B --> B:b
 C --> D:a
 C --> C:b
 D --> D:a, b
 D:D

$L3$ is a set of words containing the sub-string $aaa$.

 stateDiagram-v2
 direction LR
     [*] --> A
 A --> B:a
 A --> A:b
 B --> A:b
 C --> A:b
 B --> C:a
 C --> D:a
 D --> D:a,b
 D:D