polimd/Formal Languages and Compilers/lesson_02.md

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''}$$