Languages

Languages can be either formal or generative.

Formal: sets of strings composed of symbols from a finite set $w \in L$
Generative: you can run the machine as a generator to get strings from the language $\forall w \in L$

Properties of languages

$w \in L_{1} \cap w \in L_{2} \to w \in L_{1} L_{2}$
- if a word belongs to two languages, then it belongs to both languages
$w \in L_{1} \cup w \in L_{2} \to w \in L_{1} \cup L_{2}$
- if a word belongs to either one of the languages, then it belongs to either L1 or L2

Example

Given $L_{1} = {na t_l an g_p roc} an d L_{2} = {i s_coo l, i s_f u n}$ and $L_{3} = L_{1} L_{2}^{*}$

$x \in L_{3}$ : $n lp_i s_coo l, n lp_i s_f u n, n lp_i s_coo l_i s_coo l, n lp_i s_coo l_i s_f u n$
$L_{1} = {n lp}$ $L_{2} = "is_cool" ∣ "is_fun"$ $L_{3} = (nlp) (is_cool ∣ is_fun)$

Automa L1 (riconosce "nlp"):
(q0) --> (q1) --nlp--> [Accept]

Automa L2 (riconosce "is_cool" o "is_fun"):
(q0) --> --is_cool--> q1 [Accept]
       \            /
        ---is_fun---

Automa L3 (riconosce L1 seguito da zero o più elementi di L2):
(q0) --> (q0) --nlp--> (q1)
	    (q1) --is_cool--> [accept]
             --is_fun --> [accept]
            [Accept] in q1