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

## Operations on languages
An operation defined on a language, applies to (and is definable over) 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\}$$
In the language there is not 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\}$$

#### Strings of finite length
The language of the strings that have a length not greater than an integer k
$$L=\{\varepsilon,a,b\}^3 \;k=3$$
$$L=\{\varepsilon,a,b,aa,ab,ba,bb,aaa,...,bbb\}$$
The $\varepsilon$ is useful to obtain the strings of length 0,1,2  
We can exclude the empty string $\varepsilon$ in the following way.
$$L\{a,b\}\{\varepsilon,a,b\}^2$$
---
### Set-theoretic Operations
Are traditional operators of set theory, like __union__ $\cup$, __intersection__ $\cap$, __complement__ $\lnot$, also __strict inclusion__, __inclusion__, __equality__, __inequality__...

#### Universal language
The set of all strings defined over the alphabet $\Sigma$, also called __free monoid__.

#### Complement of a language
over the alphabet $\Sigma$ is the set-theoretic difference between the universal language and the given language
$$\lnot L =L_{universal} \setminus L$$
>The complement of a finite language is always an infinite language  
The complement of ain infinite language may be infinite or finite.

#### Set-theoretic difference
$$L_1\setminus L_2$$
Is the language containing all the strings of $L_1$ that __are not part__ of $L_2$

---
### Star Operator
Also called __Kleene star__ or __concatenation closure__.  
Is the union of all powers of a language, for every positive or null exponent.
$$L^*=\bigcup_{h=0...\infty}L^h=L^0\cup L^1\cup L^2...=\varepsilon\cup L^1\cup L^2...$$
$$L=\{ab,ba\}\;L^*=\{\varepsilon,ab,ba,abab,abba,baab,baba,...\}$$

#### Properties:
- monotonic
- closed w.r.t. Concatenation
- idempotent
- commutes with mirroring

### Cross Operator
Also called __Kleene cross__, or __$\varepsilon$-free concatenation closure__
Is the non-reflexive closure with respect to concatenation
$$L^+=\bigcup_{h=1...\infty}L^h=L^1\cup L^2\cup...$$
$$\{ab,bb\}^+ =\{ab,bb,ab^3,b^2ab,abab,b^4,...\}$$

### Quotient Operator
It shortens the strings of a language $L'$ by stripping off a *suffix* from another language $L''$
$$L=L'/L''=\{y\|(x=yz\in L')\wedge z\in L''\}$$