polimd/formal_languages_and_compilers/lesson_02.md

Formal languages and compilers

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

Star Operator

Also called Kleene star or Concatenation closure.

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 of star operator

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

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

---

Regular Expressions

Regular Expresions are defined by operators over an alphabet, The operation admitted are: