Formal Notation - A simple example

Question

I'm taking Formal Languages and Automata Theory course and i couldn't understand the notation below. Can someone explain me this please?

$\{ d \mid d \in \{ b f \mid b, f \in \{ a, c, e \} \} \}$

Answer 1

$\{x|P\}$ where $P$ is some collection of conditions means the set of all $x$ such that $x$ satisfies all the conditions in $P$. Expanding this into what you have written, we have $\{bf\,|\,b,f\in\{a,c,e\}\}$ means the set of all elements $bf$ where each of $b$ and $f$ are elements of $\{a,c,e\}$. Finally, $\{d|\,d\in \{bf\,|\,b,f\in\{a,c,e\}\}\}$ means the set of all elements $d$ such that $d$ is an element of the set we just described.

We can even describe these sets explicitly (because they are finite objects). $$\{bf\,|\,b,f\in\{a,c,e\}\}=\{aa,ac,ae,ba,bc,be,ea,ec,ee\},$$ and $$\{d|\,d\in \{bf\,|\,b,f\in\{a,c,e\}\}\}=\{d|\,d\in \{aa,ac,ae,ba,bc,be,ea,ec,ee\}\}\\=\{aa,ac,ae,ba,bc,be,ea,ec,ee\}$$

Answer 2

It's frequently helpful to read these from the inside to the outside:

• Let $b$ and $f$ be single letters from the list "a,c,e".
• Construct the set of strings $bf$ where concatenation is indicated by juxtaposition -- all strings of length two with symbols from the list "a,c,e".
• Let $d$ be one of those length two strings.

As written, the outermost expression is redundant. In fact anything of the form "$\{x \mid x \in X\}$" is just equivalent to $X$. (In words: the set of things that happen to be in the set $X$ is the set $X$.)

Answer 3

$$\color{blue}{ \{ d } \color{green}{\mid} \color{blue}{d} \color{red}{\in \{ b f} \color{green}{\mid} \color{red}{b, f} \color{purple}{\in \{ a, c, e \}}\color{red}{\}} \color{blue}{\}}$$

$\color{blue}{\text{The set of elements d }}\color{green}{\text{such that}}\color{blue}{\text{ d }} \color{red}{\text{is in the set of } bf}\color{green}{\text{ such that }}\color{red}{b,f}\color{purple}{\text{ are in the set } \{a,c,e\}.}$

I hope the color coding was helpful and not confusing!