# FLC - lesson 02
##### Luca Oddone Breveglieri
###### 8 october 2015

## Operations on languages
Applies (and is defined) to each string in the language
$$L^R=\{|x=y^R\wedge y\in L\}$$
#### Prefix-free language
$$\text{prefix}(L)=\{y|x=yz\wedge x\in L\wedge y,z\neq\varepsilon\}$$
There isn't any string that is prefix of another.
$$\text{prefix(L)} \cap L=\Phi$$

#### Concatenation
$$L'L''=\{xy|x\in L' \wedge y \in L''\}$$
#### m-th power (m≥0)
$$L^m=L^{m-1}L,m>0\;\;L^0=\{\varepsilon\}$$
---
### Set-theoretic Operations
#### Universal language
The set of all strings defined over the alphabet $\Sigma$, also called __free monoid__.
#### Complement of a language
Set-theoretic difference between the universal language and the given language
$$\lnot L =L_{universal} \setminus L$$
#### Set-theoretic difference

---
### Star Operator
Also called Kleene star or Concatenation closure.  
Is the union of all powers of a language
$$L=\{ab,ba\}\;L^*=\{\varepsilon,ab,ba,abab,abba,baab,baba,...\}$$
<!--*-->
#### Properties:
- monotonic
- closed w.r.t. Concatenation
- idempotent
- commutes with mirroring

##### example
$$\sum_A=\{A,B,...,Z\} \; \sum_N=\{0,1,2,...,9\}$$

#### Cross Operator
Also called Kleene cross, or $\varepsilon$-free concatenation closure
$$\{ab,bb\}^+ =\{ab,bb,ab^3,b^2ab,abab,b^4,...\}$$

#### Quotient Operator
It shortens the phrases of a language L' by stripping off a suffix out of another languare L''
$$L=L'/L''=\{y|(x=yz\in L') x\in L''\}$$