Formální jazyky a jejich hierarchie

Abeceda a jazyk

Abeceda

• libovolná konečná množina $\Sigma$
• prvky nazýváme znaky abecedy

Příklad abecedy

• množina $\{a,b\}$
• množina $\{0,1,...,9\}$
• množina $\varnothing$

Slovo

• Slovo $v$ nad abecedou $\Sigma$ je libovolná konečná posloupnost znaků této abecedy
• Počet členů této posloupnosti značíme $|v|$ a nazýváme délkou slova
• Počet výskytů znaku $a$ ve slově $v$ značíme ${\#}_a(v)$
• Prázdné posloupnosti znaků odpovídá tzv. prázdné slovo
  • značíme $ϵ$, které má nulovou délku
• Množina všech slov nad abecedou $\Sigma$ značíme ${\Sigma }^{\ast }$
• Množinu všech neprázdných slov ${\Sigma }^{+}$

Příklad

• $\{a{\}}^{\ast }=\{ϵ,a,aa,aaa,aaaa,...\}$
• $\{a{\}}^{+}=\{a{\}}^{\ast }$\$\{ϵ\}$
• $\{0,1{\}}^{\ast }=\{ϵ,0,1,00,01,10,11,000,001,011,...\}$

• Definitoricky dále klademe ${\varnothing }^{\ast }=\{ϵ\}$ a ${\varnothing }^{+}=\varnothing$
• Na každé dvě slova $u,v$ lze aplikovat binární operaci zřetězení, která je definována $u.v=uv$

Příklad zřetězení slov

• zřetězením slov $abba$ a $bba$ obdržíme slovo $abbabba$

• Operace zřetězení je asociativní

  • $u.(v.w)=(u.v).w$ pro libovolná slova $u,v,w$

• Déle $ϵ$ se chová jako jednotkový prvek

  • $u.ϵ=ϵ.u=u$ pro libovolné $u$

• Pro snazší specifikaci jazyků je výhodné zavést unární operaci $i$-té mocniny slova, která je definovaná induktivně pro každé $i\in N_0$ takto:

  • Nechť $\Sigma$ je libovolná abeceda, $u\in {\Sigma }^{\ast }$ libovolní slovo. Pak
    • $u^0=ϵ$
    • $u^{i+1}=u.u^i$

Příklad i-té mocniny slova

• $(abc{)}^3=abcabcabc$

• Pro slova $u,v\in {\Sigma }^{\ast }$ platí:

  • $u=v$, právě když $|u|=|v|$ a zároveň $u_i=v_i$ pro všechna $i=1,...,|u|$

• Slovo $u$ je podslovem slova $v$, jestliže existují slova $x,y$ taková, že $v=x.u.y$

  • Pokud navíc $x=ϵ$, říkáme že slovo $u$ je předponou (prefixem) slova $v$

• Je-li $y=ϵ$ nazveme $u$ příponou (sufix) slova $v$

Jazyk

• Jazyk nad abecedou $\Sigma$ je libovolná množina slov nad $\Sigma$ (Jazyk nad $\Sigma$ je tedy právě podmnožina ${\Sigma }^{\ast }$)

Příklady

• $\{10,1,011101\}$ je jazyk nad abecedou $\{0,1\}$
• prázdná množina je jazyk nad libovolnou abecedou

• Jazyky mohou ovšem být i nekonečné

Příklad nekonečných jazyků

• $\{w\in \{a,b{\}}^{\ast }\mid {\#}_a(w)={\#}_b(w)\}$ je jazyk nad abecedou $\{a,b\}$ obsahující všechna slova, ve kterých se $a$ i $b$ vyskytují ve stejném počtu

Operace nad jazyky

• Nechť $L$ je libovolný jazyk nad abecedou $\Sigma$ a $K$ libovolný jazyk nad abecedou $\Delta$.
• Jelikož $L$ i $K$ jsou množiny, můžeme aplikovat standarní množinové operace sjednocení, průnik a rozdíl. Výsledkem je vždy jazyk nad abecedou $\Sigma \cup \Delta$.
• Dále definujeme:
  • Zřetězení jazyků $K$ a $L$ je jazyk $K.L=\{uv\mid u\in K,v\in L\}$ nad abecedou $\Sigma \cup \Delta$.
    • Podle definice zejména platí $\varnothing .M=M.\varnothing =\varnothing$ a $\{ϵ\}.M=M.\{ϵ\}=M$ pro libovolný jazyk $M$. Operace zřetězení jazyků je také zřejmě asociativní
  • $i$-tá mocnina jazyka $L$ je definována induktivně pro každé $i\in N_0$:
    • $L^0=\{ϵ\}$
    • $L^{i+1}=L.L^i$ Zejména tedy ${\varnothing }^0=\{ϵ\},{\varnothing }^i=\varnothing$ pro libovolné $i\in N$ a $\{ϵ{\}}^i=\{ϵ\}$ pro libovolné $j\in N_0$
  • Iterace jazyka $L$ je jazyk $L^{\ast }={\cup }_{i=0}^{\infty }{L}^i$
  • Pozitivní iterace jazyka $L$ je taky $L^{+}={\cup }_{i=0}^{\infty }{L}^i$. Obecně není pravda, že $L^{+}=L^{\ast }\backslash \{ϵ\}$
    • tato rovnost platí právě tehdy, když $L$ neobsahuje $ϵ$
  • Doplněk jazyka $L$ je jazyk co-L = ${\Sigma }^{\ast }\backslash L$
  • Zrcadlovým obrazem (též reverzí) slova $x=a_1,...,a_n$ nazýváme slovo ${\omega }^R=a_n,...,a_1$. Zrcadlový obraz jazyka $L$ definujeme jako $L^R=\{{\omega }^R\mid {\omega }^L\}$
  • Substituce $f$ je zobrazení abecedy $\Sigma$ do podmnožiny ${\Delta }^{\ast }$
    • tj. přiřazuje každému $a\in \Sigma$ jazyk $f(a)\subseteq {\Delta }^{\ast }$.
    • Zobrazení $f$ je rozšířeno na slova takto:
      • $f(ϵ)=ϵ$
      • $f(xa)=f(x).f(a)$ $f$ rozšíříme na jazyk tak, že pro každé $L\subseteq {\Sigma }^{\ast }$ klademe $f(L)={\cup }_{x\in L}f(x)$.
  • Speciálním případem substituce je homomorfismus $h$, který definujeme jako substituci, u níž $h(a)$ obsahuje jediné slovo pro každé $a\in \Sigma$.
  • Je-li $h$ homomorfismus, pak definujeme inverzní homomorfní obraz jazyka $L$ jako $h^{-1}(L)=\{x\mid h(x)\in L\}$ a pro slova definujeme inverzní homomorfismus jako $h^{-1}(w)=\{x\mid h(x)=w\}$.

Konečná reprezentace jazyka

• Konečná reprezentace by měla být opět řetězcem symbolů (nad jistou abecedou), který budeme vhodně interpretovat tak, aby danému jazyku odpovídala nějaká, ne nutně jediná, konkrétní konečná reprezentace. Obráceně pak, aby každé konkrétní konečné reprezentaci odpovídal jediný konkrétní jazyk.
• Takovými reprezentacemi pro nás budou zejména tzv. gramatiky a automaty

Gramatika

• Gramatika $G$ je uspořádaná čtveřice $G=(N,\Sigma ,P,S)$, kde:

  1. $N$ je neprázdná konečná množina neterminálních symbolů
  2. $\Sigma$ je konečná množina terminálních symbolů
     • platí $\Sigma \cap N=\varnothing$
     • Sjednocení $N$ a $\Sigma$ obdržíme množinu všech symbolů gramatiky, kterou obvykle označujeme symbolem $V$
  3. $P$ je konečná množina pravidel ve tvaru $P\subseteq V^{\ast }N{V}^{\ast }\times V^{\ast }$.
     • Pravidlo $(\alpha ,\beta )$ obvykle zapisujeme ve tvaru $\alpha \to \beta$
  4. $S\in N$ je počáteční neterminál

• Podmínka kladená na tvar pravidel $\alpha \to \beta$ pouze požaduje, aby $a$ (levá strana pravidla) obsahovala alespoň jeden neterminál, na $\beta$ (pravou stranu pravidla) nejsou obecně kladeny žádné požadavky - speciálně, může být i prázdným slovem $ϵ$

• Relaci přímého obvození $\gamma {\Rightarrow }_G\sigma$ chápeme jako aplikaci konkrétního pravidla na řetězec $\gamma =\eta \alpha \rho$, jehož výsledkem je řetězec $\eta \beta \rho$, neboli: $\eta \alpha \rho {\Rightarrow }_G\eta \beta \rho$, kde $\eta ,\rho \in V^{\ast }$ a $\alpha \to \beta$ je právě aplikované pravidlo gramatiky $G$

  • (pokud je gramatika zřejmá z kontextu, pak můžeme označení $G$ u šipky vynechat)

• ${\Rightarrow }_G^{\ast }$ umožňuje při odvození aplikovat libovolný počet libovolných pravidel

• Derivace = proces, kdy na řetězec aplikujeme konečný počet kroků odvození

• ${\Rightarrow }_{lm}$ značí nejlevější derivaci - přepisujeme vždy podle nejlevějšího neterminálu

  • analogicky ${\Rightarrow }_{rm}$ je nejpravější derivace

• Jazyk, který gramatika $G$ generuje, definujeme jako $L(G)=\{w\in {\Sigma }^{\ast }\mid S{\Rightarrow }_G^{\ast }w\}$

  • (řetězce v jazyce $G$ už neobsahují neterminály)

Příklad

• Nechť $G=(\{S,A,B\},\{a,b\},P,S)$, kde $P=\{S\to ABS,$ $S\to ϵ,$ $AB\to BA,$ $BA\to AB,$ $A\to a,$ $B\to b\}$
• Pak např. $AaBAbBS$ je větná forma $G$, zatímco $ABb$ nikoliv.
• Jazyk $L(G)$ vypadá takto: $L(G)=\{u\in \{a,b{\}}^{\ast }\mid {\#}_a(u)={\#}_b(u)\}.$

Chromského hierarchie gramatik a jazyků

• Lingvista Noam Chomsky rozdělil gramatiky do čtyř skupin (typů) na základě různých omezení na tvar pravidel
• Jeho práce byla původně motivována úvahami o struktuře přirozeného jazyka, z dnešního pohledu má však především význam jako základní rozdělení gramatik podle jejich popisné síly.
• Chomského hierarchie rozlišuje tyto čtyři (základní) typy gramatik:

Typ 0

• Libovolná gramatika je gramatikou typu $0$
• Na tvar pravidel se nekladou žádné omezující požadavky
• Někdy se též taková gramatiky označují jako gramatiky bez omezení či frázové gramatiky

Typ 1

• Též kontextová gramatika, Context-Sensitive, CSG, méně často též monoténní
• Gramatika je typu $1$, jestliže pro každé její pravidlo $\alpha \to \beta$ platí $|\alpha |\le |\beta |$ s eventuelní výjimkou pravidla $S\to ϵ$, pokud se $S$ nevyskytuje na pravé straně žádného pravidla

Typ 2

• Též bezkontextová gramatika, Context-Free, CFG
• Gramatika je typu $2$, jestliže každé její pravidlo je tvaru $A\to \alpha$, kde $|\alpha |\ge 1$ s eventuelní výjimkou pravidla $S\to ϵ$, pokud se $S$ nevyskytuje na pravé straně žádného pravidla

Typ 3

• Též regulární gramatika, pravolineární
• Gramatika je typu $3$, jestliže každé její pravidlo je tvaru $A\to aB$ nebo $A\to a$ s eventuelní výjimkou pravidla $S\to ϵ$, pokud se $S$ nevyskytuje na pravé straně žádného pravidla

---

• Hierarchie gramatik také určuje příslušnou hierarchii jazyků
• Z definice je patrné, že každý nový typ gramatiky v Chomského hierarchii je specifikován zavedením dalších omezujících podmínek na typ předchozí

Příklad

• Každá regulární gramatika je také gramatikou bezkontextovou, kontextovou i typu $0$
• Naopak to ovšem neplatí

Tvrzení

• Nak abecedou $\{a\}$ existuje jazyk, který není typu $0$.
• (Existuje nespočetně mnoho jazyků nad abecedou $\{a\}$, tedy je nelze vyjádřit konečnou reprezentací)

Navigace

Předchozí: Geometrická interpretace určitého integrálu Následující: Regulární jazyky (definice, uzávěrové vlastnosti) Celý okruh: 1. Teoretické základy informatiky