01 Formální jazyk

Last updated Nov 9, 2022

• Množina řetězců nad nějakou abecedou
• Může být prázdná - ${\space}$
• Značíme $\Sigma$ nebo $T$
• Formální jazyk $L$ nad $\Sigma: L \subseteq \Sigma^*$

$L(G)$ = jazyk generovaný gramatikou $G$

• Prázdný jazyk $L(G)={\space} = \emptyset$ lze generovat i [regulární gramatikou](notes/bi-aag/01-klasifikace-gramatik-a-jazyku.md#Regulární gramatiky RG), tedy patří do všech tříd jazyků

Například abeceda obsahující symboly $a, b, c$ $\Sigma = {a, b, c}$

$\Sigma^+$ - množina všech neprázdných řetězců nad $\Sigma$

$\Sigma^$ - množina všech řetězců nad $\Sigma$, tedy včetně prázdného řetězce $\varepsilon$ $\Sigma^ = \Sigma^+ \cup {\varepsilon}$

• Všechny řetězce doplněny do abecedy
• $L$ nad $\Sigma$
• Může být konečný jen pro prázdnou abecedu

• Sjednocení
• Průnik
• Rozdíl

Značíme tečkou $\Large{\cdot}$ $L = L_{1}\cdot L_{2}={xy: x \in L_{1}, y\in L_2}$, $L$ je definován nad abecedou $\Sigma = \Sigma_{1}\cup \Sigma_2$

Značíme hvězdičkou $\large{^}$ $L^{}= L^{0} \cup L^{1} \cup L^{2} \cup L^{3} \cup\dots$

$L^{0} = {\varepsilon}$ $L^{1}=L$ $L^{2}=L \cdot L$ $L^{3}=L \cdot L \cdot L$

Značíme plusem $\large{^+}$ $L^{+}= L^{1} \cup L^{2} \cup L^{3} \cup\dots$

Neobsahuje $L^{0}$