polimd/Formal Languages and Compilers/lesson_02.md

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